文章目录
- 1456. 定长子串中元音的最大数目
- 2269. 找到一个数字的 K 美丽值
- 1984. 学生分数的最小差值（排序）
- 643. 子数组最大平均数 I
- 1343. 大小为 K 且平均值大于等于阈值的子数组数目
- 2090. 半径为 k 的子数组平均值
- 2379. 得到 K 个黑块的最少涂色次数
- 1052. 爱生气的书店老板
- 2841. 几乎唯一子数组的最大和
- 2461. 长度为 K 子数组中的最大和
- 1423. 可获得的最大点数（转换成找中间窗口最小）
- 2134. 最少交换次数来组合所有的 1 II
- 2653. 滑动子数组的美丽值⭐
- 解法1——利用二分维护窗口中的排序（超时了）
- 解法2——滑动窗口+暴力枚举 ⭐（牛逼的暴力枚举！🐂）
- 567. 字符串的排列
- 438. 找到字符串中所有字母异位词
- 2156. 查找给定哈希值的子串⭐⭐⭐
- 解法1——倒序滚动哈希
- 解法2——倒序滑动窗口 + O ( 1 ) O(1) O(1) 额外空间
- 小技巧，将'a'——'z'转成1——26 🐂
- 346. 数据流中的移动平均值（用队列维护窗口）
- 1100. 长度为 K 的无重复字符子串
题单来源：https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/solutions/2464878/hua-dong-chuang-kou-on-shi-jian-o1-kong-cqawc/
1456. 定长子串中元音的最大数目
https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/
提示：
1 <= s.length <= 10^5
s 由小写英文字母组成
1 <= k <= s.length
定长滑动窗口，进来一个加一个，出去一个减一个。
class Solution {
public int maxVowels(String s, int k) {
int n = s.length(), cnt = 0, ans = 0;
Set<Character> vowel = Set.of('a', 'e', 'i', 'o', 'u');
for (int l = 0, r = 0; r < n; ++r) {
if (vowel.contains(s.charAt(r))) cnt++;
if (r >= l + k) {
if (vowel.contains(s.charAt(l))) cnt--;
l++;
}
ans = Math.max(ans, cnt);
}
return ans;
}
}
2269. 找到一个数字的 K 美丽值
https://leetcode.cn/problems/find-the-k-beauty-of-a-number/
提示：
1 <= num <= 10^9
1 <= k <= num.length （将 num 视为字符串）
以240为例，
起初 x=100，y=1. 取出 240 % 100 / 1 = 40;
之后 x=1000，y=10 取出 240 % 1000 / 10 = 24;
class Solution {
public int divisorSubstrings(int num, int k) {
int ans = 0;
long x = 1, y = 1;
for (int i = 0; i < k; ++i) x *= 10;
for (; x / 10 <= num; x *= 10, y *= 10) {
long z = (long)num % x / y;
if (z != 0 && num % z == 0) ++ans;
}
return ans;
}
}
1984. 学生分数的最小差值（排序）
https://leetcode.cn/problems/minimum-difference-between-highest-and-lowest-of-k-scores/description/
排序之后的区间两边一定是一个最大值和一个最小值。
逐个枚举即可。
class Solution {
public int minimumDifference(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length, ans = nums[n - 1] - nums[0];
for (int l = 0, r = k - 1; r < n; ++l, ++r) {
ans = Math.min(ans, nums[r] - nums[l]);
}
return ans;
}
}
643. 子数组最大平均数 I
https://leetcode.cn/problems/maximum-average-subarray-i/description/
注意可能会溢出的问题。
class Solution {
public double findMaxAverage(int[] nums, int k) {
double ans = -10001, s = 0;
for (int l = 0, r = 0; r < nums.length; ++r) {
s += nums[r];
if (r - l + 1 == k) {
ans = Math.max(ans, s / k);
s -= nums[l++];
}
}
return ans;
}
}
1343. 大小为 K 且平均值大于等于阈值的子数组数目
https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/description/
提示：
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4
class Solution {
public int numOfSubarrays(int[] arr, int k, int threshold) {
int ans = 0;
long t = threshold * k, s = 0;
for (int i = 0; i < k - 1; ++i) s += arr[i];
for (int i = k - 1; i < arr.length; ++i) {
s += arr[i];
if (s >= t) ans++;
s -= arr[i - k + 1];
}
return ans;
}
}
2090. 半径为 k 的子数组平均值
https://leetcode.cn/problems/k-radius-subarray-averages/description/
提示：
n == nums.length
1 <= n <= 10^5
0 <= nums[i], k <= 10^5
用 s 维护长度为 2*k+1 窗口内所有值的总和。
class Solution {
public int[] getAverages(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
long s = 0, l = 2 * k + 1;
for (int i = 0; i < 2 * k && i < n; ++i) s += nums[i];
for (int i = 2 * k; i < n; ++i) {
s += nums[i];
ans[i - k] = (int)(s / l);
s -= nums[i - 2 * k];
}
return ans;
}
}
2379. 得到 K 个黑块的最少涂色次数
https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks/description/
提示：
n == blocks.length
1 <= n <= 100
blocks[i] 要么是 'W' ，要么是 'B' 。
1 <= k <= n
固定长度滑动窗口。
class Solution {
public int minimumRecolors(String blocks, int k) {
int ans = k, n = blocks.length(), s = 0;
for (int i = 0; i < k - 1; ++i) {
if (blocks.charAt(i) == 'W') s++;
}
for (int i = k - 1; i < n; ++i) {
if (blocks.charAt(i) == 'W') s++;
ans = Math.min(ans, s);
if (blocks.charAt(i - k + 1) == 'W') s--;
}
return ans;
}
}
1052. 爱生气的书店老板
https://leetcode.cn/problems/grumpy-bookstore-owner/description/
提示：
n == customers.length == grumpy.length
1 <= minutes <= n <= 2 * 10^4
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1
变量 s 维护长度为minutes的窗口中 生气时的顾客数量，这些顾客可以通过秘密技巧变得满意。
变量 total 计算本来就满意的顾客数量。
最后的答案是本来就满意的顾客数量+使用技巧变得满意的最多顾客数量。
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int n = customers.length, s = 0, mx = 0, total = 0;
for (int i = 0; i < minutes - 1; ++i) {
if (grumpy[i] == 1) s += customers[i];
else total += customers[i];
}
for (int i = minutes - 1; i < n; ++i) {
if (grumpy[i] == 1) s += customers[i];
else total += customers[i];
mx = Math.max(mx, s);
if (grumpy[i - minutes + 1] == 1) s -= customers[i - minutes + 1];
}
return total + mx;
}
}
2841. 几乎唯一子数组的最大和
https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/submissions/
提示：
1 <= nums.length <= 2 * 10^4
1 <= m <= k <= nums.length
1 <= nums[i] <= 10^9
用 s 维护和。
用 cnt 维护不同数字的种类数量。
class Solution {
public long maxSum(List<Integer> nums, int m, int k) {
long ans = 0, s = 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < k - 1; ++i) {
s += nums.get(i);
cnt.merge(nums.get(i), 1, Integer::sum);
}
for (int i = k - 1; i < nums.size(); ++i) {
s += nums.get(i);
cnt.merge(nums.get(i), 1, Integer::sum);
if (cnt.size() >= m) ans = Math.max(ans, s);
s -= nums.get(i - k + 1);
cnt.merge(nums.get(i - k + 1), -1, Integer::sum);
if (cnt.get(nums.get(i - k + 1)) == 0) cnt.remove(nums.get(i - k + 1));
}
return ans;
}
}
2461. 长度为 K 子数组中的最大和
https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k/description/
提示：
1 <= k <= nums.length <= 10^5
1 <= nums[i] <= 10^5
class Solution {
public long maximumSubarraySum(int[] nums, int k) {
long ans = 0, s = 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
s += nums[i];
cnt.merge(nums[i], 1, Integer::sum);
if (cnt.size() == k) ans = Math.max(ans, s);
if (i >= k - 1) {
int x = nums[i - k + 1];
s -= x;
cnt.merge(x, -1, Integer::sum);
if (cnt.get(x) == 0) cnt.remove(x);
}
}
return ans;
}
}
1423. 可获得的最大点数（转换成找中间窗口最小）
https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/description/
提示：
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
从两边拿要取最大，也就是找中间连续的最小。
可以使用固定长度滑动窗口。
class Solution {
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length, l = n - k, total = 0, s = 0, mn = Integer.MAX_VALUE;
if (l == 0) return Arrays.stream(cardPoints).sum();
for (int i = 0; i < n; ++i) {
s += cardPoints[i];
total += cardPoints[i];
if (i >= l - 1) {
mn = Math.min(mn, s);
s -= cardPoints[i - l + 1];
}
}
return total - mn;
}
}
2134. 最少交换次数来组合所有的 1 II
https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/description/
提示：
1 <= nums.length <= 10^5
nums[i] 为 0 或者 1
最后所以的 1 一定会相邻。
所以转换成求固定长度窗口中 1 出现的最大值，其它不在窗口中的 1 都需要交换过来。
class Solution {
public int minSwaps(int[] nums) {
int k = Arrays.stream(nums).sum(), mx = 0, s = 0, n = nums.length;
for (int x = 0; x < 2 * n; ++x) {
int i = x % n;
s += nums[i];
if (x >= k - 1) {
mx = Math.max(mx, s);
s -= nums[(x - k + 1) % n];
}
}
return k - mx;
}
}
2653. 滑动子数组的美丽值⭐
https://leetcode.cn/problems/sliding-subarray-beauty/description/
提示：
n == nums.length
1 <= n <= 10^5
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50
解法1——利用二分维护窗口中的排序（超时了）
class Solution {
public int[] getSubarrayBeauty(int[] nums, int k, int x) {
int n = nums.length;
List<Integer> ls = new ArrayList<>();
int[] ans = new int[n - k + 1];
for (int i = 0; i < n; ++i) {
int t = nums[i];
int id = bs(ls, t);
ls.add(id, t);
if (ls.size() > k) {
id = bs(ls, nums[i - k]);
ls.remove(id);
}
if (ls.size() == k) {
if (ls.get(x - 1) < 0) ans[i - k + 1] = ls.get(x - 1);
else ans[i - k + 1] = 0;
}
}
return ans;
}
public int bs(List<Integer> ls, int t) {
int l = 0, r = ls.size();
while (l < r) {
int mid = l + r >> 1;
if (ls.get(mid) < t) l = mid + 1;
else r = mid;
}
return l;
}
}
把 ArrayList 换成 LinkedList 超时会更多。
解法2——滑动窗口+暴力枚举 ⭐（牛逼的暴力枚举！🐂）
https://leetcode.cn/problems/sliding-subarray-beauty/solutions/2241294/hua-dong-chuang-kou-bao-li-mei-ju-by-end-9mvl/
虽然是暴力枚举，但是充分利用了数值的值域很小的特性。
class Solution {
public int[] getSubarrayBeauty(int[] nums, int k, int x) {
final int BIAS = 50;
int[] cnt = new int[BIAS * 2 + 1]; // 计数数组
int n = nums.length;
int[] ans = new int[n - k + 1];
for (int i = 0; i < n; ++i) {
cnt[nums[i] + BIAS]++; // 进入窗口
if (i >= k - 1) { // 计算该位置的答案
int left = x; // 计算剩余的x
for (int j = 0; j < BIAS; ++j) {
left -= cnt[j];
if (left <= 0) { // 找到了答案
ans[i - k + 1] = j - BIAS;
break;
}
}
--cnt[nums[i - k + 1] + BIAS]; // 移出窗口
}
}
return ans;
}
}
567. 字符串的排列
https://leetcode.cn/problems/permutation-in-string/description/
提示：
1 <= s1.length, s2.length <= 10^4
s1 和 s2 仅包含小写字母
如果 s1 的排列之一是 s2 的 子串。那么应该满足 s2 的一个字串中，各个字符的数量和 s1 相同。
用计数数组维护窗口中各个字符的数量即可。
class Solution {
public boolean checkInclusion(String s1, String s2) {
int[] cnt = new int[128];
for (char ch: s1.toCharArray()) cnt[ch]++;
for (int l = 0, r = 0; r < s2.length(); ++r) {
cnt[s2.charAt(r)]--;
if (r - l >= s1.length()) cnt[s2.charAt(l++)]++;
boolean f = true;
for (char ch = 'a'; ch <= 'z'; ++ch) {
if (cnt[ch] != 0) {
f = false;
break;
}
}
if (f) return true;
}
return false;
}
}
438. 找到字符串中所有字母异位词
https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
提示:
1 <= s.length, p.length <= 3 * 10^4
s 和 p 仅包含小写字母
维护 s 中长度等于 p 的滑动窗口，检查 窗口中的各个字符数量和 p 中的字符数量是否相等即可。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<>();
int[] cnt = new int[128];
for (char ch: p.toCharArray()) cnt[ch]++;
for (int l = 0, r = 0; r < s.length(); ++r) {
cnt[s.charAt(r)]--;
if (r - l >= p.length()) cnt[s.charAt(l++)]++;
boolean f = true;
for (char ch = 'a'; ch <= 'z'; ++ch) {
if (cnt[ch] != 0) {
f = false;
break;
}
}
if (f) ans.add(l);
}
return ans;
}
}
2156. 查找给定哈希值的子串⭐⭐⭐
https://leetcode.cn/problems/find-substring-with-given-hash-value/description/
提示：
1 <= k <= s.length <= 2 * 10^4
1 <= power, modulo <= 10^9
0 <= hashValue < modulo
s 只包含小写英文字母。
测试数据保证一定 存在 满足条件的子串。
解法1——倒序滚动哈希
https://leetcode.cn/problems/find-substring-with-given-hash-value/solutions/1249153/cha-zhao-gei-ding-ha-xi-zhi-de-zi-chuan-fi8jd/
倒序处理，
先处理出
p
o
w
e
r
(
k
−
1
)
m
o
d
m
o
d
u
l
o
power^(k-1) \mod modulo
power(k−1)modmodulo。
class Solution {
public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
int n = s.length(), pos = -1;
// h:子串哈希值 mult:power^(k-1) mod modulo
long h = 0, mult = 1;
// 预处理最后一个子串的哈希值和 power^k mod modulo
for (int i = n - 1; i >= n - k; --i) {
h = (h * power + (s.charAt(i) - 'a' + 1)) % modulo;
if (i != n - k) {
mult = mult * power % modulo;
}
}
if (h == hashValue) pos = n - k;
// 向前计算哈希值并尝试更新下标
for (int i = n - k - 1; i >= 0; --i) {
h = ((h - (s.charAt(i + k) - 'a' + 1) * mult % modulo + modulo) * power + (s.charAt(i) - 'a' + 1)) % modulo;
if (h == hashValue) {
pos = i;
}
}
return s.substring(pos, pos + k);
}
}
解法2——倒序滑动窗口 + O ( 1 ) O(1) O(1) 额外空间
class Solution {
public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
int n = s.length(), pos = -1;
// h:子串哈希值 mult:power^(k-1) mod modulo
long h = 0, mult = 1;
// 预处理最后一个子串的哈希值和 power^k mod modulo
for (int i = n - 1; i >= n - k; --i) {
h = (h * power + (s.charAt(i) & 31)) % modulo;
if (i != n - k) {
mult = mult * power % modulo;
}
}
if (h == hashValue) pos = n - k;
// 向前计算哈希值并尝试更新下标
for (int i = n - k - 1; i >= 0; --i) {
h = ((h - (s.charAt(i + k) & 31) * mult % modulo + modulo) * power + (s.charAt(i) & 31)) % modulo;
if (h == hashValue) {
pos = i;
}
}
return s.substring(pos, pos + k);
}
}
小技巧，将’a’——'z’转成1——26 🐂
只需要 & 31 即可。
346. 数据流中的移动平均值（用队列维护窗口）
https://leetcode.cn/problems/moving-average-from-data-stream/description/
提示：
1 <= size <= 1000
-10^5 <= val <= 10^5
最多调用 next 方法 10^4 次
class MovingAverage {
Queue<Integer> q = new LinkedList<>();
int sz;
double sum;
public MovingAverage(int size) {
sz = size;
sum = 0;
}
public double next(int val) {
q.offer(val);
sum += val;
if (q.size() > sz) sum -= q.poll();
return sum / q.size();
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/
1100. 长度为 K 的无重复字符子串
https://leetcode.cn/problems/find-k-length-substrings-with-no-repeated-characters/description/
提示：
1 <= S.length <= 10^4
S 中的所有字符均为小写英文字母
1 <= K <= 10^4
维护长度为 k 的滑动窗口中各个字符出现的数量。
class Solution {
public int numKLenSubstrNoRepeats(String s, int k) {
int[] cnt = new int[128];
int ans = 0;
for (int l = 0, r = 0; r < s.length(); ++r) {
cnt[s.charAt(r)]++;
if (r - l >= k) cnt[s.charAt(l++)]--;
if (r >= k - 1 && check(cnt)) ans++;
}
return ans;
}
public boolean check(int[] cnt) {
for (char ch = 'a'; ch <= 'z'; ++ch) {
if (cnt[ch] > 1) {
return false;
}
}
return true;
}
}
![[DASCTF 2023 0X401七月暑期挑战赛] web刷题记录](https://img-blog.csdnimg.cn/direct/e5dc5afab49840299c7953a22f7a2817.png)
