当前位置： 首页 > article >正文

算法: 滑动窗口题目练习

article 2024/9/27 15:30:28

文章目录

  • 滑动窗口
    • 长度最小的子数组
    • 无重复字符的最长子串
    • 最大连续1个个数 III
    • 将x减到0的最小操作数
    • 水果成篮
    • 找到字符串中所有字母异位词
    • 串联所有单词的子串
    • 最小覆盖子串
  • 总结

滑动窗口

长度最小的子数组

在这里插入图片描述
做这道题时,脑子里大概有个印象,知道要用滑动窗口,但是对于滑动窗口为什么就对,不会落情况吗?对于这一点不是很清楚.

emmm虽然独自做出来了,但是还是在怀疑滑动窗口的正确性.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(int right = 0; right < nums.length;right++) {
            sum += nums[right];
            if(sum >= target) {
                while(sum >= target) {
                    sum -= nums[left++];
                }
                int tmp = right - left + 2;
                if(min > tmp) {
                    min = tmp;
                }
            }
        }
        return min==Integer.MAX_VALUE?0:min;
    }
}

看完题解后,明白了.
在这里插入图片描述
看题解后的代码:

  • 使用了Math.min(),加快了做题速度,在比赛中可以省下时间.
  • 其他的都差不多~
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(int right = 0; right < nums.length;right++) {
            sum += nums[right];
            while(sum >= target) {
                min = Math.min(min,right-left+1);
                sum -= nums[left++];
            }
        }
        return min==Integer.MAX_VALUE?0:min;
    }
}

无重复字符的最长子串

在这里插入图片描述
自己使用滑动窗口+哈希表做出来了.
最开始想只用滑动窗口解决,结果想不出来.然后就想到了hash.
刚开始写时没写对,后来画了两次图,根据图,然后就写出来了~

看题解前:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        int n = s.length();
        char[] ss = s.toCharArray();
        boolean[] hash = new boolean[1080];
        int left = 0,right = 0;
        while (right < n) {
            if(!hash[ss[right]]) {
                hash[ss[right++]] = true;
                max = Math.max(max,right-left);
            }else {
                hash[ss[left++]] = false;
            }
        }
        return max;
    }
}

看题解后:

  • 我用的boolean,他用的int.都差不多吧.
  • 还有就是我的hash数组给大了.
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        int n = s.length();
        char[] ss = s.toCharArray();
        int[] hash = new int[128];
        int left = 0,right = 0;
        while (right < n) {
            hash[ss[right]]++;
            while(hash[ss[right]] > 1) {
                hash[ss[left++]]--;
            }
            max = Math.max(max,right-left+1);
            right++;
        }
        return max;
    }
}

最大连续1个个数 III

在这里插入图片描述
自己写的代码,能过,但是看起来不美观,效率也不够高.

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0, right = 0;
        int n = nums.length;
        int max = 0;
        while (right < n) {
            if (nums[right] == 1) {
                max = Math.max(max, right - left + 1);
                right++;
            }else{
                if (k > 0) {
                    max = Math.max(max, right - left + 1);
                    right++;
                    k--;
                } else {
                    while(nums[left]==1) {
                        left++;
                    }
                    k++;
                    left++;
                }
            }
        }
        return max;
    }
}

看题解:

  • emm,只能说没有对比,就没有伤害.人家写的代码又少又快~
  • 题解使用了for循环,这样可以少写几个if,比如说当nums[right]==1时,我们可以忽略,自动让right++就行;
  • 与我写的不同的是,他的k可以小于0,而我的k不能.
class Solution {
    public int longestOnes(int[] nums, int k) {
        int max = 0;
        for(int right = 0,left = 0;right < nums.length;right++) {
            if(nums[right] == 0) k--;
            while(k < 0) 
                if(nums[left++] == 0) k++;
            max = Math.max(max,right-left+1);
        }
        return max;
    }
}

翻了翻题解,发现还有高手!
以下是大佬的题解.
难理解的地方在于为啥能直接返回 right - left.
滑动窗口，极简代码，新增图解

// 1
class Solution {
    public int longestOnes(int[] A, int K) {
        int left=0 ,right=0;
        while (right<A.length){
            if(A[right++]==0) K--;
            if(K < 0) {
                if(A[left++]==0) K++;
            }
        }
        return right-left;
    }
}

	
// 2
class Solution {
    public int longestOnes(int[] A, int K) {
        int left=0 ,right=0;
        while (right<A.length){
            K -= A[right++]^1;
            if(K < 0) K += A[left++]^1;
        }
        return right-left;
    }
}

