【读书笔记：算法小抄】滑动窗口算法——Java版实现_java滑动时间窗口并发实现

作者：很楠不爱3 | 2024-03-20 15:45:05

踩

java滑动时间窗口并发实现

算法实现列表

最小覆盖子串
字符串排列
找所有字母异位词
最长无重复子串

Java基础

HashMap中的getOrDefault(key, defaultValue)函数说明：如果map中没有key对应的键值value，则返回默认值defaultValue。

参考代码

最小覆盖子串
给你两个字符串S和T，请你在S中找到包含T中全部字母的最短子串。如果S中没有这样一个子串，则算法返回空串，如果存在这样一个字串，则可以认为答案是唯一的。比如输入S = “ADBECFEBANC”，T = “ABC”，算法应该返回“BANC”。

package com.company;
import static java.lang.System.out;
import java.util.*;

public class Main {
    /* 滑动窗口算法 */
    // 1. Leetcode之最小覆盖子串
    // 给你两个字符串S和T，请你在S中找到包含T中全部字母的最短子串。
    // 如果S中没有这样一个子串，则算法返回空串，如果存在这样一个字
    // 串，则可以认为答案是唯一的。
    // 比如输入S = “ADBECFEBANC”，T = “ABC”，算法应该返回“BANC”
    public static String minWindow(String s, String t){
        // need为T中字符出现的次数，window表示“窗口”中相应字符的出现次数
        HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        for(char c: t.toCharArray()){
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        // 窗口中满足need条件的字符个数
        int valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()){
            // c为将要移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 如果窗口中某个字符出现的数量满足need中的需要，就更新valid
                if (window.get(c) == need.get(c))
                    valid++;
            }

            // 判断左侧窗口是否需要收缩
            while(valid == need.size()){
                // 在这里更新最小覆盖子串
                if (right - left < len){
                    start = left;
                    len = right - left;
                }
                // d是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 若弹出的这个字符是需要的字符，则进行窗口内数据的一系列更新
                if (need.containsKey(d)){
                    // 如果窗口内的字符已经满足要求，此时移出应该更新valid
                    if (window.get(d) == need.get(d))
                        valid--;
                    // 窗口内相应字符数量减少一个
                    //（因为之前必然已经添加过该字符，所以可以放心的删除）
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    public static void main(String[] args) {
        String s = "ADBECFEBANC";
        String t = "ABC";
        String res = minWindow(s, t);

        out.println(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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

字符串排列
输入两个字符串S和T，请你用算法判断S是否包含T的排列，也就是要判断S中是否存在一个子串T的全排列，比如输入S = “helloworld”, T = “oow”，算法返回true，因为S包含一个子串“owo”是T的全排列。

package com.company;
import static java.lang.System.out;
import java.util.*;

public class Main {
    /* 滑动窗口算法 */
    // 2. 字符串排列
    // 输入两个字符串S和T，请你用算法判断S是否包含T的排列
    // 也就是要判断S中是否存在一个子串T的全排列
    // 比如输入S = “helloworld”, T = "oow"，算法返回true，
    // 因为S包含一个子串“owo”是T的全排列
    public static Boolean checkInclusion(String s, String t){
        HashMap<Character, Integer> need, window;
        need = new HashMap<>();
        window = new HashMap<>();

        for(char c: t.toCharArray()){
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;
        while (right < s.length()){
            char c1 = s.charAt(right);
            right++;

            if (need.containsKey(c1)){
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                if (window.get(c1) == need.get(c1))
                    valid++;
            }

            while (right - left >= t.length()){  // 实测此处改成"=="也是OK的
                if (valid == need.size()){
                    return true;
                }

                char c2 =  s.charAt(left);
                left++;

                if (need.containsKey(c2)){
                    if (window.get(c2) == need.get(c2))
                        valid--;
                    window.put(c2, window.get(c2) - 1);
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        String s = "helloworld";
        String t = "oow";
        Boolean res = checkInclusion(s, t);
        out.println(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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

找所有字母异位词
给定一个字符串S和一个非空字符串T，找到S中所有是T的字母异位词的子串，返回这些子串的起始索引。
备注：题目相当于让你找S中所有T的排列，并返回它们的起始索引。比如输入S = “cbaebabacd”, T = abc, 算法返回 [0, 6]，因为S中有两个子串“cba”和"bac"是T的排列。

package com.company;
import static java.lang.System.out;
import java.util.*;

public class Main {
    /* 滑动窗口算法 */
    // 3. 找所有字母异位词
    // 给定一个字符串S和一个非空字符串T，找到S中所有是T的字母
    // 异位词的子串，返回这些子串的起始索引。
    // 备注：题目相当于让你找S中所有T的排列，并返回它们的起始
    // 索引。比如输入S = "cbaebabacd", T = abc, 算法返回
    // [0, 6]，因为S中有两个子串“cba”和"bac"是T的排列。
    public static ArrayList<Integer> findAnagrams(String s, String t){
        ArrayList<Integer> res = new ArrayList<>();
        HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        for(char c: t.toCharArray()){
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;

        while (right < s.length()){
            char c1 = s.charAt(right);
            right++;

            if (need.containsKey(c1)){
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                if (window.get(c1) == need.get(c1))
                    valid++;
            }

            while (right - left >= t.length()){  // 直接写为if(right - left == t.length())也可
                if (valid == need.size())
                    res.add(left);

                char c2 = s.charAt(left);
                left++;

                if (need.containsKey(c2)){
                    if (window.get(c2) == need.get(c2))
                        valid--;
                    window.put(c2, window.get(c2) - 1);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String t = "abc";
        ArrayList<Integer> res = findAnagrams(s, t);
        for(int i: res){
            out.print(i);  // 06
        }
    }

}


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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

最长无重复子串
输入一个字符串s，请计算s中不包含重复字符的最长子串长度。比如，输入s = “aabab”，算法返回2，因为无重复的最长子串是"ab"或"ba"，长度为2。

package com.company;
import static java.lang.System.out;
import java.util.*;

public class Main {
    /* 滑动窗口算法 */
    // 4. 最长无重复子串
    // 输入一个字符串s，请计算s中不包含重复字符的最长子串长度。
    // 比如，输入s = "aabab"，算法返回2，因为无重复的最长子串
    // 是"ab"或"ba"，长度为2。
    public static int lengthOfLongestSubstring(String s){
        HashMap<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int maxLen = 0;

        while (right < s.length()){
            char c1 = s.charAt(right);
            right++;

            window.put(c1, window.getOrDefault(c1, 0) + 1);

            // 窗口中存在重复字符就移动left，缩小窗口
            while (window.get(c1) > 1){
                char c2 = s.charAt(left);
                left++;

                window.put(c2, window.get(c2) - 1); // 因为是已经滑过的创建，必然包含c2，可以放心的删除
            }

            if (right - left > maxLen){
                maxLen = right - left;
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        String s = "aabab";
        int res = lengthOfLongestSubstring(s);
        out.print(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
37
38
39
40
41
42
43
44
45
46

参考资料

https://www.geeksforgeeks.org/hashmap-getordefaultkey-defaultvalue-method-in-java-with-examples/

如果你认为对你有用，关注我的微信公众号支持我一下吧！~

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/274751