7.6 42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
我的思路：
时间超限了很多次，尽量一次循环得到结果，经过分析我们发现：水=高的-当前的水的高度
我们需要动态更新最大高度，因为是双指针，所以两边都要动态更新
我的代码：
function trap(height: number[]): number {
let ans = 0;
let leftMax = 0;
let rightMax = 0;
let left = 0 ;
let right = height.length - 1;
while(left < right){
// 左边
if(height[left] < height[right]){
if(height[left] >= leftMax){
leftMax = height[left];
}else {
ans += leftMax - height[left];
}
left++;
}
else {
if(height[right] >= rightMax){
rightMax = height[right];
}else {
ans += rightMax - height[right];
}
right--;
}
}
return ans;
}
总结：
明确维护了leftMax和rightMax两个变量来记录当前指针左侧/右侧的最大高度，每次移动较低指针，确保能正确计算该位置能接的雨水。
7.6 13. 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。X可以放在L(50) 和C(100) 的左边，来表示 40 和 90。C可以放在D(500) 和M(1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
我的思路：
特例：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
IV IX XL XC CD CM
我想到的就是遍历判断特例
ans
先一个个变为数字？
111
15 大数字应该在左边，1<5 5-1
110 10-1 = 9
50 5 1 1
1000 100 1000 10 100 1 5
1000
哈希表：键(罗马数字)值(阿拉伯数字)对
双指针
我的代码：
function romanToInt(s) {
// 两个哈希表，应该是普通的字符，应该是特殊的字符
const commonMap = new Map([
["I", 1],
["V", 5],
["X", 10],
["L", 50],
["C", 100],
["D", 500],
["M", 1000]
]);
const specialMap = new Map([
["CM", 900],
["CD", 400],
["IV", 4],
["IX", 9],
["XL", 40],
["XC", 90]
]);
// 双指针遍历字符
let i = 0 ;
let j = i + 1;
let ans = 0;
while(j <= s.length){
let str = s[i] + s[j];
console.log(str);
if(specialMap.has(str)){
ans +=specialMap.get(str);
i+=2;
j+=2;
}else if(commonMap.has(s[i])) {
ans += commonMap.get(s[i]);
i++;
j++;
}
console.log(ans);
}
return ans;
};
注意！初始化Map直接初始化就可以了：
const specialMap = new Map([
["CM", 900],
["CD", 400],
["IV", 4],
["IX", 9],
["XL", 40],
["XC", 90]
]);
总结：
- 字符与数值的映射：首先，定义一个映射关系，将每个罗马数字字符映射到其对应的整数值。
- 双指针扫描：使用两个指针（i 和 i1）遍历字符串，检查当前字符和下一个字符的组合。
- 特殊组合处理：如果当前字符和下一个字符组合成特殊字符（如 “IV”、“IX” 等），则将这些特殊组合转换为对应的整数值，并跳过下一个字符。
- 普通字符处理：如果当前字符不是特殊组合的一部分，则直接将其转换为对应的整数值。
- 累加结果：将所有转换后的整数值累加，得到最终结果。