沧州市高速公路建设管理局网站,wordpress邮箱验证插件,网站开发与技术,没有公司 接单做网站目录
1.长度最小的子数组
2.无重复字符的最长子串
3.将x减少到0的最小操作数
4.最大连续1的个数Ⅲ
5.找到字符串中所有字母异位词
6.水果成篮
7.串联所有单词的子串
8.最小覆盖子串 1.长度最小的子数组#xff1a;209. 长度最小的子数组 - 力扣#xff08;LeetCode209. 长度最小的子数组 - 力扣LeetCode中等
2.无重复字符的最长子串3. 无重复字符的最长子串 - 力扣LeetCode中等
3.将x减少到0的最小操作数1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode中等
4.最大连续1的个数Ⅲ1004. 最大连续1的个数 III - 力扣LeetCode中等
5.找到字符串中所有字母异位词438. 找到字符串中所有字母异位词 - 力扣LeetCode中等
6.水果成篮904. 水果成篮 - 力扣LeetCode中等
7.串联所有单词的子串30. 串联所有单词的子串 - 力扣LeetCode困难
8.最小覆盖子串76. 最小覆盖子串 - 力扣LeetCode困难 滑动窗口。1.特点具有单调性。2.步骤进窗口、判断窗口、出窗口。然后记录结果在三个步骤其一 1.长度最小的子数组
1链接209. 长度最小的子数组 - 力扣LeetCode中等
题意找到一个最短的子数组连续要求子数组的和目标值。
2思路滑动窗口不断求和当和目标值时则判断结果并出窗口
可以使用滑动窗口的原因是数组元素都是正整数不断向右递增时数组和是递增的
3代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int ret Integer.MAX_VALUE, sum 0;for(int left0,right0;rightnums.length;right) {sum nums[right]; //1.进窗口while(sum target) { //2.判断ret Math.min(right-left1,ret); //3.记录结果sum - nums[left]; //4.出窗口}}return retInteger.MAX_VALUE?0:ret;}
}
2.无重复字符的最长子串
1链接3. 无重复字符的最长子串 - 力扣LeetCode中等
题意找出没有重复字符的最长子数组也就是求最长子数组的长度
2思路也是找子数组所以可以使用滑动窗口。
如何判断是否有重复元素则可以遍历窗口内元素即可
3代码
class Solution {public int lengthOfLongestSubstring(String s) {//如何判断窗口内是否有重复元素从窗口左边开始遍历是否和新进入的窗口值相同//做法始终保持窗口内的元素是不重复的int ret 0;int n s.length();for(int left0,right0;rightn;right) {//1.入窗口--这里默认窗口为[left,right]的元素int cur left;while(cur right) { //2.判断-窗口内是否有重复元素if(s.charAt(cur) s.charAt(right)) {left cur1; //3.出窗口}cur;}ret Math.max(ret,right-left1); //4.记录结果-此时的窗口内保证无重复元素}return ret;}
}
3.将x减少到0的最小操作数
1链接1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode中等
题意每次从最左或者最右选取一个数选取完默认从数组中删除要求和为x且长度最小的。这是正向的意思我们反过来理解在中间选取一段连续区间和为sum-x要求长度最长
2思路连续数组且都是正整数且和为sum-x
3代码
class Solution {public int minOperations(int[] nums, int x) {//题意每次选择最左边或者最右边的数是否可以组合成x。//题意转换数组和为sum是否存在这样一个区间使得和为sum-x的要长度最大int sum 0, n nums.length;for(int i0;in;i) {sum nums[i];}int target sum - x, len -1, path 0;for(int left0,right0;rightn;right) {path nums[right]; //1.入窗口while(left n path target) { //2. 判断//3.出窗口path - nums[left];left;}//4.记录结果if(path target) len Math.max(len,right-left1);}return len-1?-1:n-len;}
}
4.最大连续1的个数Ⅲ
1链接1004. 最大连续1的个数 III - 力扣LeetCode中等
题意找出含有最多1的子数组有k次机会可以将0变成1
2思路连续子数组可以使用滑动窗口。窗口内维护1的个数和将0变成1的次数
出窗口的条件当0的个数大于K次时出窗口
3代码
class Solution {public int longestOnes(int[] nums, int k) {//窗口内维护1和可将0变成1的个数int n nums.length;int ret 0, count0;for(int left0,right0;rightn;right) {if(nums[right] 0) count; //1.入窗口while(count k) { //2.判断//3.出窗口if(nums[left] 0) count--;left;}//4.记录结果ret Math.max(ret,right-left1);}return ret;}
}
5.找到字符串中所有字母异位词
1链接438. 找到字符串中所有字母异位词 - 力扣LeetCode中等
题意给两个字符串要求在s字符串中找出所有和p字符串互为异位词的字符串
2思路(窗口不断向右移动字母的数量是不断增加的)窗口只需要维护p长度的大小即可每次到达该长度就判断一下是否互为异位词判断完记录结果并出窗口。
用两个计数数组判断是否互为异位词
3代码
class Solution {public ListInteger findAnagrams(String s, String p) {//如何判断异位词??int[] pMap new int[26];for(int i0;ip.length();i) {pMap[p.charAt(i)-97];}int[] sMap new int[26];ListInteger ret new ArrayList();for(int left0,right0;rights.length();right) {//1.入窗口sMap[s.charAt(right)-97];//2.判断if(right-left1 p.length()) {//3.判断是否为异位词boolean update true;for(int i0;i26;i) {if(sMap[i] ! pMap[i]) {update false;break;}}//4.记录结果if(update) ret.add(left);//5.出窗口sMap[s.charAt(left)-97]--;}}return ret;}
}
6.水果成篮
1链接904. 水果成篮 - 力扣LeetCode中等
题意给一个数组不同的值代表不同的水果。最多只能采摘两种水果求可以采摘的最多数量是多少
2思路不断向右移动数量增加且是连续子数组。
每次入窗口判断对应的map是否为空为空则为不同的种类。当种类数大于2说明超出需要出窗口最后记录结果即可。
3代码
class Solution {public int totalFruit(int[] fruits) {//如何判断水果的种类和之前的相同或者不同可以用map记录如果0则不同int[] map new int[fruits.length];int ret 0, kind 0;for(int left 0,right 0; right fruits.length; right) {//1.入窗口并判断水果种类是否增加if(map[fruits[right]] 0) {kind;}map[fruits[right]];//2.判断-种类是否超出2种while(kind 2) {//3.出窗口map[fruits[left]]--;if(map[fruits[left-1]] 0) kind--;}//4.记录结果ret Math.max(ret,right-left1);}return ret;}
}
7.串联所有单词的子串
1链接30. 串联所有单词的子串 - 力扣LeetCode困难
题意有一个字符串数组words里面的字符串长度都相同把它们以任何的顺序组成一个字符串单个单词内部顺序不变。然后求该字符串在字符串s中出现的起始位置
2思路把整个单词看成一个字母也就是找这些字母的异位词出现的起始位置
1先用Map存储words中字符串出现的频率
2滑动窗口每次移动len步每次进入窗口的单词为rightlen
3进入窗口后同时记录map中并判断该单词是否为有效单词如果有效则记录count
4如果count达到有效次数则记录结果
5滑动窗口需要执行len次 3代码
class Solution {public ListInteger findSubstring(String s, String[] words) {int n words.length, len words[0].length();MapString,Integer mapW new HashMap(); //记录words里面单词出现的频率for(String x : words) {mapW.put(x,mapW.getOrDefault(x,0)1);}ListInteger ret new ArrayList();for(int k0;klen;k) { //控制滑动窗口执行的次数MapString,Integer mapS new HashMap(); //记录窗口内里面单词出现的频率for(int leftk,rightk,count0;rightlen s.length();rightlen) {//每次进窗口为rightlen, 用count记录窗口内有效字符串的个数//1.进窗口String in s.substring(right,rightlen); //[right,rightlen-1]mapS.put(in,mapS.getOrDefault(in,0)1);//2.维护窗口内有效字符串个数if(mapS.get(in) mapW.getOrDefault(in,0)) count; //如果in字符串在mapW也存在且个数说明是有效字符串//3.判断if(right-left1 len * n) {String out s.substring(left,leftlen);if(mapS.get(out) mapW.getOrDefault(out,0)) count--; //如果out字符串在mapW也存在且个数说明是有效字符串//4.出窗口mapS.put(out,mapS.get(out)-1);left len;}//5.记录结果if(count n) ret.add(left);}}return ret;}
}
*不使用该计数数组使用map如果做
1借助一个变量count统一窗口中有效“字符”的个数。这里的字符可能是单个字母也可能是一个字符串。
2进窗口时判断两个hash中的字符个数如果进窗口的hash个数小于原hash个数 8.最小覆盖子串
1链接76. 最小覆盖子串 - 力扣LeetCode困难
题意在字符串s中找出一个连续的子串要求这个子串包含字符串t。并且要返回这个最短的子串
2思路使用两个哈希表或者计数数组维护有效数字的窗口即可。
只需要记录最短的长度和起始位置。
3代码
使用Map接口
class Solution {public String minWindow(String s, String t) {MapCharacter,Integer mapT new HashMap();for(int i0;it.length();i) {char ch t.charAt(i);mapT.put(ch,mapT.getOrDefault(ch,0)1);}int minLen Integer.MAX_VALUE, begin -1;MapCharacter,Integer mapS new HashMap();for(int left 0,right 0,count 0;right s.length();right) {//1.入窗口char ch s.charAt(right);mapS.put(ch,mapS.getOrDefault(ch,0)1);//2.判断是否有效if(mapS.get(ch) mapT.getOrDefault(ch,0)) count;//3.维护窗口while(left right count t.length()) {//4.记录结果if(count t.length() minLen right - left 1) {begin left;minLen right - left 1;}//5.出窗口char out s.charAt(left);if(mapS.get(out) mapT.getOrDefault(out,0)) count--;mapS.put(out,mapS.get(out)-1);left;} }if(begin -1) return new String();else return s.substring(begin,beginminLen);}
}
使用数组模拟
class Solution {public String minWindow(String ss, String tt) {char[] s ss.toCharArray();char[] t tt.toCharArray();int[] mapT new int[128];//记录第一轮mapint kinds 0;for(int i 0;i t.length;i) {if(mapT[t[i]] 0) kinds;mapT[t[i]];}int[] mapS new int[128];int minlen Integer.MAX_VALUE, begin -1;for(int left0,right0,count0;rights.length;right) {//1.入窗口char in s[right];mapS[in];//2.判断是否为有效种类if(mapS[in] mapT[in]) count;//3.循环while(count kinds) {//4.记录窗口if(right-left1 minlen) {begin left;minlen right-left1;}//5.出窗口char out s[left];if(mapS[out] mapT[out]) count--;mapS[out]--;}}if(begin -1) return new String();else return ss.substring(begin,beginminlen);}
}
