网站如何做301跳转,东营垦利,律师网站建站,烟台哪个公司做网站好1.最长子串
1.1 无重复字符的最长子串
原题#xff1a;力扣3.
使用 HashMap #xff0c;将字符和最后一次出现的索引存储起来。
public int lengthOfLongestSubstring(String s) {if (s.length() 0) {return 0;}HashMapCharacter, Integer map new HashMap…1.最长子串
1.1 无重复字符的最长子串
原题力扣3.
使用 HashMap 将字符和最后一次出现的索引存储起来。
public int lengthOfLongestSubstring(String s) {if (s.length() 0) {return 0;}HashMapCharacter, Integer map new HashMapCharacter, Integer();int max 0;int left 0;for (int right 0; right s.length(); right) {if (map.containsKey(s.charAt(right))) {left Math.max(left, map.get(s.charAt(right)) 1);}map.put(s.charAt(right), right);max Math.max(max, right - left 1);}return max;
}1.2 至多包含两个不同字符的最长子串
原题力扣159.
public int lengthOfLongestSubstringTwoDistinct(String s) {if (s.length() 3) {return s.length();}int left 0, right 0;HashMapCharacter, Integer hashmap new HashMap();int maxLen 2;while (right s.length()) {if (hashmap.size() 3) {hashmap.put(s.charAt(right), right);}if (hashmap.size() 3) {int del_index Collections.min(hashmap.values());hashmap.remove(s.charAt(del_index));left del_index 1;}maxLen Math.max(maxLen, right - left);}return maxLen;
}*1.3 至多包含 K 个不同字符的最长子串
原题力扣340.
public int lengthOfLongestSubstringDistinct(String s, int k) {if (s.length() k 1) {return s.length();}int left 0, right 0;HashMapCharacter, Integer hashmap new HashMap();int maxLen k;while (right s.length()) {if (hashmap.size() k 1) {hashmap.put(s.charAt(right), right);}if (hashmap.size() k 1) {int del_index Collections.min(hashmap.values());hashmap.remove(s.charAt(del_index);left del_index 1;}maxLen Math.max(maxLen, right - left);}return maxLen;
}2.长度最小的子数组
原题力扣209.
public int minSubArrayLen(int target, int[] nums) {int left 0, right 0, sum 0, min Integer.MAX_VALUE;while (right nums.length) {sum nums[right];while (sum target) {min Math.min(min, right - left);sum - nums[left];}}return min Integer.MAX_VALUE ? 0 : min;
}3.盛水最多的容器
原题力扣11.
双指针向中间移动直到碰撞。
public int maxArea(int[] height) {int i 0, j height.length - 1, res 0;while (i j) {res height[i] height[j] ?Math.max(res, (j - i) * height[i]) :Math.max(res, (j - i) * height[j--]);}return res;
}4.寻找子串异位词子串排列
如果两个字符串仅仅是字母出现的位置不一样则两者互为对方的一个排列也叫做异位词。
4.1 字符串的排列
原题力扣567.
这道题要求判断 s2 是否包含 s1 的排列。
public boolean checkInclusion(String s1, String s2) {int len1 s1.length(), len2 s2.length();if (len1 len2) {return false;}// 统计每种字符出现次数int[] charArray1 new int[26];int[] charArray2 new int[26];// 先读第一段// 滑动窗口长度固定为 len1for (int i 0; i len1; i) {// 哪个字符出现了数组中对应的位置就加 1charArray1[s1.charAt(i) - a];charArray2[s2.charAt(i) - a];}// 比较第一段数组中字符是否数目相同if (Arrays.equals(charArray1, charArray2)) {return true;}// 开始移动窗口for (int right len1; right len2; right) {// charArray1 已经存好了不需要再变动charArray2[s2.charAt(right) - a];int left right - len1;charArray2[s2.charAt(left) - a]--;if (Arrays.equals(charArray1, charArray2)) {return true;}}return false;
}4.2 找到字符串中所有字母异位
原题力扣438.
要求将所有符合条件的排列的起始索引返回。
public ListInteger findAnagrams(String s, String p) {ListInteger res new ArrayList();if (s.length() p.length()) {return res;}// 还是用滑动窗口做但是这次记录起始索引int left 0;int[] charArray1 new int[26];int[] charArray2 new int[26];for (int i 0; i p.length(); i) {charArray1[s.charAt(i) - a];charArray2[p.charAt(i) - a];}if (Arrays.equals(charArray1, charArray2)) {res.add(left);}for (int right p.length(); right s.length(); right) {charArray1[s.charAt(right) - a];charArray1[s.charAt(left) - a]--;left;if (Arrays.equals(charArray1, charArray2)) {res.add(left);}}return res;
}如果对您有帮助请点赞关注支持我谢谢❤ 如有错误或者不足之处敬请指正❤ 个人主页星不易 ❤ 算法通关村专栏不易|算法通关村 ❤
