滑动窗口算法学习
2023-06-13 09:14:26 时间
最近做了几道有关滑动窗口的算法,在此总结一下。
滑动窗口
- 就像描述的那样,可以理解成是一个会滑动的窗口,每次记录下窗口的状态,再找出符合条件的适合的窗口
- 可以使用滑动窗口来减少时间复杂度
经典滑动窗口题目
给一组大小为n的整数数组,计算长度为k的子数组的最大值 比如:数组{1,2,3,4,5,7,6,1,8},k=2,那么最终结果应该是7+6=13最大。 最简单的是使用两层遍历,通过所有情况找出最大的一个子数组,时间复杂度O(N^2) 使用滑动窗口,从[0,k-1]的一个窗口,记录其总和,然后窗口向右移动到[1,k],再到[2,k+1],直到数组的最尾端,找出里面总和最大的一个窗口,这样的解法就是滑动窗口算法。
//Java代码:
public class SlidingWindow {
public static int maxnum(int[] array,int k){
if(array.length<k){//如果k比数组长度还大,返回-1
return -1;
}
int left=0;
int sum=0;
for(int i=0;i<k;i++){
sum+=array[i];
}
int tempsum=sum;//tempsum记录每个窗口的总和
while (left+k<array.length){
tempsum=tempsum-array[left]+array[left+k];
left++;
sum=Math.max(sum,tempsum);//sum取原sum和tempsum的较大值
}
return sum;
}
public static void main(String[] args) {
int[] arr={1, 4, 2, 10, 2, 3, 1, 0, 20};
int k=3;
System.out.println(maxnum(arr,k));
}
}
字符串中的使用
- 问题描述: 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配,中间不能有其他字符
public class Matching {
public static List<Integer> findSubstring(String s,String[] words){
List<Integer> res=new ArrayList<>();
if(s==null||s.length()==0||words==null||words.length==0)
return res;
HashMap<String,Integer> map=new HashMap<>();//储存words字符数组,value值为出现的次数
int word=words[0].length();//每个子串的长度
int number=words.length;//子串的个数
for(String w:words){
map.put(w,map.getOrDefault(w,0)+1);//map中如果没有当前子串,则放入;如果有数目+1
}
for(int i=0;i<word;i++){
int left=i,right=i,count=0;
HashMap<String,Integer> temp=new HashMap<>();
while (right+word<=s.length()){
String match=s.substring(right,right+word);//滑动窗口
right+=word;
if(!map.containsKey(match)){
count=0;
left=right;
temp.clear();
}
else {
temp.put(match,temp.getOrDefault(match,0)+1);
count++;
while (temp.getOrDefault(match,0)>map.getOrDefault(match,0)){//如果匹配的个数多了,向右滑动word个字符
String match1=s.substring(left,left+word);
count--;
temp.put(match1,temp.getOrDefault(match1,0)-1);
left+=word;
}
if(count==number) res.add(left);
}
}
}
return res;
}
public static void main(String[] args) {
String s = "barfoothefoobarman";
String[] words = {"foo","bar"};
System.out.println(findSubstring(s,words));
}
}
- 问题描述:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 输入: “abcabcbb” 输出: 3
class Solution {
public int lengthOfLongestSubstring(String s) {
//使用HashSet作为滑动窗口,找出无重复字符的最长子串。
Set<Character> set=new HashSet<>();
int ans=0,i=0,j=0;//i为滑动窗口的左边,j为右边
while(i<s.length()&&j<s.length()){
if(!set.contains(s.charAt(j))){//如果没有重复
set.add(s.charAt(j++));
ans=Math.max(ans,j-i);
}
else{//如果出现重复
set.remove(s.charAt(i++));
}
}
return ans;
}
}
用滑动窗口用来解决求字符串,数组等连续的子串或子数组的问题比较简单。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
相关文章
- 机器学习十大经典算法之逻辑回归
- 为了测试未知来源的算法题,我写了一个本地刷题工具!
- 【干货书】深度强化学习Python实战:算法的简洁实现,简化数学,以及TensorFlow和PyTorch的使用
- Meanshift,聚类算法
- 神经网络是如何运用梯度下降算法进行学习
- 算法学习–整型转字符串
- 【算法学习】求得一定数值范围内的所有质数
- 机器学习算法:UMAP 深入理解
- 机器学习经典算法:决策树(2)
- 多智能体强化学习算法【三】【QMIX、MADDPG、MAPPO】
- 排序算法
- [量化投资]你的机器学习算法真的能准确预测股价吗?
- 机器学习(五):机器学习算法分类
- 机器学习算法: AdaBoost 详解
- A.机器学习入门算法(三):K近邻(k-nearest neighbors),鸢尾花KNN分类,马绞痛数据--kNN数据预处理+kNN分类pipeline
- 推荐系统遇上深度学习(十二)--推荐系统中的EE问题及基本Bandit算法
- java冒泡算法
- 算法-旋转字符串-暴力移位法详解编程语言
- 算法-数字在排序数组中出现的次数详解编程语言
- 算法-机器人的运动范围详解编程语言
- 不同路径算法详解编程语言
- Linux 中的加密技术:安全可靠的算法(linux加密算法)
- 深入浅出Oracle数据库算法(oracle数据库算法)
- 纯C语言:贪心Prim算法生成树问题源码分享