做外贸网站选择服务器,qq登录插件wordpress,东莞证券,php mysql网站开发工资一、背景知识 滑动窗口算法#xff08;Sliding Window#xff09;#xff1a; 在给定数组 / 字符串上维护一个固定长度或不定长度的窗口。可以对窗口进行滑动操作、缩放操作#xff0c;以及维护最优解操作。题型一#xff1a;固定长度题型二#xff1a;不固定长度 二、例…一、背景知识 滑动窗口算法Sliding Window 在给定数组 / 字符串上维护一个固定长度或不定长度的窗口。可以对窗口进行滑动操作、缩放操作以及维护最优解操作。题型一固定长度题型二不固定长度 二、例题
1、无重复字符的最长子串不定长度 写法一 我的答案
class Solution {public int lengthOfLongestSubstring(String s) {if(s.length()0){return 0;}int l0;//左指针int r0;//右指针int maxLen1;ListCharacter listnew ArrayList();while(rs.length() ls.length()){if(!list.contains(s.charAt(r))){list.add(s.charAt(r));//窗口右侧扩张maxLenMath.max(maxLen,r-l1);//维护一个子串长度的最大值r;}else{int indexlist.indexOf(s.charAt(r));//在窗口里查找被重复的字符的下标delItems(index,list);//把重复字符及其以前的字符移出窗口llindex1;//窗口左侧收缩}}return maxLen;}//public void delItems(int end,List list){while(end0){//从后往前删list.remove(end);end--;}}
} 写法二 官方答案 外循环for枚举字符串s的所有字符当作滑动窗口的左边界进入内循环while后不断往右移直到遇到重复的字符后跳出内循环。 更新最长子串长度删除滑动窗口最左边的一个元素。 如果该元素不是被重复的元素就不会再次进入内循环而是一直在外循环徘徊一个接一个地删掉滑动窗口最左边的元素直到删掉那个被重复的元素 class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合记录每个字符是否出现过相当于滑动窗口SetCharacter occ new HashSetCharacter();int n s.length();// 右指针初始值为 -1相当于我们在字符串的左边界的左侧还没有开始移动int rk -1, ans 0;for (int i 0; i n; i) {if (i ! 0) {// 左指针向右移动一格哈希集合移除一个字符occ.remove(s.charAt(i - 1));}while (rk 1 n !occ.contains(s.charAt(rk 1))) {// 不断地移动右指针哈希集合增加一个字符 occ.add(s.charAt(rk 1));rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串// rk-i1为当前滑动窗口内的子串长度ans Math.max(ans, rk - i 1);}return ans;}
}2、找到字符串中所有字母异位词 该题用排序法会超时用链表或哈希表会超出内存限制 写法一 突破点 在字符串 s中构造一个长度为与字符串 p的长度相同的滑动窗口并在滑动中维护窗口中每种字母的数量当窗口中每种字母的数量与字符串 p中每种字母的数量相同时则说明当前窗口为字符串 p的异位词。 class Solution {public ListInteger findAnagrams(String s, String p) {int sLen s.length(), pLen p.length();//当字符串 s 的长度小于字符串 p 的长度时字符串 s 中一定不存在字符串 p 的异位词if (sLen pLen) {return new ArrayListInteger();}ListInteger ans new ArrayListInteger();int[] sCount new int[26];//计算字符串s中26个字母出现的个数int[] pCount new int[26];//计算字符串p中26个字母出现的个数for (int i 0; i pLen; i) {sCount[s.charAt(i) - a];pCount[p.charAt(i) - a];}if (Arrays.equals(sCount, pCount)) {//两个数组相等找到异位词ans.add(0);//记录初始下标}//窗口开始滑动for (int i 0; i sLen - pLen; i) {//用滑动窗口遍历字符串s--sCount[s.charAt(i) - a];//滑动窗口左边界收缩sCount数组里该字母的个数减1sCount[s.charAt(i pLen) - a];//滑动窗口右边界扩张sCount数组里该字母的个数加1if (Arrays.equals(sCount, pCount)) {//找到异位词ans.add(i 1);}}return ans;}
}
