【算法】滑动窗口题单——1.定长滑动窗口⭐

2023-11-29 02:20
文章标签 算法 窗口 滑动 题单 定长

本文主要是介绍【算法】滑动窗口题单——1.定长滑动窗口⭐，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 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. 查找给定哈希值的子串⭐⭐⭐
  • 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;               // 计算剩余的xfor (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 modulolong h = 0, mult = 1;// 预处理最后一个子串的哈希值和 power^k mod modulofor (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 modulolong h = 0, mult = 1;// 预处理最后一个子串的哈希值和 power^k mod modulofor (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;}
}

这篇关于【算法】滑动窗口题单——1.定长滑动窗口⭐的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/431097。

相关文章

springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
bat脚本启动git bash窗口,并执行命令方式

bat脚本启动git bash窗口,并执行命令方式

《bat脚本启动gitbash窗口,并执行命令方式》本文介绍了如何在Windows服务器上使用cmd启动jar包时出现乱码的问题,并提供了解决方法——使用GitBash窗口启动并设置编码,通过编写s... 目录一、简介二、使用说明2.1 start.BAT脚本2.2 参数说明2.3 效果总结一、简介某些情
阅读更多...
基于Redis有序集合实现滑动窗口限流的步骤

基于Redis有序集合实现滑动窗口限流的步骤

《基于Redis有序集合实现滑动窗口限流的步骤》滑动窗口算法是一种基于时间窗口的限流算法,通过动态地滑动窗口,可以动态调整限流的速率,Redis有序集合可以用来实现滑动窗口限流,本文介绍基于Redis... 滑动窗口算法是一种基于时间窗口的限流算法，它将时间划分为若干个固定大小的窗口，每个窗口内记录了该时间
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2