【LeetCode热题100】接雨水+无重复字符的最长子串+找到字符串中所有字母异位词

42.接雨水

思路：
按照列计算
每列的宽度是1
所以每列承接雨水即为雨水的高度
这一列高度通过看图计算我们可以得到h=min(lh,rh)-h[i]
lh是这一列左侧最高柱子的高度，rh为这一列右侧最高柱子的高度
当遇到第一个和最后一个时我们不计算雨水（装不了）

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    const len=height.length
    let sum=0
    for(let i=0;i<len;i++){
        if(i==0||i==len-1) continue
        let rh=height[i]
        let lh=height[i]
        for(let r=i+1;r<len;r++){
            if(height[r]>rh) rh=height[r]
        }
        for(let l=i-1;l>=0;l--){
            if(height[l]>lh) lh=height[l]
        }
        let h=Math.min(rh,lh)-height[i]
        if(h>0) sum+=h
    }
    return sum
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.无重复字符的最长子串

思路：
双指针，用left记录子串的起始点，right负责右移取最大值
用s.charAt(right)判断是否有重复值
有的话l右移
没有r右移
然后更新最大值

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length<=1) return s.length
    let left=0;
    let right=1;
    let max=0
    let temp
    while(right<s.length){
        temp=s.slice(left,right)
        if(temp.indexOf(s.charAt(right))>-1){
            left++;
            continue
        }else{
            right++;
        }
        if(right-left>max) max=right-left
    }
    return max
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

438.找到字符串中所有字母异位词

思路：
用滑动窗口的思路，遍历字符串。
判断进入窗口的字符是否是需要的字符（种类），并且加入窗口之后该字符的数量是否是和need中的字符数量一致。
判断出窗口的字符是否是需要的字符（种类），并且该字符在窗口中的数量是否和need中的字符数量一致
判断窗口中和need中符合要求的字符是否一致 如果一致 则这个窗口形成的子串就是一个异位词

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let need={}
    let win={}
    for(let a of p){
        need[a]=(need[a]||0)+1;
    }
    let l=0
    let r=0
    let val=0
    let res=[]
    while(r<s.length){
        let c=s[r]
        r++
        if(need[c]){
            win[c]=(win[c]||0)+1
            if(win[c]==need[c]) val++
        }
        while(r-l>=p.length){
            if(val==Object.keys(need).length){
                res.push(l)
            }
            let d=s[l]
            l++
            if(need[d]){
                if(win[d]==need[d]) val--
                win[d]--
            }
        }
    }
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36