如何做网站 知乎,苏州网站建设公司排名,海南房产,黄石网站建设文章目录 滑动窗口最长无重复子串最小覆盖子串串联所有单词的子串长度最小的子数组滑动窗口最大值字符串的排列最小区间 滑动窗口
所有题目来自leetcode的回答#xff1a;https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-d… 文章目录 滑动窗口最长无重复子串最小覆盖子串串联所有单词的子串长度最小的子数组滑动窗口最大值字符串的排列最小区间 滑动窗口
所有题目来自leetcode的回答https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-dong-chuang-kou-by-powcai
会员题没有列出来。
最长无重复子串
题目https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
class Solution {public int lengthOfLongestSubstring(String s) {int n s.length();if (n 0) return 0;MapCharacter, Integer map new HashMap();int res 0, left 0;for (int i 0; i n; i ) {if (map.containsKey(s.charAt(i))) {left Math.max(left, map.get(s.charAt(i)) 1);}map.put(s.charAt(i), i);res Math.max(res, i - left 1);}return res;}
}最小覆盖子串
题目https://leetcode.cn/problems/minimum-window-substring/description/
class Solution {MapCharacter, Integer cnts new HashMap();MapCharacter, Integer cntt new HashMap();public String minWindow(String s, String t) {int ls s.length(), lt t.length();int milen Integer.MAX_VALUE, st 0, ed 0, mist 0, mied 0;boolean isNull false;for (int i 0 ; i lt; i ) {cntt.put(t.charAt(i), cntt.getOrDefault(t.charAt(i), 0) 1);}while (ed ls) {if (cntt.containsKey(s.charAt(ed))) {cnts.put(s.charAt(ed), cnts.getOrDefault(s.charAt(ed), 0) 1);while (check()) { // 这里是while一步更新到第二个在cntt里的字符过滤掉无用字符isNull true;if (milen ed - st 1) {milen ed - st 1;mist st;mied ed;}if (cntt.containsKey(s.charAt(st))) {cnts.put(s.charAt(st), cnts.getOrDefault(s.charAt(st), 0) - 1);}st ;}}ed ;}if (!isNull) return ;return s.substring(mist, mied 1);}private boolean check() {Iterator iter cntt.entrySet().iterator();while (iter.hasNext()) {Map.Entry entry (Map.Entry) iter.next();Character key (Character) entry.getKey();Integer val (Integer) entry.getValue();if (cnts.getOrDefault(key, 0) val) return false;}return true;}
}串联所有单词的子串
题目https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/
题解https://leetcode.cn/problems/substring-with-concatenation-of-all-words/solutions/3825/chuan-lian-suo-you-dan-ci-de-zi-chuan-by-powcai
// 对words中的所有单词维护一个单词计数map
// 串联子串中保证了每个子单词的原字符顺序不变
class Solution {public ListInteger findSubstring(String s, String[] words) {int ls s.length(), n words.length;int lw n * words[0].length(), oneLen words[0].length();ListInteger res new ArrayList();if (lw ls) return res;MapString, Integer wordsMap new HashMap();for (int i 0; i n; i ) {wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) 1);}for (int i 0; i ls - lw 1; i ) { // i ls - lw 1保证能枚举到最后一个窗口的第一个下标位置MapString, Integer tmpMap new HashMap();for (int j i; j i lw; j oneLen) {String subStr s.substring(j, j oneLen);tmpMap.put(subStr, tmpMap.getOrDefault(subStr, 0) 1);}if (wordsMap.equals(tmpMap)) res.add(i);}return res; }
}优化常规的滑动窗口思路和最小覆盖子串的代码逻辑相似
class Solution {public ListInteger findSubstring(String s, String[] words) {int ls s.length(), n words.length;int lw n * words[0].length(), oneLen words[0].length();ListInteger res new ArrayList();if (lw ls) return res;MapString, Integer wordsMap new HashMap();for (int i 0; i n; i ) {wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) 1);}for (int i 0; i oneLen; i ) { // 保证枚举到所有单词[0...oneLen], [1...oneLen 1], ...int st i, ed i, cnt 0;MapString, Integer tmpMap new HashMap();while (ed ls - oneLen 1) { // 同解法一的判断String subStr s.substring(ed, ed oneLen);tmpMap.put(subStr, tmpMap.getOrDefault(subStr, 0) 1);ed oneLen;cnt ; // 当前窗口里有几个单词while(tmpMap.getOrDefault(subStr, 0) wordsMap.getOrDefault(subStr, 0)) {// 窗口里的单词并不在wordsMap里移动窗口// 或者窗口里当前单词重复出现了移动窗口String stStr s.substring(st, st oneLen); // 窗口里最左边的单词tmpMap.put(stStr, tmpMap.getOrDefault(stStr, 0) - 1);st oneLen;cnt --;}if (cnt n) res.add(st);}}return res;}
}再优化直接跳过不在words里的单词和窗口
class Solution {public ListInteger findSubstring(String s, String[] words) {int ls s.length(), n words.length;int lw n * words[0].length(), oneLen words[0].length();ListInteger res new ArrayList();if (lw ls) return res;MapString, Integer wordsMap new HashMap();for (int i 0; i n; i ) {wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) 1);}for (int i 0; i oneLen; i ) { // 保证枚举到所有单词[0...oneLen], [1...oneLen 1], ...int st i, ed i, cnt 0;MapString, Integer tmpMap new HashMap();while (ed ls - oneLen 1) { // 同解法一的判断String subStr s.substring(ed, ed oneLen);ed oneLen;if (!wordsMap.containsKey(subStr)) {/**当前窗口的当前单词不是words里的单词肯定不符合题意更新窗口。题中要求所有串联单词必须挨在一起这个判断过滤掉不挨在一起的窗口*/cnt 0;st ed;tmpMap.clear();continue;}tmpMap.put(subStr, tmpMap.getOrDefault(subStr, 0) 1);cnt ; // 当前窗口里有几个单词while(tmpMap.getOrDefault(subStr, 0) wordsMap.getOrDefault(subStr, 0)) {// 窗口里的单词并不在wordsMap里移动窗口// 或者窗口里当前单词重复出现了移动窗口String stStr s.substring(st, st oneLen); // 窗口里最左边的单词tmpMap.put(stStr, tmpMap.getOrDefault(stStr, 0) - 1);st oneLen;cnt --;}if (cnt n) res.add(st);}}return res;}
}长度最小的子数组
题目https://leetcode.cn/problems/minimum-size-subarray-sum/description/
class Solution {public int minSubArrayLen(int target, int[] nums) {int n nums.length;int milen Integer.MAX_VALUE, st 0, ed 0, sum 0;boolean isNull false;while (ed n) {sum nums[ed];while (sum target) {isNull true;if (milen ed - st 1) {milen ed - st 1;}sum - nums[st];st ;}ed ;}if (!isNull) return 0;return milen;}
}滑动窗口最大值
题目https://leetcode.cn/problems/sliding-window-maximum/description/
题解https://leetcode.cn/problems/sliding-window-maximum/solutions/2361228/239-hua-dong-chuang-kou-zui-da-zhi-dan-d-u6h0
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 借鉴最小栈的思路再O(1)时间内找出窗口内的最大值// 双向队列维持一个窗口内的非严格递减排序// 队头是窗口内的最大值int n nums.length;if (k 1) return nums;int[] res new int[n - k 1];DequeInteger dq new LinkedList();int idx 0;for (int i 0; i k; i ) {while (!dq.isEmpty() dq.peekLast() nums[i]) {dq.removeLast();}dq.addLast(nums[i]);}res[idx ] dq.peekFirst();for (int i k; i n; i ) {if (dq.peekFirst() nums[i - k]) dq.removeFirst();while (!dq.isEmpty() dq.peekLast() nums[i]) {dq.removeLast();}dq.addLast(nums[i]);res[idx ] dq.peekFirst();}return res;}
}字符串的排列
题目https://leetcode.cn/problems/permutation-in-string/description/
题解-方法二https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/solutions/355881/zui-xiao-qu-jian-by-leetcode-solution
class Solution {public boolean checkInclusion(String s1, String s2) {int ls1 s1.length(), ls2 s2.length();if (ls1 ls2) return false;int[] cnt1 new int[26], cnt2 new int[26];for (int i 0; i ls1; i ) {cnt1[s1.charAt(i) - a] ;cnt2[s2.charAt(i) - a] ;}if (Arrays.equals(cnt1, cnt2)) return true;for (int i ls1; i ls2; i ) {cnt2[s2.charAt(i - ls1) - a] --;cnt2[s2.charAt(i) - a] ;if (Arrays.equals(cnt1, cnt2)) return true;}return false;}
}最小区间
题目https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/description/
class Solution {public int[] smallestRange(ListListInteger nums) {int n nums.size();MapInteger, ListInteger index new HashMap();int mi Integer.MAX_VALUE, mx Integer.MIN_VALUE;for (int i 0; i n; i ) {for (int item : nums.get(i)) {ListInteger tmp index.getOrDefault(item, new ArrayListInteger());tmp.add(i);index.put(item, tmp);if (mi item) mi item;if (mx item) mx item;}}int st mi, ed mi - 1, ansSt 0, ansEd Integer.MAX_VALUE, cnt 0;// System.out.println(mi , mx);int[] interval new int[n]; // 记录滑动窗口覆盖了多少区间,下标标识某个区间while (ed mx) {ed ;if (index.containsKey(ed)) {for (int idx : index.get(ed)) { // 枚举被覆盖的区间interval[idx] ;if (interval[idx] 1) { // idx标识的区间第一次被覆盖时标记该区间被覆盖cnt ;}while (cnt n) { // 当所有区间被覆盖更新最小区间和窗口if (ed - st ansEd - ansSt) {// System.out.println(*--*-*-);ansSt st;ansEd ed;}if (index.containsKey(st)) { // 更新最小区间的左端点看是否能覆盖全部区间for (int leftIdx : index.get(st)) {interval[leftIdx] --;if (interval[leftIdx] 0) {cnt --;}}}st ;}}}}return new int[] {ansSt, ansEd};}
}
