[算法] 优先算法(四):滑动窗口(下)
🌸个人主页: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度)
- 7. 找到字符串中的所有字母异位词(难度:🟠4度)
- 8. 串联所有单词的子串(难度:🔴5度)
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 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 findAnagrams(String s, String p) { List list = new ArrayList<>(); Map hash1 = new HashMap<>(); Map 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
- left与right指针移动的步长不一样,这里移动的步长是words中每个单词的长度.
- 滑动窗口执行的次数不一样,一共执行words中每个单词的长度的次数.原理如下图:
- 哈希表存放元素的种类不一样,hash
- 代码实现
class Solution { public List findSubstring(String s, String[] words) { List list = new ArrayList<>(); Map 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 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; } }
上一篇：工厂视频监控_工厂建模
下一篇：电脑管理员程序在哪里