中科 网站会员注册系统建设,抖音开放平台是干什么的,脚本外链生成工具,广州建设档案馆网站目录 一.滑动窗口
1.什么滑动窗口
2.滑动窗口的三要素
二.找到字符串中所有字母异位词
1.题目描述
2.问题分析
3.代码实现
三.字符串的排列
1.题目描述
2.问题分析
3.代码实现
四.考试的最大困扰度
1.题目描述
2.问题分析
3.代码实现
五.替换后的最长重复字符 …目录 一.滑动窗口
1.什么滑动窗口
2.滑动窗口的三要素
二.找到字符串中所有字母异位词
1.题目描述
2.问题分析
3.代码实现
三.字符串的排列
1.题目描述
2.问题分析
3.代码实现
四.考试的最大困扰度
1.题目描述
2.问题分析
3.代码实现
五.替换后的最长重复字符
1.题目描述
2.问题分析
3.代码实现
六.尽可能使字符串相等
1.题目描述
2.问题分析
3.代码实现
七.每种字符至少取 K 个
1.题目描述
2.问题分析
3.代码实现 一.滑动窗口
1.什么滑动窗口
滑动窗口是通过双指针同向移动而解决的一类问题
经常用于数组或者字符串求其满足条件的连续子序列或者子串将原先需要嵌套循环问题转换为单循环问题降低时间复杂度
主要分为两大类,一种是长度固定的滑动窗口,一种是长度动态变化的滑动窗口 2.滑动窗口的三要素
我们分析问题主要就是考虑这三要素,寻找满足题意的条件,使窗口的右端(right)可以向右滑行,满足条件的时候,使窗口的左端(left)向右滑行,进行收缩,直到对整个数组(或字符串)线性遍历完成
窗口扩展是寻找可行解
窗口收缩是优化可行解
窗口只能从左至右滑动
注意:长度固定的滑动窗口不需要扩张和收缩,只需要保持固定的长度向右滑动即可
二.找到字符串中所有字母异位词
1.题目描述 给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串包括相同的字符串。 力扣:力扣
2.问题分析
首先我们需要理解异位词,其实就是含有各个字母数量和一个子串的字母数量相同,那么就可以成为异位,例如(aab)和(baa),他们的长度也是相同的,所以只需要在字符串s中找到长度和p字符串长度相同且各个字母数量相同的字符串即可.这很容易可以想象到滑动窗口,并且长度固定为p的长度的窗口
这里我们采用一个长度为26的字符数组来统计长度为p长度的滑动窗口的字母数量,和p的字符数组进行比较,相同即可加入到list数组中
3.代码实现 public ListInteger findAnagrams(String s, String p) {ArrayListInteger list new ArrayList();if (p.length() s.length())return list;int[] sCount new int[26];int[] pCount new int[26];for (int i 0; i p.length(); i) {pCount[p.charAt(i) - a];}for (int i 0; i p.length() - 1; i) {sCount[s.charAt(i)-a];}for (int i 0; i s.length() - p.length(); i) {sCount[s.charAt(i p.length() - 1)-a];if (Arrays.equals(sCount, pCount)) {list.add(i);}sCount[s.charAt(i)-a]--;}return list;}
三.字符串的排列
1.题目描述 给你两个字符串 s1 和 s2 写一个函数来判断 s2 是否包含 s1 的排列。如果是返回 true 否则返回 false 。 换句话说s1 的排列之一是 s2 的 子串 。 力扣: 力扣
2.问题分析
这一题和上一题大致相似,自己可以来尝试一下,排列其实就是异位
3.代码实现 public boolean checkInclusion(String s1, String s2) {if(s1.length()s2.length())return false;char[] countS1 new char[26];char[] countS2 new char[26];for (int i 0; i s1.length(); i) {countS1[s1.charAt(i) - a];countS2[s2.charAt(i) - a];}if (Arrays.equals(countS1, countS2)) {return true;}for (int i s1.length(); i s2.length(); i) {countS2[s2.charAt(i - s1.length()) - a]--;countS2[s2.charAt(i) - a];if (Arrays.equals(countS1, countS2)) {return true;}}return false;}
四.考试的最大困扰度
1.题目描述 一位老师正在出一场由 n 道判断题构成的考试每道题的答案为 true 用 T 表示或者 false 用 F 表示。老师想增加学生对自己做出答案的不确定性方法是 最大化 有 连续相同 结果的题数。也就是连续出现 true 或者连续出现 false。 给你一个字符串 answerKey 其中 answerKey[i] 是第 i 个问题的正确结果。除此以外还给你一个整数 k 表示你能进行以下操作的最多次数 每次操作中将问题的正确答案改为 T 或者 F 也就是将 answerKey[i] 改为 T 或者 F 。请你返回在不超过 k 次操作的情况下最大 连续 T 或者 F 的数目。 力扣:力扣
2.问题分析
分析了问题可以知道,这一题包含了字符串,连续T或F字符最大的字眼,因此很容易想到需要使用滑动窗口,因为不确定最大连续字符串的长度,所以这一题的窗口长度是不固定的.问题其实可以分为以下两种情况:
第一种情况:使用k次机会将遇到的F变成T,在这种情况下使求得连续T的最大数目.
第二种情况:使用k次机会将遇到的T变成F,在这种情况下使求得连续F的最大数目.
最后只需要求得T和F连续的最大数目两者的最大值即可
分析窗口扩张的情况:(拿求连续T长度最大)因为有k次机会,所以当窗口中F数量小于等于k的时候,这个时候窗口的right向右滑行 分析窗口收缩的情况:当窗口中F的数量大于k的时候,这个时候窗口left进行收缩,直到k的数量小于等于k的时候 满足条件的窗口大小即为一个符合条件的连续T的长度,只需要寻找满足条件的窗口的最大值即可.
3.代码实现 public int maxConsecutiveAnswers(String answerKey, int k) {return Math.max(maxCount(answerKey, k, T), maxCount(answerKey, k, F));}public int maxCount(String answerKey, int k, char c) {int ans 0;for (int left 0, right 0, sum 0; right answerKey.length(); right) {sum answerKey.charAt(right) ! c ? 1 : 0;while (sum k) {sum - answerKey.charAt(left) ! c ? 1 : 0;left;}ans Math.max(ans, right - left 1);}return ans;}
五.替换后的最长重复字符
1.题目描述 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后返回包含相同字母的最长子字符串的长度。 力扣:力扣
2.问题分析
这一题和上一题基本类似,上一题只包含T和F两种字符,这一题一共26中字符(A--Z),所以要比较26次最大值,求出结果.
分析窗口扩张的情况:当窗口中不等于c字符的数量小于等于k次的时候,窗口右端right向右滑行
分析窗口收缩的情况:当窗口中不等于c字符的数量大于k次的时候,窗口左端left向右滑行,直到窗口中c字符的数量小于等于k次.
3.代码实现 public int characterReplacement(String s, int k) {int res 0;HashSetCharacter set new HashSet();for (char c : s.toCharArray()) {set.add(c);}for (Character character : set) {res Math.max(res, countMax(s, k, character));}return res;}public int countMax(String s, int k, char c) {int res 0;for (int left 0, right 0, cnt 0; right s.length(); right) {cnt s.charAt(right) ! c ? 1 : 0;while (cnt k) {cnt - s.charAt(left) ! c ? 1 : 0;left;}res Math.max(res, right - left 1);}return res;}
做完这题可以自己去做下:1004. 最大连续1的个数 III: 力扣 1493. 删掉一个元素以后全为 1 的最长子数组:力扣
六.尽可能使字符串相等
1.题目描述 给你两个长度相同的字符串s 和 t。 将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销开销可能为 0也就是两个字符的 ASCII 码值的差的绝对值。 用于变更字符串的最大预算是 maxCost。在转化字符串时总开销应当小于等于该预算这也意味着字符串的转化可能是不完全的。 如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串则返回可以转化的最大长度。 如果 s 中没有子字符串可以转化成 t 中对应的子字符串则返回 0。 力扣: 力扣
2.问题分析
这一题虽然和上一题不一样,但这一题更加简单,因为很容易想到窗口扩张和收缩的条件
分析窗口扩张的情况:当遍历到i位置的时候,所需要的预算小于等于maxCost的时候,窗口的右端可以继续向右滑行
分析窗口收缩的情况:当遍历到i位置的时候,所需要的预算大于maxCost的时候,窗口的右端不可以继续向右滑行,这个时候窗口左端left收缩,直到小于maxCost
3.代码实现 public int equalSubstring(String s, String t, int maxCost) {int res 0;for (int left 0, right 0, sum 0; right s.length(); right) {sum Math.abs(t.charAt(right) - s.charAt(right));while (sum maxCost) {sum - Math.abs(t.charAt(left) - s.charAt(left));left;}res Math.max(res, right - left 1);}return res;}
七.每种字符至少取 K 个
1.题目描述 给你一个由字符 a、b、c 组成的字符串 s 和一个非负整数 k 。每分钟你可以选择取走 s 最左侧 还是 最右侧 的那个字符。 你必须取走每种字符 至少 k 个返回需要的 最少 分钟数如果无法取到则返回 -1 。 力扣:力扣
2.问题分析
正难则反,我们不妨换一个角度考虑一下问题,问题是我们每次从左端或右端取走字符,最终使取走各k个字符a,b,c,那么我们不妨这样考虑:取走k个字符a,b,c,字符串中还剩下多少个字符a,b,c,求出长度最大的含有这样的子串,最终最小的分钟等于字符串的长度减去这个子串
设子串中要剩余至多cntA个a,cntB个b,cntC个c
分析窗口扩张的情况:当子串(滑动窗口)中所有字母的数量小于等于所需的数量(cntA,cntB,cntC)时候,窗口的right端向右滑行
分析窗口收缩的情况:当子串(滑动窗口)中任一个字母的数量大于所需的数量(cntA,cntB,cntC)时候,窗口的left端向左滑行,直至不符合条件
每次需要收集满足条件的窗口的长度,寻找到最大长度的窗口,最终的答案就是字符串的长度减去滑动窗口长度的最大值
3.代码实现 public int takeCharacters(String s, int k) {int left 0, right 0, length s.length();char[] arr s.toCharArray();int max 0;int[] cnt new int[3];//统计a,b,c的数量for (int i 0; i length; i) {cnt[arr[i] - a];}int cntA cnt[0] - k, cntB cnt[1] - k, cntC cnt[2] - k;//分别为a,b,c可以剩下的最大数量if (cntA 0 cntB 0 cntC 0)//此时要全部取走return length;if (cntA 0 || cntB 0 || cntC 0)//剩下的数量为负的时候,说明a,b,c的数量不足k个return -1;cnt new int[3];//每次循环统计剩下的a,b,c的数量while (right length) {cnt[arr[right] - a];while (cnt[0] cntA || cnt[1] cntB || cnt[2] cntC) {cnt[arr[left] - a]--;left;//当剩下的字符串过长而不满足条件的时候,滑动窗口左端向右移}max Math.max(max, right - left1);right;//窗口的左端向右移}return length - max;}