作者：怕冷的三十三
链接：https://leetcode.cn/problems/max-consecutive-ones-iii/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

将x减到0的最小操作数

在这里插入图片描述

刚开始看到题目确实感觉难以下手,"移除数组 nums 最左边或最右边的元素"这是什么鬼???

后来想了想,我们只需要让 数组中剩下的元素 = 原始数组中全部元素的和 - x . 就行了.
这道题目也就变成了寻找能满足上面的条件时,数组的最大值.
找到这个最大值然后让 数组的原始长度 - 最大值,就可以得到最小操作数啦~

但是有个坑(踩了两次qwq)

  • 当 原始数组中全部元素的和 - x == 0 时,说明此时不需要进行任何操作(因为元素都是正数),直接返回数组长度就OK
  • 当 原始数组中全部元素的和 - x < 0 时,说明把数组中的所有元素凑起来也凑不出x.此时直接返回-1.

错了好几次,通过不断地画图,分析,总算是做出来了~
代码:

class Solution {
    public int minOperations(int[] nums, int x) {
        int max = 0;
        int left = 0;
        int right = 0;
        int sum = 0;
        int sum2 = 0;
        for (int i = 0; i < nums.length; i++) sum2 += nums[i];
        
        sum2 -= x;
        
        if (sum2 < 0) return -1;
        if (sum2 == 0) return nums.length;
        while (right < nums.length) {
            if (sum < sum2) {
                sum += nums[right++];
            }
            while (sum > sum2) {
                sum -= nums[left++];
            }
            if (sum == sum2) {
                max = Math.max(max, right - left);
                sum -= nums[left++];
            }
        }
        return max == 0 ? -1 : nums.length - max;
    }
}

在这里插入图片描述

看了题解,跟我写的差不多,但是我写的还有可以优化的地方.

优化后:

class Solution {
    	public int minOperations(int[] nums, int x) {
		int max = 0;
		int left = 0;
		int right = 0;
		int sum = 0;
		int sum2 = 0;
		for (int i = 0; i < nums.length; i++) sum2 += nums[i];

		sum2 -= x;

		if (sum2 < 0) return -1;
		if (sum2 == 0) return nums.length;
		while (right < nums.length) {
			sum += nums[right++];

			while (sum > sum2)
				sum -= nums[left++];
			if (sum == sum2)
				max = Math.max(max, right - left);
		}
		return max == 0 ? -1 : nums.length - max;
	}
}

水果成篮

在这里插入图片描述
emmm,太久没用HashMap了,都快不会用了.

class Solution {
    public int totalFruit(int[] fruits) {
        int max = 0;
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for(int left=0,right=0; right < fruits.length;right++) {
            hashMap.put(fruits[right],hashMap.getOrDefault(fruits[right],0)+1);
            while(hashMap.size() > 2) {
                hashMap.put(fruits[left],hashMap.get(fruits[left])-1);
                if(hashMap.get(fruits[left]) == 0)
                    hashMap.remove(fruits[left]);
                left++;
            }
            max = Math.max(max,right-left+1);
        }
        return max;   
    }
}

还可以不使用HashMap,因为它给出了
0 <= fruits[i] < fruits.length
可以使用数组来模拟.
多定义了一个 kinds 变量,用来统计水果的种类.

	public int totalFruit2(int[] fruits) {
		int max = 0;
		int n = fruits.length;
		int[] hashMap = new int[n + 1];
		for (int left = 0, right = 0, kinds = 0; right < fruits.length; right++) {
			int in = fruits[right];
			if (hashMap[in] == 0) kinds++;
			hashMap[in]++;

			while (kinds > 2) {
				int out = fruits[left];
				hashMap[out]--;
				if (hashMap[out] == 0)
					kinds--;
				left++;
			}
			max = Math.max(max, right - left + 1);
		}
		return max;
	}

找到字符串中所有字母异位词

在这里插入图片描述
没写出来,最开始是想用两个hashMap,后来写着写着,又改成使用一个hashMap一个数组模拟.再然后又改成一个数组模拟,emmm改来改去,把自己绕晕了~

看了看题解,发现没有我想的那么复杂.
最开始想的是从窗口里一个一个对比P中出现的字符.搞了半天,没写出来.

