[算法] 优先算法(四):滑动窗口(下)

🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:
🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm=1001.2014.3001.5482
🍕 Collection与数据结构 (92平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀Java EE(94平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~

✒️ 期末考试结束,暑假回归,文章将会保持更新.

6. 水果成篮(难度:🟡3度)

OJ链接

题目描述

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。
示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

算法原理
研究的对象是⼀段连续的区间，可以使用「滑动窗口」思想来解决问题。
让滑动窗口满足：窗口内水果的种类只有两种。
右端水果进入窗口的时候，用哈希表统计这个水果的频次。这个水果进来后，判断哈希表的大小：
▪ 如果大小超过2：说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口，直到哈希表的大小小于等于2，然后更新结果；
▪ 如果没有超过2，说明当前窗口内水果的种类不超过两种，直接更新结果ret。
算法流程
a. 初始化哈希表hash来统计窗口内水果的种类和数量；
b. 初始化变量：左右指针left=0，right=0，记录结果的变量ret=0；
c. 当right小于数组大小的时候，⼀直执行下列循环：
i. 将当前水果放入哈希表中；
ii. 判断当前水果进来后，哈希表的大小：
• 如果超过2：
◦ 将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀；
◦ 如果这个元素的频次减⼀之后变成了0，就把该元素从哈希表中删除；
◦ 重复上述两个过程，直到哈希表中的大小不超过2；
iii. 更新结果ret；
iv. right++，让下⼀个元素进入窗口；
d. 循环结束后，ret存的就是最终结果。
代码实现

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer,Integer> hash = new HashMap<>();
        int ret = 0;
        for (int right = 0,left = 0;right < fruits.length;right++){
            hash.put(fruits[right],hash.getOrDefault(fruits[right],0)+1);
            while(hash.size() > 2){
                hash.put(fruits[left],hash.get(fruits[left])-1);
                if (hash.get(fruits[left]) == 0){
                    hash.remove(fruits[left]);
                }
                left++;
            }
            ret = Math.max(ret,right-left+1);
        }
        return ret;
    }
}

7. 找到字符串中的所有字母异位词(难度:🟠4度)

OJ链接

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

算法原理(滑动窗口+哈希表)
- 首先这道题的窗口大小是固定的,大小就是p的长度.要是窗口大小小于或等于p的长度,就要进窗口,大于就要出窗口.
- 这道题需要用到两个哈希表,hash1用来统计p中的字母种类及其个数.hash2用来统计窗口范围内的字母种类和个数.
- 这道题还需要用count这个变量来统计窗口范围中有效的字符个数.
  - 如果窗口中某个字母的个数<=hash1中某个字母的个数,那么这个字母就是有效字母,在进窗口时要给count++,在出窗口的时候,就要给count–.
  - 在每一次进出窗口,并处理count之后,如果count == p.length(),说明count中全部是有效字母,这个区间就是要找的区间.记录在list中.
代码实现

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        Map<Character,Integer> hash1 = new HashMap<>();
        Map<Character,Integer> hash2 = new HashMap<>();
        for (int i = 0 ; i < p.length() ; i++){
            hash1.put(p.charAt(i),hash1.getOrDefault(p.charAt(i),0)+1);
        }
        int count = 0;//用来统计有效字符个数
        for (int left = 0,right = 0;right < s.length();right++){
            char in = s.charAt(right);
            hash2.put(in,hash2.getOrDefault(in,0)+1);//进窗口
            if (hash2.get(in) <= hash1.getOrDefault(in,0)){//大于hash1中的重复字符不计入
                count++;//统计有效字符
            }
            if (right-left+1 > p.length()){//窗口大于p的长度,出窗口
                char out = s.charAt(left);
                if (hash2.get(out) <= hash1.getOrDefault(out,0)){//看出的是否是有效字符
                    count--;
                }
                hash2.put(out,hash2.get(out)-1);//判断完成之后再出窗口
                left++;
            }
            if (count == p.length()){//说明窗口里面全部是有效字符
                list.add(left);
            }
        }
        return list;
    }
}

8. 串联所有单词的子串(难度:🔴5度)

OJ链接

题目描述

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串长度相同。
s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]，那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”，和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以任意顺序返回答案。
示例 1：
输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。

算法原理(滑动窗口+哈希表)
这道题的算法原理与上一道题非常类似,只不过现在的对象不是字母,而是字符串,只需要把一个个的字符串看成一个个的字母即可.
但是这道题还是有和上一道题不一样的地方,一共有三点:
- 哈希表存放元素的种类不一样,hash<String,int>.
- left与right指针移动的步长不一样,这里移动的步长是words中每个单词的长度.
- 滑动窗口执行的次数不一样,一共执行words中每个单词的长度的次数.原理如下图:
代码实现

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        Map<String,Integer> hash1 = new HashMap<>();
        int len = words[0].length();
        for (int i = 0;i < words.length;i++){
            hash1.put(words[i],hash1.getOrDefault(words[i],0)+1);
        }
        for (int i = 0;i < len;i++){//滑动窗口执行的次数
            int count = 0;
            Map<String,Integer> hash2 = new HashMap<>();
            for (int left = i,right = i;right+len <= s.length();right+=len){
                String in = s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if (hash2.get(in) <= hash1.getOrDefault(in,0)){
                    count++;
                }
                if (right-left+1 > words.length*len){
                    String out = s.substring(left,left+len);
                    if (hash2.get(out) <= hash1.getOrDefault(out,0)){
                        count--;
                    }
                    hash2.put(out,hash2.getOrDefault(out,0)-1);
                    left += len;
                }
                if (words.length == count){
                    list.add(left);
                }
            }
        }
        return list;
    }
}