公司网站建设设计公司排名,wordpress 文章参数,中国住建部网站查询网,想开广告公司怎么起步前言 挑战一个月刷完力扣的hot100#xff0c;记录一下每题的思路~ 这次是子串相关的题目
#xff08;1#xff09;560. 和为 K 的子数组 ①暴力枚举#xff0c;使用一个变量sum记录以l开头r结尾的情况
class Solution {public int subarraySum(int[] nums, int k) {int r…前言 挑战一个月刷完力扣的hot100记录一下每题的思路~ 这次是子串相关的题目
1560. 和为 K 的子数组 ①暴力枚举使用一个变量sum记录以l开头r结尾的情况
class Solution {public int subarraySum(int[] nums, int k) {int res0;// 枚举每种情况for(int l0;lnums.length;l){int sum0; // l开头for(int rl;rnums.length;r){ // r结尾sumnums[r];if(sumk)res; // 满足条件}}return res;}
} ②前缀和mapmap记录每种前缀和出现的次数。若位置i的前缀和为premap中存在pre-k的前缀和即存在某位置到i的和为k统计次数即可
class Solution {MapInteger,Integer map new HashMap(); // 每种前缀和出现次数public int subarraySum(int[] nums, int k) {int res0, pre0;map.put(0,1);for(int i0;inums.length;i){prenums[i]; // 开头到i的和// map中存在前缀和pre-k即存在某个位置到i的和为kif(map.containsKey(pre-k))resmap.get(pre-k);map.put(pre,map.getOrDefault(pre,0)1); // 更新前缀和pre的次数}return res;}
}
2239. 滑动窗口最大值 ①优先队列记录值和下标按值降序越大越优先每次移除下标越界元素取最大值
class Solution {// 优先队列存值和下标按值降序即越大优先级越高PriorityQueueint[] pq new PriorityQueue((a,b)-Integer.compare(b[0],a[0]));ListInteger res new ArrayList();public int[] maxSlidingWindow(int[] nums, int k) {for(int i0;ik;i)pq.offer(new int[]{nums[i],i});res.add(pq.peek()[0]); // 第一种情况for(int ik;inums.length;i){pq.offer(new int[]{nums[i],i});while(pq.peek()[1]i-k)pq.poll(); // 移除窗口外元素res.add(pq.peek()[0]); // 存最大值}return res.stream().mapToInt(Integer::intValue).toArray(); // 流式转换}
} ②单调递减双端队列。若lr且nums[l]nums[r]在后续的窗口中不可能选到l。每次入队为靠后元素若该元素大于队尾元素队尾不可能再选到直接出队。队列保留目前最大值和其后递减较小值。最大值移出滑动窗口时将其出队
class Solution {ListInteger res new ArrayList();DequeInteger queue new ArrayDeque(); // 单调递减双端队列public int[] maxSlidingWindow(int[] nums, int k) {for(int i0;inums.length;i){// 移除窗口的元素刚好为队头出队if(ikqueue.peekFirst()nums[i-k])queue.pollFirst();// 加入当前元素满足单调递减while(!queue.isEmpty()queue.peekLast()nums[i])queue.pollLast();queue.addLast(nums[i]);// 遍历到k-1时开始取队头即目前最大值if(ik-1)res.add(queue.peekFirst());}return res.stream().mapToInt(Integer::intValue).toArray();}
} ③思路同上一种单调队列记录下标用于队头下标越界判断更好理解
class Solution {ListInteger res new ArrayList();DequeInteger deque new ArrayDeque(); // 单调递减双端队列public int[] maxSlidingWindow(int[] nums, int k) {for(int i0;inums.length;i){// 加入当前元素满足单调递减while(!deque.isEmpty()nums[deque.peekLast()]nums[i])deque.pollLast();deque.addLast(i);// 队头出界移出if(ikdeque.peekFirst()i-k)deque.pollFirst();// 遍历到k-1时开始取队头即目前最大值if(ik-1)res.add(nums[deque.peekFirst()]);}return res.stream().mapToInt(Integer::intValue).toArray();}
} ④分组最大前后缀。k个数一组计算每组最大前后缀。窗口起始值i若为k的整数倍即窗口恰好为一组否则窗口跨越两个分组取前一个分组最大后缀和后一个分组最大前缀的最大值
class Solution {ListInteger res new ArrayList();public int[] maxSlidingWindow(int[] nums, int k) {int n nums.length;int[] prefixMaxnew int[n], suffixMaxnew int[n];for(int i0,jn-1;in;i,j--){// 下标为k整数倍组头if(i%k0)prefixMax[i]nums[i]; else prefixMax[i]Math.max(prefixMax[i-1],nums[i]);// 数组最后一位或下标后一位为k整数倍组尾if(jn-1||(j1)%k0)suffixMax[j]nums[j]; else suffixMax[j]Math.max(suffixMax[j1],nums[j]);}// i为窗口起始位置// i为k整数倍窗口恰为一个分组// 否则窗口跨越两个分组取前一个分组最大后缀和后一个分组最大前缀的最大值for(int i0;in-k;i)res.add(Math.max(suffixMax[i],prefixMax[ik-1]));return res.stream().mapToInt(Integer::intValue).toArray();}
}
376. 最小覆盖子串 滑动窗口。map和count分别记录t和滑动窗口的字符数check判断count不小于map即滑动窗口满足条件。r扩张直到check为true然后收缩l直到不满足记录最短滑动窗口
class Solution {MapCharacter,Integer map new HashMap();MapCharacter,Integer count new HashMap();public String minWindow(String s, String t) {if(s.length()t.length())return ; // 长度不够int l0,r-1,sLens.length(),tLent.length(); // 滑动窗口int resL-1,resR-1; // 结果下标// t中字符计数for(char c:t.toCharArray())map.put(c,map.getOrDefault(c,0)1);// s滑动窗口while(rsLen){r; // 扩张if(rsLenmap.containsKey(s.charAt(r)))count.put(s.charAt(r),count.getOrDefault(s.charAt(r),0)1);while(check()lr){if(resL-1||r-lresR-resL){resLl;resRr;}if(map.containsKey(s.charAt(l)))count.put(s.charAt(l),count.getOrDefault(s.charAt(l),0)-1);l; // 收缩}}return resL-1?:s.substring(resL,resR1);}// count不小于map个数boolean check(){for(Character c:map.keySet()){if(count.getOrDefault(c,0)map.get(c))return false;}return true;}
}
总结 ①子串。双指针暴力枚举map记录每种前缀和出现次数统计pre-k存在次数 ②和为K的子串。优先队列记录值和下标值大优先下标限界单调递减双端队列位于前面且更小的值不会再被选中分组最大前后缀预处理分组的前后缀滑动窗口恰为分组或跨越两个分组 ③滑动窗口最大值。滑动窗口r扩张找到满足的情况l收缩尽可能最短