其实只需要将窗口的长度固定下来就OK.

  1. 入窗口,hash[in]++.
  2. 判断一下right-left+1 是否大于 p字符串的长度.
    • 大于,出窗口
  3. 判断是否要更新结果(right - left + 1 == p字符串的长度)
    • 相等,比较两个hash表中的字符出现次数.如果完全一致,那就更新结果.

也有一些小坑:

  • 字符串s的长度必须要大于字符串p的长度,不然不可能有结果.
  • 如果使用数组模拟hash表,并且设置数组大小为26.那么别忘了要 -'a'.
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
		List<Integer> list = new ArrayList<>();
		int n1 = s.length(), n2 = p.length();
		if (n1 < n2)
			return list;
		char[] ss = s.toCharArray();
		int[] hash = new int[26];
		int[] hashP = new int[26];
		for (int i = 0; i < n2; i++) {
			hashP[p.charAt(i) - 'a']++;
		}

		for (int left = 0, right = 0; right < n1; right++) {
			char in = ss[right];
			hash[in - 'a']++;

			if (right - left + 1 > n2) {
				char out = ss[left++];
				hash[out - 'a']--;
			}

			if (right - left + 1 == n2) {
				int i = 0;
				for (; i < 26; i++) {
					if (hash[i] != hashP[i]) {
						break;
					}
				}
				if (i >= 26) {
					list.add(left);
				}
			}
		}

		return list;
	}
}

在以上代码的基础上做一下优化~

上述代码中,在检查两个hash表中的内容是否相等时,用的方法不是很好.
这道题给出了s串和p串中只有小写字母.由于小写字母只有26个,所以检查起来很快.
但是接下来还有一道题目,让你判断两个字符串,如果还是用上面的方法,那就会超时~

具体的优化思路:

维护一个count,count用来记录"有效字符个数".

具体一点:

  1. 进窗口: 如果hash[in] <= hashP[in],那么count++.
  2. 出窗口: 如果hash[out] <= hashP[out],那么count–;
  3. 更新结果: 如果count == p串长度,更新结果.

坑:

  • 注意count维护的时机.

优化后:

class Solution {
    public List<Integer> findAnagrams2(String s, String p) {
		List<Integer> list = new ArrayList<>();
		int n1 = s.length(), n2 = p.length();
		if (n1 < n2)
			return list;
		char[] ss = s.toCharArray();
		int[] hash = new int[26];
		int[] hashP = new int[26];
		for (int i = 0; i < n2; i++) {
			hashP[p.charAt(i) - 'a']++;
		}
		int count = 0;
		for (int left = 0, right = 0; right < n1; right++) {
			int in = ss[right] - 'a';
			hash[in]++;
			if (hash[in] <= hashP[in]) count++;

			if (right - left + 1 > n2) {
				int out = ss[left++] - 'a';
				if (hash[out] <= hashP[out]) count--;
				hash[out]--;
			}

			if (count == n2) {
				list.add(left);
			}
		}

		return list;
	}
}

串联所有单词的子串

在这里插入图片描述
尝试了两次,没写出来.

  • 想不到,可以这样写.
  • String/StringBuilder 中有的方法不知道,而且用的不熟练.比如说substring.
  • 在出窗口这里卡了一下.

看完题解后,自己写出来的代码:
count 的位置和加减容易写错.

public List<Integer> findSubstring(String s, String[] words) {
		List<Integer> list = new ArrayList<>();
		int lenS = s.length();
		int lenWords = words.length;
		int lenWord = words[0].length();
		HashMap<String, Integer> hashWords = new HashMap<>();
		for (String str : words)
			hashWords.put(str, hashWords.getOrDefault(str, 0) + 1);

		for (int i = 0; i < lenWord; i++) {
			HashMap<String, Integer> hashS = new HashMap<>();
			int count = 0;
			for (int left = i, right = i + lenWord; right <= lenS; right += lenWord) {
				String in = s.substring(right - lenWord, right);
				hashS.put(in, hashS.getOrDefault(in, 0) + 1);
				if (hashS.get(in) <= hashWords.getOrDefault(in, 0))
					count++;
				if (right - left > lenWord * lenWords) {
					String out = s.substring(left, left + lenWord);
					if (hashS.get(out) <= hashWords.getOrDefault(out, 0))
						count--;
					hashS.put(out, hashS.get(out) - 1);
					left += lenWord;
				}
				if (count == lenWords)
					list.add(left);
			}
		}
		return list;
	}

题解代码:

