LeetCode刷题笔记——HOT100面试题（10）

算法
,

滑动窗口

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

参见《剑指Offer》最长不含重复字符的子字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int l = 0, r = 0, res = 0;
        while (r<s.length()) {
            char c = s.charAt(r);
            if (map.containsKey(c)) {
                l = Math.max(l, map.get(c)+1);
            }
            res = Math.max(res, r-l+1);
            map.put(c, r);
            r++;
        }
        return res;
    }
}

76. 最小覆盖子串

使用滑动窗口模拟最小覆盖子串，用数组记录所需的字符数量和窗口中的字符数量。首先向右扩张窗口边界直到滑动窗口包含全部所需的字符，然后不断向右缩小左边界直到窗口中不满足全部所需字符，同时不断更新最小覆盖子串的长度。

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
37
38
class Solution {
    public String minWindow(String s, String t) {
        // l和r用于保存当前最小覆盖子串的左右下标
        int l = -1, r = -1, minLen = Integer.MAX_VALUE;
        // need用于统计所需要的字符，count用于计数所需字符总数
        int[] need = new int[128];
        int count = 0;
        for (char c: t.toCharArray()) {
            need[c]++;
            count++;
        }
        // window用于计数滑动窗口中的字符
        int[] window = new int[128];
        int i = 0, j = 0;
        while (j<s.length()) {
            // 扩张右边界
            char rc = s.charAt(j);
            window[rc]++;
            if (window[rc]<=need[rc]) count--;
            // 滑动窗口包含所有所需字符，开始缩减左边界
            while (count==0) {
                // 更新最小覆盖子串的长度
                if (minLen>j-i+1) {
                    minLen = j-i+1;
                    r = j;
                    l = i;
                }
                char lc = s.charAt(i);
                window[lc]--;
                i++;
                if (window[lc]<need[lc]) count++;   
            }
            j++;
        }
        // 如果l没有更新过，说明不存在覆盖子串
        return l>=0? s.substring(l, r+1): "";
    }
}

239. 滑动窗口最大值

参见《剑指Offer》滑动窗口的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length==0) return new int[]{};
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i=0; i<k; i++) {
            while (!queue.isEmpty() && queue.peekLast()<nums[i]) {
                queue.pollLast();
            }
            queue.offer(nums[i]);
        }
        int[] res = new int[nums.length-k+1];
        res[0] = queue.peek();
        for (int i=k; i<nums.length; i++) {
            if (nums[i-k]==queue.peekFirst()) queue.pollFirst();
            while (!queue.isEmpty() && queue.peekLast()<nums[i]) {
                queue.pollLast();
            }
            queue.offer(nums[i]);
            res[i-k+1] = queue.peekFirst();
        }
        return res;
    }
}

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

此题与76题相似，不同的是只记录窗口中所需字符的数量，并且只当窗口大小与模式字符串相等时才判断是否是字母异位词，然后缩小左边界。

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
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] need = new int[128];
        for (char c: p.toCharArray()) {
            need[c]++;
        }
        int count = 0;
        int[] window = new int[128];
        int left = 0, right = 0;
        ArrayList<Integer> res = new ArrayList<>();
        while (right < s.length()) {
            char rc = s.charAt(right);
            if (need[rc]>0) {
                window[rc]++;
                if (window[rc]<=need[rc]) {
                    count++;
                }
            }
            right++;
            while (count==p.length()) {
                if (right-left==p.length()) {
                    res.add(left);
                }
                char lc = s.charAt(left);
                if (need[lc]>0) {
                    window[lc]--;
                    if (window[lc]<need[lc]) {
                        count--;
                    }
                }
                left++;
            }
        }
        return res;
    }
}