哪些网站是中文域名,joomla与wordpress学哪个好,搜索引擎优化seo培训,com域名注册商这里是Thembefue 今天讲解算法中较为经典的一个算法 滑动窗口 本讲解主要通过题目来讲解以理解算法 讲解分为三部分#xff1a;题目解析 算法讲解 编写代码 滑动窗口 在正式进入题目的讲解之前#xff0c;得先了解一下什么是滑动窗口#xff0c;以及应该在什… 这里是Thembefue 今天讲解算法中较为经典的一个算法 滑动窗口 本讲解主要通过题目来讲解以理解算法 讲解分为三部分题目解析 算法讲解 编写代码 滑动窗口 在正式进入题目的讲解之前得先了解一下什么是滑动窗口以及应该在什么情况下使用。 滑动窗口其实是由暴力遍历优化来的其本质也是双指针但这个双指针是利用数组等单调性同向移动的不会倒退使其像一个窗口一个从左向右滑动。 长度最小的子数组 题目解析 找到一个子数组使这个子数组的和大于等于给定的目标值子数组是数组上连续的一段一定是连续的 算法讲解 本题使用暴力遍历的时间复杂度位O(n*2)所以一定会超时。 所以我们在暴力遍历的基础上进行优化根据数组的单调性我们没必要在 left 指针向右移时让 right 指针重新回来再遍历一次这样会导致重复遍历徒增时间。 滑动窗口这个过程一般都分为四步进窗口判断出窗口更新结果。 其中更新结果可能在出窗口前也可能在出窗口后根据题目意思即可。 我们先维护一个 sum 变量用于表示当前窗口中所有元素的全部和当和大于等于 target时我们便可更新结果并且让此时应该让left 指向的元素出窗口。 编写代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int left 0, right 0;int sum 0, len Integer.MAX_VALUE;while (right nums.length) {// 进窗口sum nums[right];// 开始缩小窗口while (sum target) {len Math.min(len, right - left 1);sum - nums[left]; // 出窗口} right;}return len Integer.MAX_VALUE ? 0 : len;}
}
无重复字符的最长子串 题目解析 子串和子数组其实就是一个意思连续的一段子字符串且这段字符串不能出现重复的字符返回其最长子串。 算法讲解 本题需要借用一个数据结构来实现也即是哈希表哈希表记录某个字符出现的次数。 首先是进窗口操作也就是把当前字符放入到哈希表同时更新其出现的次数。 当出现了两次相同的字符时说明此子串不符合条件。此时 left 指针移动缩小窗口。 随后更新结果。 编写代码
class Solution {public int lengthOfLongestSubstring(String s) {int[] hash new int[128];int left 0, right 0;int len 0;while (right s.length()) {// 进窗口hash[s.charAt(right)];while (hash[s.charAt(right)] 1) {// 出窗口hash[s.charAt(left)]--;}// 更新数据len Math.max(len, right - left 1);right;}return len;}
} 最大连续1的个数 III 题目解析 同样是求符合条件的最长子数组但其实不用真的修改数组的元素不然要改回去就麻烦了。 算法讲解 我们可以使用一个计数器来统计此时窗口中0出现的次数0出现了多少次就要将其变成1多少次。所以进出窗口的操作大差不差。 但是有一个细节在出窗口时0计数器不能直接减小但 left指向的元素为0时才能减去否则 left一直减小直到 0计数器减小到题目条件时。 编写代码
class Solution {public int longestOnes(int[] nums, int k) {int zeroCount 0, ret 0;int left 0, right 0;while (right nums.length) {// 进窗口if (nums[right] 0) zeroCount;while (zeroCount k) {if (nums[left] 0) zeroCount--; // 出窗口}ret Math.max(ret, right - left);}return ret;}
} 将 x 减到 0 的最小操作数 题目解析 选取数组最左边或者最右边的元素从 x 中减去该元素直到将 x 减为0为止但得返回最小的操作次数。 注意只能选取最左边或者最右边的元素选过的元素从数组中删除不能再使用。 算法讲解 这题乍一看好像并不是滑动窗口因为一下操作左边一下操作右边并不能形成连续的一段。 但是看问题的角度有多种俗话说正难则反。假设我们现在选取了左边和右边的元素的一个假设此时这两个数字的和正好等于 x也就是满足题目的条件。 我们不难发现除去这两个数字剩下的元素其实构成了一个子数组也就是一个窗口且这个窗口的值等于数组所有元素的总和减去 x。 掌握了这个性质这题就迎刃而解了。 编写代码
class Solution {public int minOperations(int[] nums, int x) {int left 0, right 0;int ret -1;int sum 0;for (int i: nums) sum i;int target sum - x, temp 0;if (target 0) return -1;while (right nums.length) {// 进窗口temp nums[right];// 判断while (temp target) {temp - nums[left]; // 出窗口}if (temp target) ret Math.max(ret, right - left 1);right;}return ret -1 ? -1 : nums.length - ret;}
} 好了以上就是今天内容的全部讲解如果有不懂的地方随时私聊 我们下半部分见