class Solution {
 public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();//返回答案
        HashMap<String, Integer> hash1 = new HashMap<>();//hash1用来记录words中出现过的单词以及对应次数
        for (String str : words) {
            hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        }
        int len = s.length();
        int wordLength = words[0].length();
        int wordsLength = words.length;
        for (int i = 0; i < wordLength; i++) {
            HashMap<String, Integer> hash2 = new HashMap<>();
            for (int right = i, left = i, count = 0; right + wordLength <= len; right += wordLength) {
                String str = s.substring(right, right + wordLength);
                hash2.put(str, hash2.getOrDefault(str, 0) + 1);
                if (hash2.get(str) <= hash1.getOrDefault(str, 0)) {
                    count++;
                }
                if (right - left + 1 > wordLength * wordsLength) {
                    String str2 = s.substring(left, left + wordLength);
                    if (hash2.get(str2) <= hash1.getOrDefault(str2, 0)) {
                        count--;
                    }
                    hash2.put(str2,hash2.get(str2)-1);
                    left += wordLength;
                }
                if(count == wordsLength) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }
}

最小覆盖子串

在这里插入图片描述
emmm,怎么说呢,没写出来,但是看完题解,发现我的代码只需要把一个if改成while就能过了,而且速度很快…

	class Solution {
		public String minWindow(String ss, String tt) {
			int min = Integer.MAX_VALUE;
			char[] s = ss.toCharArray();
			char[] t = tt.toCharArray();
			int len = tt.length();
			StringBuilder ret = new StringBuilder();
			int count = 0, left1 = 0, right1 = 0;
			int[] hashS = new int[58];
			int[] hashT = new int[58];
			for (char ch : t) hashT[ch - 'A']++;
			for (int right = 0, left = 0; right < s.length; right++) {
				int in = s[right] - 'A';
				hashS[in]++;
				if (hashS[in] <= hashT[in]) {
					count++;
				}
				while (count == len) {
					if (min > right - left + 1) {
						right1 = right;
						left1 = left;
						min = right - left + 1;
					}
					int out = s[left++] - 'A';
					if (hashS[out] <= hashT[out])
						count--;
					hashS[out]--;
				}
			}
			while (left1 <= right1) {
				ret.append(s[left1++]);
			}
			return min == Integer.MAX_VALUE ? "" : ret.toString();
		}
	}

总结

  1. 感觉滑动窗口本质上还是双指针,只不过是同向双指针.
  2. 使用滑动窗口时要用到单调性.
  3. 使用滑动窗口的套路就是:进窗口,出窗口,根据题意找个地方更新结果.
  4. 对于一些需要记录 单词出现次数/种类 的题目,可以定义一个count来优化代码.

本文到这里就结束啦~

在这里插入图片描述


http://www.kler.cn/news/321923.html

相关文章：

  • 搬砖5、Python构造程序逻辑
  • 【JavaScript】LeetCode：41-45
  • C#-__DynamicallyInvokable
  • 【深度学习基础模型】Autoencoders (AE) 详细理解并附实现代码。
  • 大数据：快速入门Scala+Flink
  • Iceberg 基本操作和快速入门
  • 8.11 矢量图层线要素单一符号使用四(短划线)
  • Java语言的Springboot框架+云快充协议1.5+充电桩系统+新能源汽车充电桩系统源码
  • 安全帽检测系统丨OPENAIGC开发者大赛高校组AI创作力奖
  • 机器学习实战：使用Python和scikit-learn构建预测模型
  • [单master节点k8s部署]27.Istio流量管理（三）
  • ElementUI el-tree 树组件 增加辅助线
  • Docker与Kubernetes学习
  • 网络基础概念和 socket 编程
  • 前端——js基础
  • 三维扫描 | 解锁低成本、高效率的工作秘籍
  • WPF项目中使用Caliburn.Micro框架实现日志和主题切换
  • 论文解析_客户分组对商业银行个人信用评分模型的提升作用研究，作者张亚京-中国人民银行征信中心博士后工作站
  • 数据仓库适用的业务场景
  • 【高分系列卫星简介】
  • 系统架构设计师 SOA与微服务架构篇
  • Spark-RDD持久化
  • IDEA2020运行项目时不从配置的maven仓库找jar包，从C盘默认路径下找jar包
  • 使用 React useEffect 实现条件判断的最佳实践
  • c语言200例 64
  • 示例说明：sql语法学习
  • 9.sklearn-K-means算法
  • 人员个体检测、PID行人检测、行人检测算法样本
  • c++----继承（初阶）
  • 开源 AI 智能名片 S2B2C 商城小程序与营销工具的快速迭代