新手seo网站做什么类型好,网站后台文章添加成功 不显示,wordpress商城制作,沈阳关键词优化费用滑动窗口模板//滑动窗口模板#xff1a;注意使用滑动窗口方法#xff0c;使用一个 for(while) 循环中的变量是用来控制终止位置的//最小滑窗#xff1a;给定数组 nums#xff0c;定义滑动窗口的左右边界 i、j#xff0c;求满足某个条件的滑窗的最小长度
for(j 0; j …滑动窗口模板//滑动窗口模板注意使用滑动窗口方法使用一个 for(while) 循环中的变量是用来控制终止位置的//最小滑窗给定数组 nums定义滑动窗口的左右边界 i、j求满足某个条件的滑窗的最小长度
for(j 0; j nums.length; j) {不断的添加值到题中要求的结果集中(比如 sum)while(满足条件) {更新求最小长度 result Math.min(result,j-i1);不断更新结果集(比如 sum)i; // 缩小左边界}
}//最大滑窗给定数组 nums定义滑窗的左右边界 i、j求满足某个条件的滑窗的最大长度
for(j 0; j nums.length; j) {不断的添加值到题中要求的结果集中(比如 sum)while(不满足条件) {i; // 缩小左边界不断更新结果集(比如 sum)}// 走到这里条件满足更新最小长度继续 for 循环更新求最小长度 result Math.min(result,j-i1);
}1. 长度最小的子数组题目链接209. 长度最小的子数组 - 力扣LeetCode给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。示例 1输入target 7, nums [2,3,1,2,4,3]输出2解释子数组 [4,3] 是该条件下的长度最小的子数组。示例 2输入target 4, nums [1,4,4]输出1示例 3输入target 11, nums [1,1,1,1,1,1,1,1]输出0提示1 target 1091 nums.length 1051 nums[i] 105进阶如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。思想滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出想要的结果使用暴力解法是一个 for 循环滑动窗口的起始位置一个 for 循环为滑动窗口的终止位置用两个 for 循环完成一个不断搜索区间的过程。而滑动窗口是用一个 for 循环来完成这个操作并且这个 for 表示的应该是终止位置因为如果这个 for 表示的是起始位置那么如何遍历剩下的终止位置呢到最后还是又回到了暴力解法所以 滑动窗口使用一个 for 循环来表示滑动窗口的终止位置使用滑动窗口需要确定三点窗口内是什么窗口就是满足 sum targe 长度的最小的连续子数组如何移动窗口的起始位置起始位置就是 如果当前窗口的值大于 targe窗口就要向前移动了缩小范围如何移动窗口的结束位置结束位置就是 for 循环中的索引滑动窗口的优点在于能够根据当前子序列和大小的情况不断调节子序列的起始位置在这道题中也就是满足sum target 时起始位置就要开始移动从而将 O(n^2) 暴力解法时间复杂度降为 O(n)滑动窗口 // 209public int minSubArrayLen(int target, int[] nums) {int i 0; //左int result Integer.MAX_VALUE;int sum 0;for (int j 0; j nums.length; j) { // 右sum nums[j];while(sum target) { // while 循环找到满足要求且元素个数最小的result Math.min(result,j-i1);sum - nums[i];}}return result Integer.MAX_VALUE ? 0 : result;}2. 水果成篮题目链接904. 水果成篮 - 力扣LeetCode你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果你只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘你必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。给你一个整数数组 fruits 返回你可以收集的水果的 最大 数目。示例 1输入fruits [1,2,1]输出3解释可以采摘全部 3 棵树。示例 2输入fruits [0,1,2,2]输出3解释可以采摘 [1,2,2] 这三棵树。如果从第一棵树开始采摘则只能采摘 [0,1] 这两棵树。示例 3输入fruits [1,2,3,2,2]输出4解释可以采摘 [2,3,2,2] 这四棵树。如果从第一棵树开始采摘则只能采摘 [1,2] 这两棵树。示例 4输入fruits [3,3,3,1,2,1,1,2,3,3,4]输出5解释可以采摘 [1,2,1,1,2] 这五棵树。提示1 fruits.length 1050 fruits[i] fruits.length思想在上一题长度最小的子数组中是要求满足条件的子数组的最小长度用滑动窗口的方法来说就是最小滑窗是在迭代右移左边界的过程中更新结果。而本道题水果成篮是要求满足条件情况下收集水果的最大数目也就是要在迭代右移右边界的过程中更新结果。利用 left 和 right 分别表示窗口的左右边界同时利用哈希表来存储这个窗口内的数以及出现的次数一个 for 循环控制的就是终止位置也就是右边界右移一个位置并且将 fruits[right] 加入到哈希表中如果 哈希表大小大于2也就是水果的种类那就移动 left 将 fruits[left] 从哈希表中移除直到满足要求并且当 fruits[left] 在哈希表中出现的次数减少为0那就将 key 移除代码public int totalFruit(int[] fruits) {int n fruits.length;MapInteger,Integer cnt new HashMap();int left 0, ans 0;for(int right 0; right n; right) {// 每次添加一个水果计数cnt.put(fruits[right],cnt.getOrDefault(fruits[right],0) 1);// 如果添加新水果后不止两种就从前往后逐渐丢弃水果while(cnt.size() 2) {int pre fruits[left];cnt.put(pre,cnt.get(pre) - 1);// 如果这种水果被全部丢弃就从 map 中删除if(cnt.get(pre) 0) {cnt.remove(pre);}}// 计算一下当前区域的长度ans Math.max(ans,right-left1);}return ans;
}3. 最小的覆盖子串题目链接76. 最小覆盖子串 - 力扣LeetCode给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。注意对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串我们保证它是唯一的答案。示例 1输入s ADOBECODEBANC, t ABC输出BANC解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。示例 2输入s a, t a输出a解释整个字符串 s 是最小覆盖子串。示例 3:输入: s a, t aa输出: 解释: t 中两个字符 a 均应包含在 s 的子串中因此没有符合条件的子字符串返回空字符串。提示m s.lengthn t.length1 m, n 105s 和 t 由英文字母组成**进阶**你能设计一个在 o(mn) 时间内解决此问题的算法吗思想还是按滑动窗口的思路来做不断增加 j 使滑动窗口增大直到窗口包含了 T 中所有元素不断增加 i 使用滑动窗口缩小因为是要求最小子串所以要将不必要的元素排除在外使用长度减小直到遇到一个必须包含的元素那么此时就记录这个滑动窗口的长度并且保存最小值也就是保存左边界然后可以根据长度计算右边界从而可以返回子串让 i 再向右移动一个位置那么这个时候滑动窗口肯定是不满足条件的就重新从步骤1 开始执行寻找新的满足条件的滑动窗口判断滑动窗口中包含了 T 的所有元素这里可以用一个字典 need 也就是数组来表示滑动窗口中需要的各个元素的数量int[] need new int[128] 这个数组大小设为 128 是因为 ascii 中有 128 个字符比如 need[76] 2表示 ascii 为 76 的这个字符在字符串中需要两个比如 need[76] -2表示 ascii 为 76 的这个字符在字符串中多余两个。先把用 T 把 need 数组初始化表示现在need[X] ? 需要这些元素下面就是通过滑动窗口来修改need 数组中的元素当滑动窗口中包含某个元素就让 need 元素减1代表需要的元素减1当滑动窗口移除某个元素就让 need 中元素的数量加1这样做的目的就是为了步骤2中的 排除不必要元素数量为负表示不必要元素数量为 0 表示刚刚好need 数组中记录着当前滑动窗口中需要的元素数量这个动态修改是靠滑动窗口的移动来维护的总之如何判断滑动窗口中包含了 T 的所有元素这是根据 need 中所有元素的数量都小于或等于 0 时表示当前滑动窗口不需要任何元素但是还有个细节每次判断滑动窗口是否包含 T 的所有元素都是去判断 need 所有元素数量都小于等于0这样还是要遍历 need 的这个是要耗费时间的所以可以**定义一个变量 needCnt 来记录当前需要元素的总数量**当遇到所需元素 c那 need[c] 就减1同时 needCnt 也减1这样就不用每次都来遍历 need 数组了只需要看 needCnt 就行代码public String minWindow(String s, String t) {// need 数组表示每个字符在 t 中需要的数量// need[76]2 表示 ascii为76的字符在目标字符串中需要两个int[] need new int[128];// 用 t 来初始化 need 【初始状态】for(int i 0; i t.length(); i) {need[t.charAt(i)];}/*left/right: 窗口左右边界size: 表示窗口的长度needCnt: 表示当前所需字符的总数起始大小为 t 的长度start表示有效窗口的起始位置可以根据size来求子串区间范围*/int left 0, size Integer.MAX_VALUE, needCnt t.length(), start 0;for(int right 0; right s.length(); right) {char c s.charAt(right);// 【步骤一】// 如果当前这个字符 c 在 t 中存在那么 need 中对应位置应该是大于 0if(need[c] 0) {needCnt--; // 找到一个元素了所需字符总数-1}// 不论这个字符是否在 t 中都要 -1.need[c]--;if(needCnt 0) {// 【步骤二】// 缩小左边界去除无用的元素while(left right need[s.charAt(left)] 0) {need[s.charAt(left)];left;}// 更新窗口的长度if(right - left 1 size) {size right - left 1;start left;}// 【步骤三】need[s.charAt(left)];left;needCnt;}}return size Integer.MAX_VALUE ? : s.substring(start,startsize);
}
