常见滑动窗口实现(Java 语言实现)
作者:秋名山码民
- 2022 年 6 月 06 日
本文字数:1023 字
阅读完需:约 3 分钟
滑动窗口,大家应该都不陌生吧,我们今天用 Java 语言来实现几个常见的滑动窗口题目
固定窗口
题目:给定一个整数数组 arr 和俩个整数 k 和 threshold,请你返回长度为 k 且平均值大于等于 threshold 的子数组的数目
package 滑动窗口;
import java.util.Scanner;
public class 固定窗口 {
public static void main(String[] args) {
// 俩个相邻的长度为4的窗口,下一个窗口一定比上一个窗口少一个数据,以及多另一个数据
// 直接沿用之前的数据,并且减去前面的,加上后来的,就是 下一个窗口的值!
//题目:给定一个整数数组arr和俩个整数k和threshold,请你返回长度为k且平均值大于等于threshold的子数组的数目
int[] arr1={1,2,3,4,5};
Scanner a = new Scanner(System.in);
int k = a.nextInt();
int threshold = a.nextInt();
int i,sum = 0, ret = 0;
threshold *= k;
for(i = 0; i<k; ++i){
sum += arr1[i];
//前k个
}
if(sum>=threshold) ++ret;
for(i = k; i<arr1.length; ++i){
sum-=arr1[i-k];
sum+=arr1[i];
if(sum>=threshold) ++ret;
}
System.out.println(ret);
}
}
复制代码
可变窗口
package 滑动窗口;
import org.w3c.dom.ls.LSOutput;
public class 可变窗口 {
//解决在s中最长不含重复子串的字符串
//1.定义一个滑动窗口,初始化为空窗口,也就是i= 0,j = -1
//2.然后,不断的向右移动滑动窗口的右边界,同时记录当前字符的出现次数,可以用一个哈希表来记录
//3.当第j个字符在哈希表中出现超过 1次 ,则移动滑动窗口的左边界,同时更新对应字符的出现次数,主要这里要循环迭代计算
//4.当右边界枚举到整个字符串结尾,则结束计算
public static void main(String[] args) {
int[] s = {1, 2, 3, 4, 5, 6, 7, 8};
int n = s.length;
int[] hash = new int[256];
int max = 0;
int i = 0, j = -1;
while (j < n - 1) {
++j;
++hash[s[j]];
while (hash[s[j]] > 1) {
--hash[s[i]];
++i;
}
if (j - i + 1 > max) {
max = j - i + 1;
}
}
System.out.println(max);
}
}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 4
版权声明: 本文为 InfoQ 作者【秋名山码民】的原创文章。
原文链接:【http://xie.infoq.cn/article/7394925c65728e9143cf33ef6】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
![用户头像](http://static001.geekbang.org/account/avatar/00/2a/f9/d9/4d1498a5.jpg?x-oss-process=image/resize,w_200,h_200)
秋名山码民
关注
卷不死,就往…… 2021.10.19 加入
2019NOIP退役成员,华为云享专家,阿里云专家博主,csdn博主,努力进行算法分享,有问题欢迎私聊
评论