本文主要是介绍Fixed win size sliding window，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这篇记录灵神题单中的定长滑窗环节，不跟之前的Sliding Window一起了。
1. LC 1423 可获得的最大点数
这题其实有点思维的。实现上简单。
每次从首或者尾部拿，总共拿k次。相当于有n-k张牌不拿。因为不可能从中间截断着拿，因此必然这n-k张牌是连续的，所以就变成定长n-k滑窗。更新维护最小值，最终拿总和减掉最小值就是能拿的最大值。
import java.util.HashMap;class Solution {public int maxScore(int[] cardPoints, int k) {int sum = 0;for (int cardPoint : cardPoints) {sum+=cardPoint;}int rest = 0;int n = cardPoints.length;for (int i = 0; i < (n - k); i++) {rest += cardPoints[i];}int min = rest;for(int i=1;i<=k;i++){rest = rest - cardPoints[i-1]+cardPoints[i+n-k-1];min = Math.min(min,rest);}return (sum-min);}
}
2. LC 2134 最少交换次数来组合所有的1Ⅱ
这题是任意位置交换，不是相邻位置。有时间想想相邻交换要怎么做。
统计所有1的个数，统计当前区间（区间长度就是这个个数，因为把所有1聚集起来）的1的个数，差就是交换次数，维护最小值即可。统计区间的1很显然是个滑窗，环形数组取余即可。
import java.util.Arrays;class Solution {public int minSwaps(int[] nums) {int oT = 0;for (int num : nums) {oT += num==1?1:0;}int ans = oT+1;int t = 0;for(int i=0;i<oT;i++){t += nums[i]==1?1:0;}ans = Math.min(ans,oT-t);for(int i=1;i<nums.length;i++){t += (nums[i-1]==1?-1:0) + (nums[(i+oT-1)%nums.length]==1?1:0);ans = Math.min(ans,oT-t);}return ans;}
}
3. LC 2653 滑动子数组的美丽值
这题我写的很丑。
大致思路就是模拟，每个窗口更新维护一个有序哈希表，里面只存放负数的数量，然后从小到大累加各个负数的数量，直到找到第k小。
这种题用数组自己模拟比官方库快多了
import java.util.*;class Solution {public int[] getSubarrayBeauty(int[] nums, int k, int x) {int n = nums.length;int[] ans = new int[n - k + 1];Arrays.fill(ans,0);TreeMap<Integer, Integer> tm = new TreeMap<>();for (int i = 0; i < k; i++) {if(nums[i]<0){mAdd(tm,nums[i]);}}iter(ans,x,tm,0);for(int i=1;i<=n-k;i++){if(nums[i-1]<0){mRemove(tm,nums[i-1]);}if(nums[i+k-1]<0){mAdd(tm,nums[i+k-1]);}iter(ans,x,tm,i);}return ans;}private void iter(int[] ans,int x,Map<Integer,Integer> m,int index){int t = 0;for (Map.Entry<Integer, Integer> next : m.entrySet()) {t += next.getValue();if (t >= x) {ans[index] = next.getKey();return;}}}private void mAdd(Map<Integer,Integer> m,int num){m.put(num,m.getOrDefault(num,0)+1);}private void mRemove(Map<Integer,Integer> m,int num){Integer t = m.get(num);if(null==t){return;}if(1==t){m.remove(num);return;}m.put(num,t-1);}
}
这篇关于Fixed win size sliding window的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
