jsp系统网站建设带源代码,怎么申请 免费网站空间,全国网页制作大赛,为什么我的网站没有百度索引量文章目录 滑动窗口题目1-无重复字符的最长子串题目2-找到字符串中所有字母异位词 滑动窗口
滑动窗口是一种常用的算法技巧#xff0c;适用于需要在一个数组或字符串中找出满足特定条件的连续子数组或子字符串的问题。它通过维护一个窗口范围来减少重复计算#xff0c;从而优… 文章目录 滑动窗口题目1-无重复字符的最长子串题目2-找到字符串中所有字母异位词 滑动窗口
滑动窗口是一种常用的算法技巧适用于需要在一个数组或字符串中找出满足特定条件的连续子数组或子字符串的问题。它通过维护一个窗口范围来减少重复计算从而优化算法的时间复杂度
滑动窗口算法通常涉及两个指针分别表示窗口的左边界和右边界。窗口在数组或字符串上滑动并在滑动过程中动态调整窗口的大小和位置以满足特定条件。主要步骤如下
初始化窗口边界设置窗口的初始左边界和右边界。移动右边界扩大窗口的右边界直到窗口内的元素满足特定条件。调整左边界当窗口内的元素满足特定条件时尝试移动左边界以缩小窗口同时保持窗口内的元素仍然满足条件。记录结果在每次窗口满足条件时记录当前窗口的大小或内容。重复步骤 2 和 3直到右边界到达数组或字符串的末尾。
题目1-无重复字符的最长子串 第一种【第一次接触可能第一种方法容易理解】
public class Test {public static int lengthOfLongestSubstring(String s) {MapCharacter, Integer map new HashMap();char[] charArray s.toCharArray();int left 0, right 0;int res 0;while (right charArray.length) {if (map.containsKey(charArray[right])) {map.remove(charArray[left]);left;} else {map.put(charArray[right], 1);res Math.max(res, right - left 1);right;}}return res;}public static void main(String[] args) {String s abcabcbb;System.out.println(lengthOfLongestSubstring(s));}
}
第二种可以跳跃式地移动 left 指针
public class Test {public static int lengthOfLongestSubstring(String s) {MapCharacter, Integer map new HashMap();char[] charArray s.toCharArray();int left 0, right 0;int res 0;for (; right s.length(); right) {if (map.containsKey(charArray[right])) {left Math.max(left, map.get(charArray[right]) 1);}map.put(charArray[right], right);res Math.max(res, right - left 1);}return res;}public static void main(String[] args) {String s abcabcbb;System.out.println(lengthOfLongestSubstring(s));}
}题目2-找到字符串中所有字母异位词 第一种方法不建议容易超时 这是我第一想到的方法
public class Test {public static String stringSort(String s) {char[] charArray s.toCharArray();Arrays.sort(charArray);return new String(charArray);}public static ListInteger findAnagrams(String s, String p) {ListInteger res new ArrayList();if (s.length() p.length()) return res;String sortedP stringSort(p);int s_len s.toCharArray().length;int p_len p.toCharArray().length;int left 0, right 0;while (right s_len) {if (right - left 1 p_len) {if (stringSort(s.substring(left, right 1)).equals(sortedP)) {res.add(left);}left;right;} else {right;}}return res;}public static void main(String[] args) {String s cbaebabacd, p abc;System.out.println(findAnagrams(s, p));}
}
第二种方法
public class Test {public static ListInteger findAnagrams(String s, String p) {ListInteger res new ArrayList();if (s.length() p.length()) return res;int p_len p.length();int s_len s.length();int[] pCount new int[26];for (char c : p.toCharArray()) {pCount[c - a];}int[] sCount new int[26];for (int i 0; i s_len; i) {sCount[s.charAt(i) - a];if (i p_len) {sCount[s.charAt(i - p_len) - a]--;}if (check(pCount, sCount)) {res.add(i - p_len 1);}}return res;}private static boolean check(int[] pCount, int[] sCount) {for (int i 0; i 26; i) {if (pCount[i] ! sCount[i]) {return false;}}return true;}public static void main(String[] args) {String s cbaebabacd;String p abc;System.out.println(findAnagrams(s, p));}
}❤觉得有用的可以留个关注~~❤
