滑动窗口不也挺好的吗.jpg
这个月大胆预测一波，这个月可能是leetcode的滑动窗口月，先提前开个坑（，毕竟上个月的查并集月已经在写了已经在写了（雾。
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
示例：
1
2
3
| 输入：[1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
|
提示：
- 1 <=
k <= n <= 30,000。
- 所给数据范围 [-10,000，10,000]。
非常典型的滑动窗口类型题目，不过暴力嘛很容易超时，当然如果你之前做过滑动窗口类型的题目的话，这题肯定一眼就看出来了.jpg。当然代码也在意料之中的很简单。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public double findMaxAverage(int[] nums, int k) {
int sum=0;
for (int i=0;i<k;i++){
sum+=nums[i];
}
double maxsum=sum;
for (int i=k;i<nums.length;i++){
sum=sum+nums[i]-nums[i-k];
maxsum=Math.max(sum,maxsum);
}
return maxsum/k;
}
}
|
给你两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
示例 1：
1
2
3
| 输入：s = "abcd", t = "bcdf", cost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。
|
示例 2：
1
2
3
| 输入：s = "abcd", t = "cdef", cost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。
|
示例 3：
1
2
3
| 输入：s = "abcd", t = "acde", cost = 0
输出：1
解释：你无法作出任何改动，所以最大长度为 1。
|
提示：
1 <= s.length, t.length <= 10^50 <= maxCost <= 10^6s 和 t 都只含小写英文字母。
这题也是滑动窗口类型的题耶，滑动窗口月实锤！！！！，这题也是滑动窗口诶，这题的滑动窗口使用双指针来维护，right指针不变，让left指针来缩小范围即可，简单题我重拳出击，困难题我唯唯诺诺（。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int cost = 0, right = 0, left = 0, maxLength = 0;
while (right < s.length()) {
cost += Math.abs(s.charAt(right) - t.charAt(right));
while (cost > maxCost) {
cost -= Math.abs(s.charAt(left) - t.charAt(left));
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
right++;
}
return maxLength;
}
}
|
ps：有人指出这题严格来说不算是滑动窗口，严格来说应该是双指针，两者的区别在于「滑动窗口」是一类问题本身，「双指针」是解决一类二分查找问题的通用优化方法。或者说滑动窗口」本身并不是解决问题的一种方法（或者说算法），它其实就是这个问题本身。我们需要做的是寻找合适的数据结构来「维护」这个「滑动窗口」，比如说第一题典型的滑动窗口
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例 1：
1
2
3
| 输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
|
示例 2：
1
2
3
| 输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
|
示例 3：
1
2
3
| 输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
|
示例 4：
1
2
3
| 输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
|
示例 5：
1
2
| 输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202
|
提示：
1 <= cardPoints.length <= 10^51 <= cardPoints[i] <= 10^41 <= k <= cardPoints.length
emmmmm这题我一开始就陷入了误区，慌慌忙忙开始敲代码，这题既然求最大的点数之和，我们只需要维护最小的滑动窗口就行了，知道了这点之后就变得很简单了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length;
int windowSize = n - k;
int sum = 0;
for (int i = 0; i < windowSize; ++i) {
sum += cardPoints[i];
}
int minSum = sum;
for (int i = windowSize; i < n; ++i) {
sum += cardPoints[i] - cardPoints[i - windowSize];
minSum = Math.min(minSum, sum);
}
return Arrays.stream(cardPoints).sum() - minSum;
}
}
|
当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时，我们称其为湍流子数组：
- 若
i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；
- 或 若
i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。
也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
返回 A 的最大湍流子数组的长度。
示例 1：
1
2
3
| 输入：[9,4,2,10,7,8,8,1,9]
输出：5
解释：(A[1] > A[2] < A[3] > A[4] < A[5])
|
示例 2：
示例 3：
提示：
1 <= A.length <= 400000 <= A[i] <= 10^9
这题我们根据定义可能会存在arr[right-1]<arr[right]&&arr[right]>arr[right+1]或者arr[right-1]>arr[right]&&arr[right]<arr[right-1]，这两种情况需要把right向右移动一个单位，此外当无法满足这两种情况时需要另left=right。
当窗口的长度为1时，需要把left和right都右移一个单位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int maxTurbulenceSize(int[] arr) {
int n = arr.length;
int ret = 1;
int left = 0, right = 0;
while (right < n - 1) {
if (left == right) {
if (arr[left] == arr[left + 1]) {
left++;
}
right++;
} else {
if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
right++;
} else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
right++;
} else {
left = right;
}
}
ret = Math.max(ret, right - left + 1);
}
return ret;
}
}
|
给定一个二进制数组， 计算其中最大连续 1 的个数。
示例：
1
2
3
| 输入：[1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
|
提示：
- 输入的数组只包含
0 和 1 。
- 输入数组的长度是正整数，且不超过 10,000。
这题有了上面几题的经验和模板应该很容易看出来了.jpg
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int left = 0, right = 0;
int ans = 0;
while (right < nums.length) {
if (nums[right] == 1) {
right++;
} else {
right++;
left = right;
}
ans = Math.max(ans, right - left);
}
return ans;
}
}
|
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
1
2
3
4
5
| 输入：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：
1
2
3
4
5
| 输入：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
这题看了半天没想到怎么用滑动数组，这里其实不用去计算1的数量，我们只需要去维护0的数量小于2的滑动窗口就好了,想通了这一点之后就变得很简单了，代码的话是常规滑动数组的写法，也没什么好说的，总之就是很简单.jpg
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int longestOnes(int[] A, int K) {
int n = A.length;
int left = 0, lsum = 0, rsum = 0;
int ans = 0;
for (int right = 0; right < n; ++right) {
rsum += 1 - A[right];
while (lsum < rsum - K) {
lsum += 1 - A[left];
++left;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
|
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
示例：
1
2
3
4
5
| 输入：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
这题也是典型的滑动窗口，这题灵活的运用了数组customer和grumpy的关系，代码实现倒是很简单，弹前提是活用customer和grumpy的关系，代码实现倒是很常规
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int total = 0;
int n = customers.length;
for (int i = 0; i < n; i++) {
if (grumpy[i] == 0) {
total += customers[i];
}
}
int increase = 0;
for (int i = 0; i < X; i++) {
increase += customers[i] * grumpy[i];
}
int maxIncrease = increase;
for (int i = X; i < n; i++) {
increase = increase - customers[i - X] * grumpy[i - X] + customers[i] * grumpy[i];
maxIncrease = Math.max(maxIncrease, increase);
}
return total + maxIncrease;
}
}
|
这是二月最后一道滑动窗口题啦，这我我最后的波纹啦，jojo！！！！
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
示例 1：
1
2
3
| 输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
|
示例 2：
1
2
3
| 输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
|
提示：
1 <= s.length <= 104s 仅由小写英文字母组成1 <= k <= 105
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public int longestSubstring(String s, int k) {
int ans = 0;
int len = s.length();
char[] cs = s.toCharArray();
int[] cnt = new int[26];
for (int curKind = 1; curKind <= 26; curKind++) {
Arrays.fill(cnt, 0);
int left = 0, right = 0;
int totalKind = 0, sumKind = 0;
while (right < len){
int rightIndex = cs[right] - 'a';
cnt[rightIndex]++;
if (cnt[rightIndex] == 1) totalKind++;
if (cnt[rightIndex] == k) sumKind++;
while (totalKind > curKind) {
int leftIndex = cs[left] - 'a';
if (cnt[leftIndex] == 1) totalKind--;
if (cnt[leftIndex] == k) sumKind--;
cnt[leftIndex]--;
left++;
}
if (totalKind == sumKind) ans = Math.max(ans, right - left + 1);
right++;
}
}
return ans;
}
}
|
嗯这的确是leetcode本月最后一道滑动窗口题，二月最后一道滑动窗口题发出了它最后的波纹，二月的题我几乎每道题都打了，注意是几乎是几乎，也就是说还有几道因为大过年的懒得刷，还有令我唯唯诺诺的困难题，嗯！！！二月勋章没拿到呢！！！！
