LeetCode滑动窗口
LeetCode 滑动窗口
滑动问题包含一个滑动窗口，它是一个运行在一个大数组上的子列表，该数组是一个底层元素集合。假设有数组 [a b c d e f g h ]，一个大小为 3 的 滑动窗口 在其上滑动，则有：
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动，同时 动态地记录一些有用的数据，很多情况下，能够极大地提高算法地效率。
239. 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
返回滑动窗口最大值。
示例：
输入：nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
注意：
你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。
进阶：
你能在线性时间复杂度内解决此题吗？
解法一
public static int[] maxSlidingWindow2(int[] nums, int k) {
//题目上说的不为空，还是给我来了个空。
if(nums.length==0){
return new int[]{};
}
if(k==1) return nums;
LinkedList<Integer> list=new LinkedList<Integer>();
int []res=new int[nums.length-k+1];
int index=0;
list.add(0);
for (int i=1;i<nums.length;i++) {
while(!list.isEmpty() && nums[list.getLast()]<nums[i]){
//小于 nums[i] 的元素，从右边（尾）出队列 , 控制最左边（头）最大
list.removeLast();
}
//然后将它加到队列中，从右边（尾）
list.addLast(i);
//如果队列溢出了就从右边移除一个（头）
if(i-list.getFirst()==k){
list.removeFirst();
}
if(i>=k-1){
res[index++]=nums[list.getFirst()];
}
}
return res;
}
2020.2.9 回头看了下，这不是单调队列么😂（用堆也可以啦，不过既然要在头尾都操作，直接用队列会更方便）
其实开始我也不会做，看了提示后搞了半天才弄出来，23ms，70%左右，思路就是利用一个双端队列（头尾都可以进出），队列中存数组下标，然后遍历数组，在进入队列时从右向左遍历队尾，将小于当前元素的队尾元素去除（因为已经没用了，后面的最大值不可能是它们），举个例子
[2，1，-1，3，……] k=3 ，当读到** 3 **这个元素的时候，窗口再向右移动最大值肯定不会是右边的元素了，所以直接剔除他们，在纸上画一画就明白了
然后很关键的一步就是什么时候移除最左边的元素，其实按照人的思路来想就是最左边的元素不在窗口内的时候，比如上面的例子，读到** 3 **的时候，**2 **其实就应该剔除了因为它已经不在窗口内了。用代码来描述就是
i-list.getFirst()==k，i 代表当前元素下标，上面的例子** 3 对应的 i 就是 3**，list.getFirst()=0，刚好差为 k，就代表** 2 **已经超出窗口了应该移除了。
其实这里我开始不是这样做的，我在队列里面存的不是元素索引，我存的是元素，然后在判断什么时候移除的时候发现判断不了，**index **也只是结果元素的下标，并不能代表队列最左元素的下标，对于数组存下标优先于存元素，多一个已知量有时候还是很方便的
解法二
属于对暴力法的优化吧，最坏情况下时间复杂度O(NK)，比如完全逆序的情况（2020.2.9 回顾 fix）
public static int[] maxSlidingWindow3(int[] nums, int k) {
//题目上说的不为空，还是给我来了个空。
int len = nums.length;
if (len == 0) return new int[]{};
if (len == 1) return new int[]{nums[0]};
int localMax = Integer.MIN_VALUE;
int[] result = new int[len - k + 1];
for (int i = 0; i < k; i++) {
//找到第一个窗口的最大值
localMax = max(nums[i], localMax);
}
result[0] = localMax;
for (int i = 1; i < len - k + 1; i++) {
//窗口的下一个元素 k=3 , i=1 下一个元素下标为 3
if (nums[i + k - 1] > localMax) {
//判断当前窗口最大值和下一个元素的大小
//如果比当前窗口的最大值还要大 就不用找了 就是它了
localMax = nums[i + k - 1];
} else if (nums[i - 1] == localMax) {
//下一个元素比当前窗口最大值小 而且很不巧
//当前最大值刚好是当前窗口的最左边的元素，也就是马上要超过窗口的元素
localMax = nums[i];
//所以就要重新找最大值
for (int x = i; x < i + k; x++) {
localMax = max(nums[x], localMax);
}
}
//剩下的请况就是 比当前最大值小，并且最大值不是最左边的元素（还没有出界），最大值不变
//copy 到结果中
result[i] = localMax;
}
return result;
}
//其实可以用 Math.max()
public static int max(int a,int b){
if(a>=b)return a;
return b;
}
2ms，99% 提交记录这种做法是最快的😂，时间复杂度最坏应该是O(NK)
5312. 大小为 K 且平均值大于等于阈值的子数组数目
给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
示例 1：
输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值）。
示例 2：
输入：arr = [1,1,1,1,1], k = 1, threshold = 0
输出：5
示例 3：
输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6
解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。
示例 4：
输入：arr = [7,7,7,7,7,7,7], k = 7, threshold = 7
输出：1
示例 5：
输入：arr = [4,4,4,4], k = 4, threshold = 1
输出：1
提示：
1 <= arr.length <= 10^51 <= arr[i] <= 10^41 <= k <= arr.length0 <= threshold <= 10^4
解法一
19 双周赛的第 2 题，很简单的滑动窗口，枚举所有窗口计数就行了
public int numOfSubarrays(int[] arr, int k, int threshold) {
threshold*=k;
int sum=0;
int count=0;
for (int i=0;i<k;i++) {
sum+=arr[i];
}
for (int i=k;i<arr.length;i++) {
if (sum>=threshold) {
count++;
}
//0 1 2 3
sum+=arr[i];
sum-=arr[i-k];
}
return count;
}
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入："abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入："bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入："pwwkew"
输出：3
解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解法一
这题其实很久以前（半年前）做过一次，当时用的方法很 low😂
public int lengthOfLongestSubstring(String s) {
char [] chars = s.toCharArray();
if (chars.length == 0) {
return 0;
}
int length = 1;
String temp=new String();
for (int i = 0; i <s.length()-1; i++) {
if(chars[i] != chars[i+1]) {
temp=s.substring(i, i+2);
} else continue;
for (int j = i+2; j < s.length(); j++) {
if (!temp.contains(chars[j]+"")) {
temp = s.substring(i, j+1);
} else break;
}
//Break 出来后判断是否是最长的 k
length=temp.length()>length?temp.length():length;
}
return length;
}
我这种完全就是利用 api 暴力法，居然还跑过了，时间复杂度应该是 O(N3)，这题的 ac 率还是挺低的只有 29.3%
解法二
下面的是我下午重新做的
public static int lengthOfLongestSubstring4(String s) {
//边界问题永远不能忽略
//LinkedList<Integer> list=new LinkedList<>();
int length=s.length();
if(length==0) return 0;
int head=0,tail=0;
int max=1;
for (int i=1;i<length;i++) {
int index=i-1; //当前元素前一个元素下标
while(index>=head){
if(s.charAt(i)!=s.charAt(index)){
index--;
}else{
//按思路应该是把相等前所有元素移除，但是那样效率好低，所以这里我决定用数组模拟队列
head=index+1;
tail++;
break;
}
//从尾遍历到头仍然没有相等，可以添加到队列中
if(index==head-1){
tail++;
break;
}
}
//每次结束循环后 尾 index-头 index
max=tail-head+1 > max?tail-head+1:max;
//System.out.println(max);
}
return max;
}
20ms 左右 80%左右，思路也比较清晰，遍历字符串，然后从后往前遍历字符串，判断当前字符串在前面有没有，有的话就将前面相等那个元素 (index) 前的元素都移除（窗口右移）
eg: [head...index....tail] i 向右移动....index [head ... i]
把当前元素添加进来，时间复杂度是 O(N^2)，比上面单纯的暴力法要快多了，但是并不是最优解
解法三
上面的算法，其实还可以优化，每次判断前面有没有重复元素的时候可以直接用一个大小 256 的扩展 ASCII 码表数组来判断（前提是这些字符都在标准的 ASCII 字符中），freq[s.charAt(i)] 代表的就是 s.charAt(i) 这个字符在窗口内出现过没有，出现过就为 1，否则就是 0，这里如果 ASCII 不够其实也可以用 HashMap，查找效率也很高接近 O(1)
public int lengthOfLongestSubstring(String s) {
int length=s.length();
if(length==0) return 0;
int[] freq=new int[256]; //ASCII 码表
freq[s.charAt(0)]=1;
int head=0,tail=0;
int max=1;
while(head<length){
if(tail+1<length&&freq[s.charAt(tail+1)]==0){
//没有重复，右边界右移
tail++;
freq[s.charAt(tail)]++;
}else{
//逐渐缩减左边界，直到不再有重复元素
freq[s.charAt(head)]--;
head++;
}
max=max<tail-head+1?tail-head+1:max;
}
return max;
}
这种做法最坏情况（没有重复的字符）下其实会遍历两遍数组 tail 先移动到尾部 head 随后有移动到尾部，但是比较好理解，解法四实际上就是对这里的优化，head 每次移动都是直接移动到上一个重复元素的位置，而不是一个一个的向右移
解法四
提交记录上最快的方法，理解起来有点费劲，现在回头看又看不懂了。
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
//索引为元素值，这里因为元素都是字符转过来就是 askll 码，所以可以直接这样
int[] index = new int[128];
for (int j = 0, i = 0; j < n; j++) {
//如果字符 char 在没有出现过，index[char] 为 0，出现则 index[char] 是遍历出现的最后的 char 的位置
// index[s.charAt(j)] 是当前字符上一次出现的位置（从 1 开始）
i = Math.max(i,index[s.charAt(j)]);
//j - i + 1 就是舍弃 s.charAt(j) 重复出现之前字符的长度 如 abca, 当 s.charAt(j) == a 时，j - i + 1 就是 bca 的长度
//求最大值常规操作
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
// 从 1 开始
}
return ans;
}
这里最主要就是这个** i **的理解
这个 i 不一定是当前元素上一次出现的位置，也有可能是离当前元素从右向左最近的重复字符的_位置_。而 index 中存的就是这个元素的索引位置+1，为什么要加 1？
主要是因为 i 的默认值是 0 而数组默认值也是 0，如果以 0 开始就会出现上面的情况。
其实这两种算法也比较类似，只是后面判断字符是否出现过的方式不同，前者是直接遍历这个子串，后者是利用字符为索引，其值就是上一次出现的位置 (+1)，借此来计算长度。
回首掏
19/9/14，在网页上又写了一种不同的解法，属于解法 4 的变体（做的时候并没有想到解法 4），freq[] 数组索引是字符串，但是值是该字符在 s 中对应的索引，不会遍历两遍数组，left 可以通过索引直接跳到上一次出现的位置
public static int lengthOfLongestSubstring6(String s) {
if(s==null||s.length()<1) return 0;
if(s.length()==1) return 1;
int[] freq=new int[256];
int left=0,right=0,res=0;
Arrays.fill(freq,-1);
while(right<s.length()){
char sr=s.charAt(right);
//已经存在，并且在窗口内
if(freq[sr]!=-1 && freq[sr]>=left){
//System.out.println(left+","+right+","+freq[sr]);
res=Math.max(res,right-left);
left=freq[sr]+1;
freq[sr]=right;
}else{
res=Math.max(res,right-left+1);
freq[sr]=right;
}
right++;
}
return res;
}
回首掏 2
public static int lengthOfLongestSubstring7(String s) {
if(s==null||s.length()<1) return 0;
if(s.length()==1) return 1;
int[] freq=new int[256];
int left=0,right=0,res=0;
//Arrays.fill(freq,-1);
while(right<s.length()){
char sr=s.charAt(right);
//已经存在（出现过）, 并且上一次出现在窗口内
if(freq[sr]!=0 && freq[sr]>=left){
//这里不包含 right, 所以不用加 1
res=Math.max(res,right-left);
//left 移动到重复位置元素的下一个
//因为 freq 的值是存的索引+1 所以这里不用+1
left=freq[sr];
}else{
//这里包含 right 所以需要加 1
res=Math.max(res,right-left+1);
}
//加 1 是为了区别 s 的第一个字符
freq[sr]=right+1;
right++;
}
return res;
}
感觉对这题有很深的执念😅，对上面右优化了一下，但是其实还是上面的解法三比较简单，说到解法三，我又抽风改了一个 boolean 数组版本的
//update: 2020.4.13 重写了一遍，代码更简洁了
public int lengthOfLongestSubstring(String s) {
if(s==null ||s.length()<=0) return 0;
boolean[] freq=new boolean[128];
int left=0,right=0;
int max=0;
while(left<=right && right<s.length()){
if(!freq[s.charAt(right)]){
max=Math.max(max,right-left+1);
freq[s.charAt(right++)]=true;
}else{
freq[s.charAt(left++)]=false;
}
}
return max;
}
以上解法全部作废
统一使用for-while结构，能用for-if的一定可以用for-while，反过来就不行
//2020.5.5 根据自己总结的滑窗模板重写
public int lengthOfLongestSubstring(String s) {
if(s==null || s.length()<=0) {
return 0;
}
int n=s.length();
int left=0;
int res=1;
boolean[] freq=new boolean[128];
for(int right=0;right<n;right++){
while(freq[s.charAt(right)]){
freq[s.charAt(left++)]=false; //left 不用限制
}
freq[s.charAt(right)]=true;
res=Math.max(res,right-left+1);
}
return res;
}
最优解
map 记录元素最后出现的位置，当重复的时候更新起点，只用遍历一遍
func lengthOfLongestSubstring(s string) int {
if len(s)==0{
return 0
}
m:=make(map[rune]int)
start:=0
res:=0
for i,ch:=range s{
if idx,ok:=m[ch];ok && idx+1>start{
start=idx+1
}
m[ch]=i
res=Max(res,i-start+1)
}
return res
}
func Max(a,b int) int{
if a>b{
return a
}
return b
}
219. 存在重复元素 II
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大（不超过）为 k。
示例 1:
输入：nums = [1,2,3,1], k = 3
输出：true
示例 2:
输入：nums = [1,0,1,1], k = 1
输出：true
示例 3:
输入：nums = [1,2,3,1,2,3], k = 2
输出：false
解法一
这题建议区看看原版的英文题，这里翻译过来有点误导人，应该是不超过 k，写个最大搞得我有点懵
public static Boolean containsNearbyDuplicate2(int[] nums, int k) {
int len=nums.length;
//if(k==35000) return false; 哈哈哈哈
if(len==0||k==0)return false;
for (int i=1;i<len;i++) {
int index=i-1;
while(i-index<=k){
//k 步之内
if(index<0){
break;
}
if(nums[i]==nums[index--]){
return true;
}
}
}
return false;
}
暴力法，惨不忍睹，600ms，15%beats 。这题最好的做法还是借助 hash 表
解法二
public static Boolean containsNearbyDuplicate3(int[] nums, int k) {
HashMap<Integer,Integer> map=new HashMap<>();
int len=nums.length;
if(len==0||k==0) return false;
for (int i=0;i<len;i++) {
if(map.containsKey(nums[i])){
int index=map.get(nums[i]);
if(i-index<=k) {
return true;
} else {
//大于 k 了那前面那个没用了
map.replace(nums[i],i);
}
} else {
map.put(nums[i],i);
}
}
return false;
}
12ms，90%，其实效率的差距就在查找子串里有没有这个字符上，HashMap 的 containsKey 的效率比我们遍历的不知道高到那里去了，底层源码暂时还看不太懂，以后看的时候再专门来讲
19.9.14 又做了一遍，直接在网页上写的，本来应该是 bugfree 的，结果减反了。
public static boolean containsNearbyDuplicate4(int[] nums, int k) {
HashMap<Integer,Integer> hashMap=new HashMap<>();
int left=0,right=0;
while(right<nums.length){
if(hashMap.containsKey(nums[right])){
//md, 重新做的时候这里减反了真是个 zz
if(right-hashMap.get(nums[right])<=k){
return true;
} else{
hashMap.put(nums[right],right);
}
}else{
hashMap.put(nums[right],right);
}
right++;
}
return false;
}
19.9.15 又做了一遍，这次代码写的很简洁，思路也不同了，直接利用 set 集合，维护一个大小为 k 的连续 set（窗口）
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> set=new HashSet<>();
for (int i=0;i<nums.length;i++) {
if (!set.add(nums[i])) {
return true;
}
if (set.size()>k) {
set.remove(nums[i-k]);
}
}
return false;
}
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 **s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。**如果不存在符合条件的连续子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶：
如果你已经完成了* O*(n) 时间复杂度的解法，请尝试 O(n log n) 时间复杂度的解法。
解法一
老规矩先上个慢的
public static int minSubArrayLen(int s, int[] nums) {
int len=nums.length;
if(len==0)return 0;
int minLen=Integer.MAX_VALUE;
for (int i=1;i<len;i++){
if(nums[i-1]>=s) return 1;
int index=i-1;
int sum=nums[i];
//累加前面的元素，直到大于 s 或者 index<0
while(sum<s&&index>=0){
sum+=nums[index--];
}
if(sum>=s){
minLen=minLen>i-index?i-index:minLen;
} else if(i==len-1){
return 0;
}
}
return minLen;
}
这个是最开始想到了思路比较清晰，遍历数组然后逆序求和直到大于 S，要注意边界，比较慢，主要就是那个循环累加前面的元素会很耗费时间，111ms，14% beats🤣
解法二
public static int minSubArrayLen2(int s, int[] nums) {
int len =nums.length;
if(len==0)return 0;
//窗口左右边界
int head=0,tail=-1;
int minLen=Integer.MAX_VALUE;
int sum=0;
// 2,3,1,2,4,3 | 7
while (tail<len) {
if(sum>=s){
minLen=minLen>tail-head+1?tail-head+1:minLen;
//System.out.println(minLen);
//删除头节点（左边界左移）
sum-=nums[head++];
} else{
//尾指针到达边界了
if(tail==len-1) break;
//尾节点++，（右边界右移）
sum+=nums[++tail];
//如果有元素大于 s 直接返回，节约时间
if(nums[tail]>=s){
return 1;
}
}
}
return minLen==Integer.MAX_VALUE?0:minLen;
}
2ms ，99%beats，一对比差距就出来了，上面这种做法就是利用了滑动窗口的思想，很巧妙的利用了上一次计算的值，不用重复的计算累加和，上面的那种方法每次都会重新计算累加和，但是很多都是重复的计算，所以浪费了很多时间，要注意边界条件
2 3 1 2 4 3 s=7
自己在纸上画一下就懂了
解法三
找到一个模板，统一一下写法
public static int minSubArrayLen3(int s, int[] nums) {
int len =nums.length-1;
if(len==0)return 0;
int head=0,tail=-1;
int minLen=Integer.MAX_VALUE;
int sum=0;
// 2,3,1,2,4,3 | 7
while (head<=len) {
if(tail+1<=len && sum<s){
sum+=nums[++tail];
}else{
sum-=nums[head++];
}
if(sum>=s){
minLen=minLen>tail-head+1?tail-head+1:minLen;
}
}
return minLen==Integer.MAX_VALUE?0:minLen;
}
Update(2020.5.4)
上面的这也配叫模板？下面的是重做的时候统一的写法
var INF = 1 << 31
func minSubArrayLen(s int, nums []int) int {
left := 0
sum := 0
res := INF
for right := 0; right < len(nums); right++ {
sum += nums[right]
for sum >= s {
res = Min(res, right-left+1)
sum -= nums[left]
left++
}
}
if res == INF {
return 0
}
return res
}
func Min(a, b int) int {
if a < b {
return a
}
return b
}
面试题 57 - II. 和为 s 的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
解法一
滑动窗口，根据等差数列前 n 项和求 sum，然后逐步的缩圈，右移
public int[][] findContinuousSequence(int target) {
List<int[]> res=new ArrayList<>();
int left=1,right=2;
int sum=0;
//9 right 最多到 5
while(left<=right && right<=(target+1)/2){
//等差数列前 n 项和
int n=right-left+1;
sum=left*n+n*(n-1)/2;
if(sum>target){
left++; //剔除一个小的
}else if(sum<target){
right++; //添加一个大的
}else{ //build 结果集
res.add(build(left,right));
left++;//窗口左移，剔除一个小的
right++; //回头重写发现这里还可以优化，右边界也可以扩大
}
}
return res.toArray(new int[0][0]);
}
public int[] build(int left,int right){
int[] res=new int[right-left+1];
for(int i=left;i<=right;i++){
res[i-left]=i;
}
return res;
}
这里其实并不是最优解，还有更好的数学解法，直接根据求和公式，枚举所有的长度，逆向求出所有的首项，这里后面有时间再来实现
480. 滑动窗口中位数
中位数是有序序列最中间的那个数。如果序列的大小是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5
给出一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
例如：
给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。
窗口位置 中位数
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。
提示：
假设k是合法的，即：k 始终小于输入的非空数组的元素个数。
head 题，理清楚思路后也不难。
public static double[] medianSlidingWindow(int[] nums, int k) {
//看了一圈评论区，大概知道思路了，还是要排序
//List<Integer> list=new ArrayList<>(); 用链表还是不方便啊
int [] queue=new int[k];
int head=0,tail=k-1;
//头尾
double [] res=new double[nums.length-k+1];
for (int i=0;i<k;i++) {
queue[i]=nums[i];
}
Arrays.sort(queue);
printArray(queue);
if (k%2==0) {
res[0]=queue[(k-1)/2]/2.0+queue[(k-1)/2+1]/2.0;
//注意除小数 .。这里的测试用例 Integer 最大值，直接相加/2 会越界
} else {
res[0]=queue[k/2];
}
for (int i=k;i<nums.length;i++) {
//插入之前要移除上一次的头元素，这里用数组不好搞啊啊
//System.out.println(nums[i-k]);
deleHead(queue,nums[i-k]);
tail--;
//printArray(queue);
//二分找插入点
int index=binarySearch(queue,0,tail,nums[i]);
System.out.println(index);
tail++;
//插入元素，tail++;
for (int j=tail;j>index;j--) {
//后一个等于前一个，给插入的元素腾出位置
queue[j]=queue[j-1];
}
queue[index]=nums[i];
//求中点
if (k%2==0) {
res[i-k+1]=queue[head+(tail-head)/2]/2.0+queue[head+(tail-head)/2+1]/2.0;
} else {
res[i-k+1]=queue[head+(tail-head)/2];
}
}
return res;
}
public static void deleHead(int []nums,int target){
for (int j=0,i=0;j<nums.length;j++,i++) {
if(nums[j]==target){
if (i==nums.length-1) {
return;
}
while(i<nums.length-1){
nums[i]=nums[i+1];
i++;
}
return;
}
}
}
public static int binarySearch(int []nums,int lo,int hi,int target){
while(lo<=hi){
int mid=lo+(hi-lo)/2;
if(nums[mid]<target){
lo=mid+1;
} else if(nums[mid]>target){
hi=mid-1;
} else{
return mid;
}
}
return lo;
}
根据评论区提供的思路，用数组实现了一遍，当时就感觉有问题，确实，最后 164ms ，27%，很慢了，我觉得主要问题就是那个删除头的操作，但是毕竟数组，没办法，随即改用链表
public static double[] medianSlidingWindow2(int[] nums, int k) {
//看了一圈评论区，大概知道思路了，还是要排序
List<Integer> list=new ArrayList<>();
int head=0,tail=k-1;
//头尾
double [] res=new double[nums.length-k+1];
//Arrays.sort(nums,0,k);
int []temp=new int[k];
for (int i=0;i<k;i++) {
temp[i]=nums[i];
}
Arrays.sort(temp);
for (int i=0;i<k;i++) {
list.add(temp[i]);
}
if (k%2==0) {
res[0]=list.get((k-1)/2)/2.0+list.get((k-1)/2+1)/2.0;
} else {
res[0]=list.get(k/2);
}
for (int i=k;i<nums.length;i++) {
//插入之前要移除上一次的头元素，这里用数组不好搞啊啊
//list.remove((Object)nums[i-k]); 直接删太慢了
int dele=binarySearch(list,0,k-1,nums[i-k]);
list.remove(dele);
//System.out.println(list);
//二分找插入点，找的区间为 [i-k+1, i-1]
//int head=i-k+1,tail=i-1;
int index=binarySearch(list,0,k-2,nums[i]);
System.out.println(index);
list.add(-1);
for (int j=k-1;j>index;j--) {
//后一个等于前一个，给插入的元素腾出位置
list.set(j,list.get(j-1));
}
list.set(index,nums[i]);
System.out.println(list);
//求中点
if (k%2==0) {
res[i-k+1]=list.get((k-1)/2) / 2.0 + list.get((k-1)/2+1)/2.0;
} else {
res[i-k+1]=list.get(k/2);
}
}
return res;
}
public static int binarySearch(List<Integer> list,int lo,int hi,int target){
while(lo<=hi){
int mid=lo+(hi-lo)/2;
if(list.get(mid)<target){
lo=mid+1;
} else if(list.get(mid)>target){
hi=mid-1;
} else{
return mid;
}
}
return lo;
}
47ms，70%左右，删除的时候利用二分删除，如果直接根据元素去删就跟数组效率差不多了。
76. 最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入：S = "ADOBECODEBANC", T = "ABC"
输出："BANC"
说明：
- 如果 S 中不存这样的子串，则返回空字符串 “"。
- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
解法一
public static String minWindow(String s, String t) {
int slen=s.length();
int tlen=t.length();
int l=0,r=0; //初始都为 0
int[] target=new int[256]; //A:1 B:1 C:1
int[] window=new int[256];
int count=0; //不同字符的数量
for (int i=0;i<tlen;i++) {
target[t.charAt(i)]++;
}
for (int a:target) {
if (a!=0) {
count++; //统计不同字符出现的次数
}
}
int match=0; //match 代表已经匹配的字符
int[] res=new int[]{0,Integer.MAX_VALUE};
while(r<slen){
char c=s.charAt(r);
if(target[c]!=0){ //在目标子串中存在
window[c]++; //window 对应的 char++
if(window[c]==target[c]){ //到达了目标串中该 char 所需的数量
match++;
}
}
r++;
while(l<r&&count==match) { //满足目标串，注意别越界
char d=s.charAt(l);
if (r-l<res[1]-res[0]) { //统计最小值
res[0]=l;
res[1]=r;
}
l++;
if (target[d]!=0) {
window[d]--;
if (window[d]<target[d]) {//左边界左移后不再满足目标串
match--;
}
}
}
}
return res[1]==Integer.MAX_VALUE?"":s.substring(res[0],res[1]);
}
10ms 86%，Hard 题，其实大致的思路还是有的，主要是不知道怎么去和目标串对比，没想到用一个window数组去对比，一致想的是在目标串的数组上做手脚，但是越想越复杂。太蠢了😅，这题其实也可以用一个 HashMap 来做，但是我看了下提交记录上的普遍都是 7,80ms，相对都比较慢，实际上题目没有明确的说明有特殊字符的话都是可以用一个** ASCII **数组来充当 HashMap 的，当然我这里用数组的时候相比 HashMap 要多了一步，需要统计不同字符出现的次数，不过这个操作也是常数级别的操作，并不耗时，整体时间复杂度 O(N+M)，NM 分别代表目标子串t 和源字符串 p的长度，首先遍历了t 然后滑动窗口，后面的滑动窗口左右边界最多移动 2M 次
Update
2020.4.15，在瞄了一眼之前做的之后按照之前的思路重写了一遍，感觉还行，有一个地方 WA 了一次
//update: 2020.4.15
public String minWindow(String s, String t) {
if(s==null || t==null) return "";
int[] needMap=new int[128]; //需要的字符 map
int[] curMap=new int[128]; //已经匹配的字符 map
int needCount=0; //需要匹配的字符个数
for(int i=0;i<t.length();i++){
if(needMap[t.charAt(i)]==0){
needCount++;
}
needMap[t.charAt(i)]++;
}
int matchCount=0; //已经匹配的个数
int left=0,right=0;
int minLeft=0,maxRight=Integer.MAX_VALUE;
while(left<=right && right<s.length()){
char c=s.charAt(right);
if(needMap[c]!=0){
curMap[c]++;
if(curMap[c]==needMap[c]){
matchCount++;
}
}
while(left<=right && right<s.length() && matchCount==needCount){
if(right-left<maxRight-minLeft){
maxRight=right;
minLeft=left;
}
char cl=s.charAt(left);
if(curMap[cl]!=0){
curMap[cl]--;
//这里注意，WA 点，开始写的=0
if(curMap[cl]<needMap[cl]){
matchCount--;
}
}
left++;
}
right++;
}
return Integer.MAX_VALUE==maxRight?"":s.substring(minLeft,maxRight+1);
}
刷题的时候发现有一道很类似的题，最小窗口子序列 唯一的区别就是这道题要求有序（子序列）
632. 最小区间
Difficulty: 困难
你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1:
输入：[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释：
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
注意：
- 给定的列表可能包含重复元素，所以在这里升序表示 >= 。
- 1 <=
k<= 3500 - -105 <=
元素的值<= 105
解法一
func smallestRange(nums [][]int) []int {
var n = len(nums)
//列表中所有元素 k, 存在于那些数组中
var m = make(map[int][]int)
var Max = func (a, b int) int {if a > b {return a}; return b}
var Min = func (a, b int) int {if a < b {return a}; return b}
//记录最大最小值，然后在区间内滑窗，也可以直接将所有数组归并排一下，然后滑窗，比较麻烦，懒得写了
//所以下面的做法实际上是和循序无关的，没有用到有序这个条件
var maxV = math.MinInt32
var minV = math.MaxInt32
for i :=0; i < n; i++ {
for j := 0; j < len(nums[i]); j++ {
m[nums[i][j]] = append(m[nums[i][j]], i)
maxV = Max(maxV, nums[i][j])
minV = Min(minV, nums[i][j])
}
}
//同 76. 最小覆盖子串，这题可能思维的转换比较重要
var count = 0
var freq = make([]int, n+1)
var res =[]int{minV, maxV}
var left = minV
for right := minV; right <= maxV; right++ {
if lis, ok := m[right]; ok {
for _, numIdx := range lis {
freq[numIdx]++
if freq[numIdx] == 1{
count++
}
}
}
for count == n && left <= right {
if right-left < res[1]-res[0] {
res[0] = left
res[1] = right
}
if lis, ok := m[left]; ok{
for _, numIdx := range lis {
freq[numIdx]--
if freq[numIdx] < 1 {
count--
}
}
}
left++
}
}
return res
}
解法二
上面的解法并不是最好的解法，没有用到有序的条件，比较好的解法应该是小根堆（本来打算用 Go 撸一个的，写一半感觉太麻烦了，不过整体小根堆的逻辑实现是对的，就是没有泛型要改很多东西，不太方便）
维护两个最值，一个是找到一个能覆盖当前所有列表的最小的右端点（max），一个是当前列表最小的那个元素（最左的端点），然后不断缩减左端点求最小区间
class Node {
int i, j;
public Node (int i, int j) {
this.i = i;
this.j = j;
}
}
//k 组链表，平均 m 个元素，时间复杂度 O(kmlog(k))
public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> nums.get(a.i).get(a.j)-nums.get(b.i).get(b.j));
int INF = (int) 1e5+1;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.size(); i++) {
pq.add(new Node(i, 0));
max = Math.max(max, nums.get(i).get(0));
}
int [] res = {-INF, INF};
while (true) {
Node cur = pq.poll();
//应该把 val 也存进去的，懒得改了
if (max-nums.get(cur.i).get(cur.j) < res[1]-res[0]) {
res[0] = nums.get(cur.i).get(cur.j);
res[1] = max;
}
if (cur.j+1 >= nums.get(cur.i).size()) {
break;
}
pq.add(new Node(cur.i, cur.j+1));
max = Math.max(max, nums.get(cur.i).get(cur.j+1));
}
return res;
}
438. 找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 1:
输入：
s: "cbaebabacd" p: "abc"
输出：
[0, 6]
解释：
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
示例 2:
输入：
s: "abab" p: "ab"
输出：
[0, 1, 2]
解释：
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
解法一
这题和上面一题其实一样，只是这里要求是连续的，在上面一题的基础上在添加结果的时候判断下长度就 OK
public List<Integer> findAnagrams(String s, String p) {
int[] target=new int[256];
int[] window=new int[256];
int l=0,r=0;
int plen=p.length();
int slen=s.length();
int count=0,match=0;
List<Integer> res=new ArraysList<>();
for (int i=0;i<plen;i++) {
target[p.charAt(i)]++;
}
for (int a:target) {
if(a!=0){
count++;
}
}
while(r<slen){
char right=s.charAt(r);
if (target[right]!=0) {
window[right]++;
if (window[right]==target[right]) {
match++;
}
}
r++;
while(l<r && count==match){
char left=s.charAt(l);
if (r-l==res) {
res.add(l);
}
l++;
if (target[left]!=0) {
window[left]--;
//不满足了
if (window[left]<target[left]) {
match--;
}
}
}
}
return res;
}
UPDATE:2020.7.23
用模板重写了下
func findAnagrams(s string, p string) []int {
var target = make([]int, 128)
var window = make([]int, 128)
var match = 0
for _, sp := range p {
if target[sp] == 0 {
match++
}
target[sp]++
}
var left = 0
var count = 0
var res []int
for right := 0; right < len(s); right++ {
if target[s[right]] > 0 {
window[s[right]]++
if window[s[right]] == target[s[right]] {
count++
}
}
for count == match && left <= right {
if right-left+1 == len(p) {
res = append(res, left)
}
if window[s[left]] > 0 {
window[s[left]]--
if window[s[left]] < target[s[left]] {
count--
}
}
left++
}
}
return res
}
15ms，86%时间复杂度O(M+N)，其实是完全套的之前最小覆盖子串的模板，不如肯定不好写这么长
解法二
正常的做法，实际上上面的解法一直在避免直接比较 target 和 window，但是实际上比较这两个数组的成本是很低的，两个数组长度固定，比较时间复杂度 O(1)，具体情况具体分析，不过套模板几乎是通用的
func findAnagrams(s string, p string) []int {
var left = 0
//-'a'看起来太丑了，直接 128
var target [128]int //注意用数组，可以直接比较
var window [128]int
for _, sp := range p {
target[sp]++
}
var res []int
for right := 0; right < len(s); right++ {
if target[s[right]] > 0 {
window[s[right]]++
}
for right-left+1 > len(p) {
if window[s[left]] > 0 {
window[s[left]]--
}
left++
}
if window == target {
res = append(res, left)
}
}
return res
}
567. 字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例 1:
输入：s1 = "ab" s2 = "eidbaooo"
输出：True
解释：s2 包含 s1 的排列之一 ("ba").
示例 2:
输入：s1= "ab" s2 = "eidboaoo"
输出：False
注意：
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
解法一
这题其实是 76. 最小覆盖子串 的弱化版本，套路滑窗，但是有一些细节需要注意
public boolean checkInclusion(String s1, String s2) {
if(s1==null || s2==null || s1.length()>s2.length()){
return false;
}
int n1=s1.length();
int n2=s2.length();
int[] freq=new int[26];
int count=0;
for(int i=0;i<n1;i++){
int c=s1.charAt(i)-'a';
if(freq[c]==0){
count++;
}
freq[c]++;
}
int[] window=new int[26];
int match=0;
int left=0;
for(int right=0;right<n2;right++){
int cr=s2.charAt(right)-'a';
if(freq[cr]>0){
window[cr]++;
if(window[cr]==freq[cr]){
match++;
}
}
while(right-left+1>n1){
int cl=s2.charAt(left)-'a';
if(freq[cl]>0){
//WA 点，开始写错了
//window[cl]--;
if(window[cl]==freq[cl]){
match--; //match--的前提是原本是匹配的
}
window[cl]--;
}
left++;
}
if(match==count){
return true;
}
}
return false;
}
一开始写完了，测试了用例发现都是对的，心里一喜，难道又 bugfree 了？提交，结果还是 WA 了🤣，debug 了半天，根据错误的哪个长 case 自己构造了一个短 case（长的不好 debug），然后发现了问题，这个问题我看见评论区也有人问到，顺手还回了一下😁，其实错误的原因就是套模板没套好，没理解模板的细节
这里的核心问题就是match--的时候有一个大前提：cl字符已经匹配好了，也就是window[cl]==freq[cl]
这个时候你left++将cl移除窗口，才能做match--操作，否则像之前的模板中
if (target[left]!=0) {
window[left]--;
//不满足了
if (window[left]<target[left]) {
match--;
}
}
这样写就有可能 window[left] 还没有匹配上，这个时候直接减就错了，之前的模板中缩圈都是在 match==count 的前提下缩圈的，所以没问题，都是匹配的，其实也可以像之前的模板一样写，就像下面这样
public boolean checkInclusion(String s1, String s2) {
if(s1==null || s2==null || s1.length()>s2.length()){
return false;
}
int n1=s1.length();
int n2=s2.length();
int[] freq=new int[26];
int count=0;
for(int i=0;i<n1;i++){
int c=s1.charAt(i)-'a';
if(freq[c]==0){
count++;
}
freq[c]++;
}
int[] window=new int[26];
int match=0;
int left=0;
for(int right=0;right<n2;right++){
int cr=s2.charAt(right)-'a';
if(freq[cr]>0){
window[cr]++;
if(window[cr]==freq[cr]){
match++;
}
}
//****************************
//主要就是这里不一样
while(match==count){
if(right-left+1==n1) return true;
int cl=s2.charAt(left)-'a';
if(freq[cl]>0){
window[cl]--;
if(window[cl]<freq[cl]){
match--;
}
}
left++;
}
//****************************
}
return false;
}
这样就不用考虑先减还是后减的问题了
解法二
这题其实还可以暴力做，窗口大小固定，每滑动一次就判断窗口和freq是不是相等，因为题目说了都是小写字母所以也是行得通的，只是常数会大一些，这里我就不写了，笔试推荐这样写，代码好写一点
面试题 17.18. 最短超串
假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
示例 1:
输入：
big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
small = [1,5,9]
输出：[7,10]
示例 2:
输入：
big = [1,2,3]
small = [4]
输出：[]
提示：
big.length <= 1000001 <= small.length <= 100000
解法一
也是属于 76. 最小覆盖子串的弱化，虽然解法都一样，没啥好说的，注意细节
//没啥好说的，套模板就行了
public int[] shortestSeq(int[] big, int[] small) {
if(big==null || big.length<=0) {
return new int[0];
}
int slen=small.length;
int blen=big.length;
int[] res=new int[2];
res[0]=-1;res[1]=-1;
int min=Integer.MAX_VALUE;
HashSet<Integer> set=new HashSet<>();
for(int i:small) set.add(i);
HashMap<Integer,Integer> window=new HashMap<>();
int match=0;
int left=0;
for(int right=0;right<blen;right++){
int wr=big[right];
if(set.contains(wr)){
window.put(wr,window.getOrDefault(wr,0)+1);
if(window.get(wr)==1){
match++;
}
}
while(match==slen){
if(right-left+1<min){
res[0]=left;
res[1]=right;
min=right-left+1;
}
int wl=big[left];
if(set.contains(wl)){
window.put(wl,window.get(wl)-1);
if(window.get(wl)==0){
match--;
}
}
left++;
}
}
return res[0]==-1?new int[0]:res;
}
1004. 最大连续 1 的个数 III
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
提示：
1 <= A.length <= 200000 <= K <= A.lengthA[i]为0或1
解法一
这题其实下面一题 424. 替换后的最长重复字符的弱化版本
//简单的滑窗
public int longestOnes(int[] A, int K) {
if(A==null || A.length<=0) return 0;
int N=A.length;
int left=0,res=0,countA=0;
for(int right=0;right<N;right++){
countA+=(A[right]&1);
//if 也可以，个人喜欢 while 通用性更强
while(right-left+1-countA>K){
countA-=(A[left++]&1);
}
res=Math.max(res,right-left+1);
}
return res;
}
按照模板来写简直是信手拈来（其实也没有什么模板，就是规范了写法而已）
5434. 删掉一个元素以后全为 1 的最长子数组
Difficulty: 中等
给你一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0 。
提示 1：
输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。
示例 2：
输入：nums = [0,1,1,1,0,1,1,0,1]
输出：5
解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。
示例 3：
输入：nums = [1,1,1]
输出：2
解释：你必须要删除一个元素。
示例 4：
输入：nums = [1,1,0,0,1,1,1,0,1]
输出：4
示例 5：
输入：nums = [0,0,0]
输出：0
提示：
1 <= nums.length <= 10^5nums[i]要么是0要么是1。
解法一
29th 双周赛的 t3，秒切，其实是上一题 [1004. 最大连续 1 的个数 III](#1004-最大连续 1 的个数-iii) 的弱化
public int longestSubarray(int[] nums) {
int res=0, sum=0;
int left=0;
for(int right=0;right<nums.length;right++){
sum+=(nums[right]&1);
//区间和小于 right-left-1 说明中间不止一个 0 需要缩减窗口
while(left<right && sum<= right-left-1){
if(nums[left] == 1){
sum--;
}
left++;
}
//至少删除一个，所以不用+1
res = Math.max(res,right-left);
}
return res;
}
很可惜这次前 3 题 15 分钟就做完了，都是直接 web 上写的，本以为有机会 AK，最后一题搞了半天最后交了一发还是没过，貌似很多人写了假算法，贪心莽过了（lc 数据太弱了）
424. 替换后的最长重复字符
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意： 字符串长度 和 k 不会超过 104。
示例 1:
输入：
s = "ABAB", k = 2
输出：
4
解释：
用两个'A'替换为两个'B', 反之亦然。
示例 2:
输入：
s = "AABABBA", k = 1
输出：
4
解释：
将中间的一个'A'替换为'B', 字符串变为 "AABBBBA"
子串 "BBBB" 有最长重复字母，答案为 4
解法一
上面一题的加强版
public int characterReplacement(String s, int k) {
int max = 0, start = 0, end = 0, cur = -1;
int[] count = new int[256];
while (end < s.length()) {
//当前窗口出现最多的字符
cur = Math.max(cur, ++count[s.charAt(end)]);
//不能替换了，不同字符太多了，需要缩减窗口
while (end - start + 1 - cur > k){
//缩减左边界的 count
count[s.charAt(start)]--;
start++;//不能替换了，start++
}
//统计最大值
max = Math.max(max, end - start + 1);
end++;
}
return max;
}
UPDATE: (2020.5.5)
按照模板重写，果然滑窗的题都是一样的
public int characterReplacement(String s, int k) {
if(s==null || s.length()<=0){
return 0;
}
int n=s.length();
int res=1;
int left=0;
int[] freq=new int[128];
int maxFreq=0;
for(int right=0;right<n;right++){
char c=s.charAt(right);
freq[c]++;
maxFreq=Math.max(maxFreq,freq[c]);
while((right-left+1-maxFreq)>k){
freq[s.charAt(left)]--;
left++; //这里实际上只会执行一次，改成 if 也是可以的，不过为了统一写法就不改了
}
res=Math.max(res,right-left+1);
}
return res;
}
重写这题的时候发现这题还是挺有意思的，这个里面的maxFreq是一个只增不减的量，是一个历史最大值，只有当出现更大的 freq 的时候才会更新maxFreq，当maxFreq保持不变的时候结果不会受到影响，只有出现了更大 freq 的时候才有可能会使结果变大
因为我们只对最长有效的子字符串感兴趣，所以我们的滑动窗口不需要收缩，即使窗口可能覆盖无效的子字符串。我们可以通过在右边添加一个字符来扩展窗口，或者将整个窗口向右边移动一个字符。而且我们只在新字符的计数超过历史最大计数（来自覆盖有效子字符串的前一个窗口）时才增长窗口。也就是说，我们不需要精确的当前窗口的最大计数；我们只关心最大计数是否超过历史最大计数；这只会因为新字符而发生。
解法二
憨憨的解法，不过绝对是能 AC 的，时间复杂度并没有问题，依然是O(N)
public int characterReplacement(String s, int k) {
if(s==null || s.length()<=0){
return 0;
}
int n=s.length();
int res=1;
for(int c='A';c<='Z';c++){
int[] freq=new int[128];
int temp=1;
int left=0;
for(int right=0;right<n;right++){
if(s.charAt(right)==c){
freq[c]++;
}
while((right-left+1-freq[c])>k){
if(s.charAt(left)==c){
freq[c]--;
}
left++;
}
temp=Math.max(temp,right-left+1);
}
res=Math.max(res,temp);
}
return res;
}
既然题目说了只有大写字母，那就直接枚举所有的字符然后滑窗就行了😂，简单直白
1234. 替换子串得到平衡字符串
有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0
示例 1：
输入：s = "QWER"
输出：0
解释：s 已经是平衡的了。
示例 2：
输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" （或 "QRWE") 是平衡的。
示例 3：
输入：s = "QQQW"
输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。
示例 4：
输入：s = "QQQQ"
输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
提示：
- 1 <= s.length <= 10^5
- s.length 是 4 的倍数
- s 中只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符
解法一
周赛题，说实话不多做做竞赛真不知道自己多菜
(update: 2020.4.15)
我拿到这题，首先想到的是无脑套路滑窗，既然要保证平衡，那么每个字符出现的次数都应该是N/4，所以我们可以统计下多出来的有几个，比如QQQW，那么多出来的就是 2 个**Q，也就是说我们要求的窗口内至少**有 2 个 Q，这样问题其实就转换成了 [76. 最小覆盖子串](#76-最小覆盖子串）（这明明是个 mid 题，你咋还给转换成 hard 了，你是不是傻🤣)
其实最小覆盖子串看起来好像挺难，但是是有套路的，我们直接套模板就可以了
public int balancedString(String s) {
if(s==null || s.length()<=0) return -1;
int N=s.length();
//这里用 26 有的浪费，为了方便写代码，就这样吧
int[] need=new int[26];
//初始化为-N/4 这样最后得到的大于 0 的值就是多出来的
Arrays.fill(need,-N/4);
int[] cur=new int[26];
for(int i=0;i<N;i++){
need[s.charAt(i)-'A']++;
}
//有几个字符多出来了
int needCount=0;
for(int i=0;i<need.length;i++){
if(need[i]>0) needCount++;
}
if(needCount==0) return 0;
int res=N;
int left=0,right=0;
int matchCount=0;
//无脑套路滑窗
while(right<s.length()){
char c=s.charAt(right);
if(need[c-'A']>0){
cur[c-'A']++;
if(cur[c-'A']==need[c-'A']){
matchCount++;
}
}
while(left<=right && matchCount==needCount){
res=Math.min(right-left+1,res);
char cl=s.charAt(left);
if(need[cl-'A']>0){
cur[cl-'A']--;
if(cur[cl-'A']<need[cl-'A']){
matchCount--;
}
}
left++;
}
right++;
}
return res;
}
解法二
上面的解法是考虑窗口内的元素组成，窗口内至少应该有哪些元素，反过来想，我们窗口内的元素是多出来的元素，我们是把多的元素放到窗口中，那么窗口外的元素就肯定都是小于等于 N/4的了，那么我们就可以利用这一点进行滑窗，统计符合条件的窗口的最小值，这样代码就会简洁很多
//code 删掉了，之前的代码有点问题，最后的返回值有些情况过不去，lc 的 case 太弱了，让我过了
UPDATE: (2020.5.4)
按照先前的模板来分析下，这里要求的是最小的修改次数，很明显不能用for-if，所以采用for-while的结构，for-while最基本的结构就是外层枚举所有right，内层根据题目要求缩减left，但是这题 left 也需要控制边界，我这里用的是left<=right 但是实际上这样会有一类 case 结果不对，比如"QWER"这样的，返回的结果是 1，我上面在最后做了特判（上面的特判是错的，比如“QWEE”这样的就返回 0），其实这里还可以修改下边界，改成left<N，这样就没问题了，这样 left 就可以超过 right 达到 right+1，这样对”QWER"就能得到正确的结果，并且根据题目信息当left=right+1之后left就不会再增加了，while 条件就无法满足了，但是有的题目left是不用设置限制的，基本上都是在达到 right+1 之后就不会继续增加了
class Solution {
public int balancedString(String s) {
if(s==null || s.length()<=0){
return 0;
}
int N=s.length();
int left=0;
int res=N;
int[] freq=new int[26];
for(int i=0;i<N;i++) {
freq[s.charAt(i)-'A']++;
}
for(int right=0;right<N;right++){
freq[s.charAt(right)-'A']--;
while(left<N && freq['Q'-'A']<=N/4 && freq['W'-'A']<=N/4 && freq['E'-'A']<=N/4 && freq['R'-'A']<=N/4){
res=Math.min(res,right-left+1);
freq[s.charAt(left++)-'A']++;
}
}
return res;
}
}
1358. 包含所有三种字符的子字符串数目
给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
示例 1：
输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" （相同字符串算多次）。
示例 2：
输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。
示例 3：
输入：s = "abc"
输出：1
提示：
- 3 <= s.length <= 5 x 10^4
- s 只包含字符 a，b 和 c 。
解法一
20 双周赛 T3
public int numberOfSubstrings(String s) {
int[] freq=new int[3];
int left=0,right=-1,slen=s.length();
int res=0;
//abc
while(left<slen-2){
while(right+1<slen && !valid(freq)){
freq[s.charAt(++right)-'a']++;
}
res+=valid(freq)?(slen-right):0;
freq[s.charAt(left)-'a']--;
left++;
}
return res;
}
public boolean valid(int[] freq){
return freq[0]!=0 && freq[1]!=0 && freq[2]!=0;
}
枚举所有的左边界，然后找到最短的可以满足的右边界，那么包括右边界和之后的所有的都满足条件，直接计算就可以了，时间复杂度O(N)
解法二
2020.5.4 用自己总结的滑窗模板重写，也是for-while结构，right 和 left 不能同时扩展。比如"aaacb"这样的 case
public int numberOfSubstrings(String s) {
int left=0;
int res=0;
int n=s.length();
int[] freq=new int[3];
for(int right=0;right<n;right++){
freq[s.charAt(right)-'a']++;
while(freq[0]>0 && freq[1]>0 && freq[2]>0){
res+=n-right; //后面的都符合条件
freq[s.charAt(left)-'a']--;
left++;
}
}
return res;
}
1423. 可获得的最大点数
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例 1：
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
示例 2：
输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
示例 3：
输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
示例 4：
输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
示例 5：
输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202
提示：
1 <= cardPoints.length <= 10^51 <= cardPoints[i] <= 10^41 <= k <= cardPoints.length
解法一
186 周赛 T2，很明显的滑动窗口，前后拿 K 张最大，只需要求一个最小的[n-k]区间值就行了，也可以用前缀和，思路都一样
func maxScore(cardPoints []int, k int) int {
if cardPoints == nil || len(cardPoints) == 0 {
return 0
}
n := len(cardPoints)
left := 0
right := n - k - 1
sum := 0
windowSum := 0
for i, num := range cardPoints {
sum += num
if i == right {
windowSum = sum
}
}
if k == n {
return sum
}
minWin := windowSum
for right+1 < n {
windowSum += (cardPoints[right+1] - cardPoints[left])
minWin = min(windowSum, minWin)
right++
left++
}
return sum - minWin
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Tag 里面有 dp，确实这题和前面的 石子游戏 有一点像，但是还是滑窗来的比较直接。
1208. 尽可能使字符串相等
给你两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
示例 1：
输入：s = "abcd", t = "bcdf", cost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。
示例 2：
输入：s = "abcd", t = "cdef", cost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。
示例 3：
输入：s = "abcd", t = "acde", cost = 0
输出：1
解释：你无法作出任何改动，所以最大长度为 1。
提示：
1 <= s.length, t.length <= 10^50 <= maxCost <= 10^6s和t都只含小写英文字母。
解法一
func equalSubstring(s string, t string, maxCost int) int {
left := 0
cost := 0
res := 0
for right := 0; right < len(s); right++ {
cost += getCost(s[right], t[right])
if cost <= maxCost {
res = max(res, right-left+1)
} else {
cost -= getCost(s[left], t[left])
left++
}
}
return res
}
func getCost(a, b byte) int {
if a < b { //a-b<0 byte 是 uint8 直接这样减会变成正数
return int(b - a)
}
return int(a - b)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
这个题本身不难，主要是为了学习滑窗类型的题，这题我又改了好长时间，果然做滑窗的题还是有点乱，不过做了这一题之后已经有点感觉了，目前打算把所有的滑窗都重做一遍，然后总结一下套路
思考
下面for-while的结构似乎更加统一，上面for-if的结构只能用在求最长，最大的情况下，这种时候left和right允许同时加加，所以用if也是可以的，但是求最短的时候，比如上面 209. 长度最小的子数组就不能用for-if ，当 right 到达边界的时候 left 可能还需要继续移动，所以不能用if
func equalSubstring(s string, t string, maxCost int) int {
left := 0
cost := 0
res := 0
for right := 0; right < len(s); right++ {
cost += getCost(s[right], t[right])
for cost > maxCost {
cost -= getCost(s[left], t[left])
left++
}
res = max(res, right-left+1)
}
return res
}
1052. 爱生气的书店老板
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
示例：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
提示：
1 <= X <= customers.length == grumpy.length <= 200000 <= customers[i] <= 10000 <= grumpy[i] <= 1
解法一
滑动窗口的感觉来了，越来越熟练了，这题直接 bugfree 了😁
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
if(grumpy==null || grumpy.length<0) return 0;
int N=grumpy.length;
int left=0;
int window=0;//窗口内反转人数
int max=0; //最多反转人数
for(int right=0;right<N;right++){
if(grumpy[right]==1){
window+=customers[right];
}
//while 和 if 都可以，个人比较喜欢 while 通用性比较强
while(right-left+1>X){
if(grumpy[left]==1){
window-=customers[left];
}
left++;
}
max=Math.max(window,max);
}
int res=0;
for(int i=0;i<N;i++){
res+=(grumpy[i]==0?customers[i]:0);
}
return res+max;
}
可以看到仍然是前面总结的for-while结构，等我把所有的滑窗 tag 做完了再来总结一波
1040. 移动石子直到连续 II
在一个长度无限的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作端点石子。
每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。
值得注意的是，如果石子像 stones = [1,2,5] 这样，你将无法移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。
示例 1：
输入：[7,4,9]
输出：[1,2]
解释：
我们可以移动一次，4 -> 8，游戏结束。
或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。
示例 2：
输入：[6,5,4,3,10]
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。
示例 3：
输入：[100,101,104,102,103]
输出：[0,0]
提示：
3 <= stones.length <= 10^41 <= stones[i] <= 10^9stones[i]的值各不相同。
解法一
懵逼，某次周赛的 T4，嗯抄，不会做，题目都差点没看懂
public int[] numMovesStonesII(int[] stones) {
if(stones==null || stones.length<=0){
return new int[2];
}
//0 1 2 3 4 5 6 7 8 9 10
// 0 1 2 3 4
int N=stones.length;
Arrays.sort(stones);
int left=0;
int[] res=new int[2];
res[0]=Integer.MAX_VALUE;
for(int right=0;right<N;right++){
//整个区间范围大于 N 了需要缩小区间
while(stones[right]-stones[left]+1>N){
left++;
}
int windowStones=right-left+1;
if(windowStones==N-1&&stones[right]-stones[left]+1==N-1){
res[0]=Math.min(2,res[0]);
}else{
res[0]=Math.min(res[0],N-windowStones);
}
}
res[1]=Math.max(stones[N-1]-stones[1]-N+2,stones[N-2]-stones[0]-N+2);
return res;
}
1456. 定长子串中元音的最大数目
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。
示例 1：
输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。
示例 2：
输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。
示例 3：
输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。
示例 4：
输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。
示例 5：
输入：s = "tryhard", k = 4
输出：1
提示：
- 1 <= s.length <= 10^5
- s 由小写英文字母组成
- 1 <= k <= s.length
解法一
好久没写滑窗的题了，回顾下之前的模板，for-while结构
public int maxVowels(String s, int k) {
int left=0;
int res=0;
int count=0;
for(int right=0;right<s.length();right++){
if(vowel(s.charAt(right))){
count++;
}
while(right-left >= k){
if(vowel(s.charAt(left))){
count--;
}
left++;
}
res=Math.max(res,count);
}
return res;
}
public boolean vowel(char ch){
return ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u';
}
1461. 检查一个字符串是否包含所有长度为 K 的二进制子串
Difficulty: 中等
给你一个二进制字符串 s 和一个整数 k 。
如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 True ，否则请返回 False 。
示例 1：
输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。
示例 2：
输入：s = "00110", k = 2
输出：true
示例 3：
输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。
示例 4：
输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。
示例 5：
输入：s = "0000000001011100", k = 4
输出：false
提示：
1 <= s.length <= 5 * 10^5s中只含 0 和 1 。1 <= k <= 20
解法一
某次周赛的 T2 还是 T3，忘了，我用了最暴力的方法，直接回溯生成了所有的二进制串，然后对比的，写的很快，也 AC 了，但是但是后面一直没时间重写，今天偶然发现了这道题，重写下
经典 for-while 结构
func hasAllCodes(s string, k int) bool {
var set = make(map[int]bool)
var left = 0
var cur = 0
for right := 0; right < len(s); right++{
cur = cur * 2 + int(s[right] & 1)
for right - left + 1 > k{
cur &= ^(1 << k) //将首位置为 0
left++
}
if right - left + 1 == k{
set[cur] = true
}
}
return len(set) == 1 << k
}
这个题也可以直接存字符串进去，但是存字符串的时间复杂度就不是 O(N) 了 (N 为字符长度），而是 O(KN)，因为字符串 Hash 的复杂度是 O(K)，但是这里 K 很小，所以其实也无所谓，但是我们还是要追求更加优秀的解法，所以最好的做法还是将其转换成数字，然后存到哈希表中，这里看了别人的解法又学到了一手位运算的小技巧，cur & ^(1<<k)（k 为 cur 长度-1）可以将 cur 首位置为 0，也就是消去首位，原理也很简单，就不赘述了
1498. 满足条件的子序列数目
Difficulty: 中等
给你一个整数数组 nums 和一个整数 target 。
请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
由于答案可能很大，请将结果对 10^9 + 7 取余后返回。
示例 1：
输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)
示例 2：
输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
示例 3：
输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）
示例 4：
输入：nums = [5,2,4,1,7,6,8], target = 16
输出：127
解释：所有非空子序列都满足条件 (2^7 - 1) = 127
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^61 <= target <= 10^6
解法一
双指针滑窗，很关键的一步就是排序，因为我们只关心最大最小值，而且是子序列，与顺序无关
//双指针
public int numSubseq(int[] nums, int target) {
Arrays.sort(nums);
int MOD = (int)(1e9+7);
int n = nums.length;
//预处理出幂值表
int[] pow = new int[n];
pow[0] = 1;
for (int i = 1; i < n; i++){
pow[i] = (pow[i-1] << 1) % MOD;
}
int left = 0, right = n-1;
long count = 0;
while(left <= right){
while(left <= right && nums[left] + nums[right] > target) {
right--;
}
if (left <= right) {
//nums[left] + nums[right] <>= target
//包含 left 的子序列个数：left 固定，在 [left+1,right] 选若干个，就有 2^(right-left) 种选法
count = (count + pow[right-left]) % MOD ;
}
left++;
}
return (int)count%MOD;
}
解法二
二分
//二分
public int numSubseq(int[] nums, int target) {
Arrays.sort(nums);
int MOD = (int)(1e9+7);
int n = nums.length;
//预处理出幂值表
int[] pow = new int[n];
pow[0] = 1;
for (int i = 1; i < n; i++){
pow[i] = (pow[i-1] << 1) % MOD;
}
long count = 0;
for (int i = 0; i < n; i++) {
if (target-nums[i] < 0){
break;
}
int right = search(nums, target-nums[i]);
if (right >= i){
count = (count + pow[right-i]) % MOD;
}
}
return (int) count % MOD;
}
//搜索最后一个小于等于 target 的值
public int search(int[] nums, int target){
int left = 0, right = nums.length-1;
int res = -1;
while (left <= right) {
int mid = left + (right-left)/2;
if (nums[mid] <= target){
res = mid;
left = mid + 1;
}else{
right = mid - 1;
}
}
return res;
}
904. 水果成篮
Difficulty: 中等
在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：
- 把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
- 移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。
你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果总量是多少？
感觉这里想表达的应该是水果树的数量 示例 1：
输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。
示例 2：
输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2].
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。
示例 3：
输入：[1,2,3,2,2]
输出：4
解释：我们可以收集 [2,3,2,2].
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。
示例 4：
输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：我们可以收集 [1,2,1,1,2].
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 个水果。
提示：
1 <= tree.length <= 400000 <= tree[i] < tree.length
解法一
题目意思其实就是求只包含 2 个元素的最长子串，题目表述的不太清楚，已经反馈了
func totalFruit(tree []int) int {
var left = 0
var Max = func (a, b int) int {if a>b {return a};return b}
var n = len(tree)
var freq [40001]int
var res, count = 0, 0
for right := 0; right < n; right++ {
if freq[tree[right]] == 0 {
count++
}
freq[tree[right]]++
for count > 2 {
freq[tree[left]]--
if freq[tree[left]] == 0 {
count--
}
left++
}
res = Max(res, right-left+1)
}
return res
}
NC562. 牛牛的魔法卡
牛牛从小就有收集魔法卡的习惯，他最大的愿望就是能够集齐 k 种不同种类的魔法卡，现在有 n 张魔法卡，这 n 张魔法卡存在于一维坐标点上， 每张魔法卡可能属于某一种类。牛牛如果想收集魔法卡就需要从当前坐标点跳跃到另外一个魔法卡所在的坐标点，花费的代价是两个跳跃坐标点之间的距离差。 牛牛可以从任意的坐标点出发，牛牛想知道他集齐 k 种魔法卡所花费的最小代价是多少，如果集不齐 k 种魔法卡，输出-1。 第一行输入两个整数 n,k, 分别表示魔法卡的个数和种类个数。 接下来有 n 行，每行两个数 x，y 分别表示属于哪一种魔法卡和魔法卡所在的坐标
示例 1
输入：7,3,[[0,1],[0,2],[1,5],[1,1],[0,7],[2,8],[1,3]]
输出：3
说明：
样例一：牛牛从坐标点 5 出发，经过 7、8 两个点就收集了 3 张不同种类的魔法卡，达成成就。所需代价 （7-5）+（8-7） = 3
备注：
- 1<=n<=10^6
- 1<=k<=50 0<=x<k
- 0 <= y <= 1e9
解法一
tag 是二分，但是想了一会儿感觉好像没啥好的二分的思路，二分答案貌似可行，不过这题滑窗的思路更简单，类似 76-最小覆盖子串滑就完事儿了
public int solve (int n, int k, int[][] card) {
// write code here
Arrays.sort(card, (c1,c2)->c1[1]-c2[1]);
int INF = Integer.MAX_VALUE;
int left = 0;
int count = 0;
int[] freq = new int[k+1];
int res = INF;
for (int right = 0; right < n; right++) {
if (freq[card[right][0]] == 0) {
count++;
}
freq[card[right][0]]++;
while(left<=right && count == k){
res = Math.min(res, card[right][1] - card[left][1]);
freq[card[left][0]]--;
if (freq[card[left][0]]==0) {
count--;
}
left++;
}
}
if (res == INF) {
return -1;
}
return res;
}
1870. 全零子串的数量（LintCode）
给出一个只包含 0 或 1 的字符串 str, 请返回这个字符串中全为 0 的子字符串的个数 1<=|str|<=30000
例 1:
输入："00010011"
输出：9
解释：
"0"子字符串有 5 个，
"00"子字符串有 3 个，
"000"子字符串有 1 个。
所以返回 9
例 2:
输入："010010"
输出：5
解法一
直接滑就行了，统计所有 0 区间的长度，注意组合数的计算就行了
// 1 1 1 1 1 (5+4+3+2+1) = n(n-1)/2 + n or n(n+1)/2
public int stringCount(String str) {
// Write your code here.
int left = 0, right = 0;
int res = 0;
while (right < str.length()) {
while(right < str.length() && str.charAt(right) == '0'){
right++;
}
// (0 0 0) 1 1
// l n r
int n = right-left;
//C(n+1,2)/2
res += n*(n+1)/2;
right++;
left = right;
}
return res;
}
1529. 绝对差不超过限制的三元子数组（LintCode）
给定一个递增的整数数组 nums，和一个表示限制的整数 limit，请你返回满足条件的三元子数组的个数，使得该子数组中的任意两个元素之间的绝对差小于或者等于 limit。
如果不存在满足条件的子数组，则返回 0 。
数据范围： 1 ≤ len(nums) ≤ 1e4，1 ≤ limit ≤ 1e6，0 ≤ nums[i] ≤ 1e6 由于答案可能很大，请返回它对 99997867 取余后的结果。
样例 1:
输入：[1, 2, 3, 4], 3
输出：4
解释：可选方案有 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)。因此，满足条件的三元组有 4 个。
样例 2:
输入：[1, 10, 20, 30, 50], 19
输出：1
解释：唯一可行的三元组是 (1, 10, 20)，所以答案为 1。
挑战 你可以只用 O(n) 的时间复杂度解决这个问题吗？
解法一
我一开始看见是 Hard 想的挺复杂的，什么单调栈都搞出来了，但是仔细看题会发现题目给的数组是有序的，所以直接滑窗然后统计就行了，这里需要注意计算的方式，避免算重
//LintCode 上居然是 Hard，感觉不是很难
public int tripletSubarray(int[] nums, int limit) {
// write your code here
int n = nums.length;
int left = 0, right = 0;
int res = 0;
while (left <= right) {
//找到最远的合法 right
while (right < n && nums[right]-nums[left] <= limit) {
right++;
}
// 1 (2 3 4) 5
//left len right
int len = right-left-1;
left++;
if (len < 2) continue;
//C(len,2) 求以 left 开头，包含 left 的所有 3 元组，这样不会重复
res += len*(len-1)/2;
}
return res;
}
感觉自己静下心来想的话很多题目还是可以自己做出来的，但是就是想的可能有点慢，特别是竞赛中，规定了时间后一慌就更慢了。看来还是练少了
1375. 至少 K 个不同字符的子串（LintCode）
给定一个仅包含小写字母的字符串 S.
返回 S 中至少包含 k 个不同字符的子串的数量。
- 10 ≤ length(S) ≤ 1,000,000
- 1 ≤ k ≤ 26
样例 1:
输入：S = "abcabcabca", k = 4
输出：0
解释：字符串中一共就只有 3 个不同的字符。
样例 2:
输入：S = "abcabcabcabc", k = 3
输出：55
解释：任意长度不小于 3 的子串都含有 a, b, c 这三个字符。
比如，长度为 3 的子串共有 10 个，"abc", "bca", "cab" ... "abc"
长度为 4 的子串共有 9 个，"abca", "bcab", "cabc" ... "cabc"
...
长度为 12 的子串有 1 个，就是 S 本身。
所以答案是 1 + 2 + ... + 10 = 55.
解法一
经典滑窗，非常套路，想好怎么统计就行了
public long kDistinctCharacters(String s, int k) {
int n = s.length();
int left = 0;
int[] freq = new int[128];
int count = 0;
long res = 0;
for (int right = 0; right < n; right++) {
char cr = s.charAt(right);
if (freq[cr] == 0) {
count++;
}
freq[cr]++;
while (count >= k && left <= right) {
// abc | abcabcabc
// l r(2) n(12)
//统计以 s[left,right] 开头的所有子串
//10+9+8+7+...+1
res += n-right;
char cl = s.charAt(left);
freq[cl]--;
if (freq[cl] <= 0) {
count--;
}
left++;
}
}
return res;
}
386. 最多有 k 个不同字符的最长子字符串 (LintCode)
给定字符串 S，找到最多有 k 个不同字符的最长子串 T。
样例 1:
输入：S = "eceba" 并且 k = 3
输出：4
解释：T = "eceb"
样例 2:
输入：S = "WORLD" 并且 k = 4
输出：4
解释：T = "WORL" 或 "ORLD"
挑战： O(n) 时间复杂度
解法一
无脑滑窗就行了，太套路了
public int lengthOfLongestSubstringKDistinct(String s, int k) {
// write your code here
int n = s.length();
int left = 0;
int res = 0;
int[] freq = new int[128];
int count = 0;
for (int right = 0; right < n; right++) {
char cr = s.charAt(right);
if (freq[cr] == 0) {
count++;
}
freq[cr]++;
while (left <= right && count > k) {
char cl = s.charAt(left);
freq[cl]--;
if (freq[cl] <= 0) {
count--;
}
left++;
}
res = Math.max(res, right-left+1);
}
return res;
}
1675. 数组的最小偏移量
Difficulty: 困难
给你一个由 n 个正整数组成的数组 nums 。
你可以对数组的任意元素执行任意次数的两类操作：
- 如果元素是偶数 ，除以
2- 例如，如果数组是
[1,2,3,4]，那么你可以对最后一个元素执行此操作，使其变成[1,2,3,2]
- 例如，如果数组是
- 如果元素是奇数 ，乘上
2- 例如，如果数组是
[1,2,3,4]，那么你可以对第一个元素执行此操作，使其变成[2,2,3,4]
- 例如，如果数组是
数组的 偏移量 是数组中任意两个元素之间的 最大差值 。
返回数组在执行某些操作之后可以拥有的 最小偏移量 。
示例 1：
输入：nums = [1,2,3,4]
输出：1
解释：你可以将数组转换为 [1,2,3,2]，然后转换成 [2,2,3,2]，偏移量是 3 - 2 = 1
示例 2：
输入：nums = [4,1,5,20,3]
输出：3
解释：两次操作后，你可以将数组转换为 [4,2,5,5,3]，偏移量是 5 - 2 = 3
示例 3：
输入：nums = [2,10,8]
输出：3
提示：
- n == nums.length
- 2 <= n <= 105
- 1 <= nums[i] <= 109
解法一
和上面 632-最小区间一样，将数据变成和最小区间一样的形式，然后直接套用
public int minimumDeviation(int[] nums) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[2]-b[2]);
List<List<Integer>> lis = new ArrayList<>();
int max = 0;
for (int i = 0; i < nums.length; i++) {
ArrayList<Integer> tmp = new ArrayList<>();
if (nums[i] % 2 == 1) {
pq.add(new int[]{i, 0, nums[i]});
max = Math.max(max, nums[i]);
tmp.add(nums[i]);
tmp.add(nums[i] * 2);
} else {
tmp.add(nums[i]);
while (nums[i] % 2 == 0) {
tmp.add(nums[i]/2);
nums[i]/=2;
}
pq.add(new int[]{i, 0, nums[i]});
max = Math.max(max, nums[i]);
Collections.reverse(tmp);
}
lis.add(tmp);
}
int res = Integer.MAX_VALUE;
while (true) {
int[] min = pq.poll();
res = Math.min(res, max-min[2]);
if (min[1]+1 >= lis.get(min[0]).size()) {
break;
}
int next = lis.get(min[0]).get(min[1]+1);
pq.add(new int[]{min[0], min[1]+1, next});
max = Math.max(max, next);
}
return res;
}
解法二
public int minimumDeviation2(int[] nums) {
int INF = 0x3f3f3f3f;
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->b-a);
int min = INF;
for (int i = 0; i < nums.length; i++) {
if ((nums[i] & 1) == 1) {
nums[i] <<= 1;
}
min = Math.min(min, nums[i]);
pq.add(nums[i]);
}
int res = INF;
while (true) {
int max = pq.poll();
res = Math.min(res, max-min);
if ((max&1)==1) {
break;
}
pq.add(max/2);
min = Math.min(min, max/2);
}
return res;
}