做下载网站赚钱吗,唐山海港经济开发区人才网,辽宁城乡和住房建设部网站,开发公司工程管理岗好还是设计岗好#x1f525;个人主页#xff1a; 中草药
#x1f525;专栏#xff1a;【算法工作坊】算法实战揭秘 #x1f456;一. 长度最小的子数组 题目链接#xff1a;209.长度最小的子数组 算法原理 滑动窗口
滑动窗口算法常用于处理数组/字符串等序列问题#xff0c;通过定义一… 个人主页 中草药
专栏【算法工作坊】算法实战揭秘 一. 长度最小的子数组 题目链接209.长度最小的子数组 算法原理 滑动窗口
滑动窗口算法常用于处理数组/字符串等序列问题通过定义一个窗口即一段连续的元素并根据某种条件动态调整窗口的左右边界来找到满足条件的子序列。
在这个问题中滑动窗口的具体应用如下 初始化设置两个指针 left 和 right均初始化为0表示窗口的左右边界。同时初始化 sum 为0用于累计窗口内元素的和minlen 设置为 Integer.MAX_VALUE用于记录符合条件的最小子数组长度。 扩展右边界不断将右指针 right 向右移动并将 nums[right] 加入到 sum 中这相当于不断扩大窗口右侧尝试包含更多的元素以满足和至少为 target 的条件。 收缩左边界当窗口内的元素和 sum 至少达到 target 时开始尝试缩小窗口左侧即增加 left 指针的值并从 sum 中减去移出窗口的元素 nums[left]。这个过程会持续进行直到 sum 小于 target确保每次收缩都检查当前窗口是否仍然满足条件。 更新最小长度在每次收缩窗口后即 sum 小于等于 target 时用当前窗口的长度right - left 1更新 minlen保持记录最短的满足条件的子数组长度。 遍历结束当右指针遍历完整个数组后检查 minlen 是否仍为初始值 Integer.MAX_VALUE如果是则说明没有找到满足条件的子数组返回0否则返回 minlen 作为结果。
时间复杂度与空间复杂度
时间复杂度O(n)其中n为数组 nums 的长度。每个元素最多被访问两次一次作为窗口扩展时加入一次作为窗口收缩时移除。空间复杂度O(1)只使用了固定数量的变量与输入数组大小无关。
综上所述这段代码利用滑动窗口算法高效地解决了寻找最小长度子数组使其和至少为目标值的问题。
代码
public int minSubArrayLen(int target, int[] nums) {int sum0,minlenInteger.MAX_VALUE;//无穷大for(int left0,right0;rightnums.length;right){sumnums[right];//进窗口while(sumtarget){//出窗口minlenMath.min(minlen,right-left1);sum-nums[left];}}if(minlenInteger.MAX_VALUE){return 0;}return minlen;}
举例
测试用例 [2,3,1,2,4,3]
初始状态
sum 0minlen Integer.MAX_VALUE初始化双指针left 0, right 0
执行过程
第一轮迭代
right0: sum nums[0] 2, 现在 sum 2, 不满足 sum targetright。right1: sum nums[1] 3, 现在 sum 5, 不满足 sum targetright。right2: sum nums[2] 1, 现在 sum 6, 不满足 sum targetright。right3: sum nums[3] 2, 现在 sum 8, 满足 sum target。
这时进入内部的 while 循环。
第一次窗口收缩
sum target计算子数组长度 right-left1 4更新 minlen Math.min(minlen, 4) 4。从 sum 中减去 nums[left] nums[0] 2得到 sum 6继续在循环内检查。再次检查 sum target是的所以继续收缩。从 sum 中减去 nums[left] nums[1] 3得到 sum 3现在 sum target退出 while 循环。
接下来
继续移动 right累加 sum 直至再次满足条件或遍历完数组。
第二次满足条件
right4: sum nums[4] 4现在 sum 7满足 sum target。计算子数组长度 right-left1 2更新 minlen Math.min(minlen, 2) 2。由于这次 sum 正好等于 target收缩窗口会导致 sum target因此不会进一步收缩。
遍历完成
继续移动 right但不再有新的子数组满足条件且长度更小。
结果
遍历结束后minlen 2这是满足条件的最小子数组长度对应子数组是 [4,3]。
二.无重复字符的最长子串 题目链接3.无重复字符的最长子串 算法原理 初始化定义两个指针 left 和 right初始都指向字符串的起始位置即 left 0right 0。hash 数组用于记录 ASCII 字符出现的次数考虑到 ASCII 总共有 128 个字符故数组大小为 128。ret 用于存储最长无重复子串的长度初始化为 0。 扩展右边界不断地将右指针 right 向右移动每移动一次就将当前字符 ch[right] 在 hash 数组中的计数加一。这意味着窗口正在尝试包含更多的字符。 处理重复字符与收缩左边界如果 hash[ch[right]] 大于 1表明当前字符 ch[right] 已经在窗口内出现过这时需要移动左指针 left将 left 指向的字符在 hash 中的计数减一同时左指针右移一位以此来排除重复字符保证窗口内的字符都是唯一的。 更新最大长度每次移动右指针时都计算当前窗口的长度即 right - left 1并将这个长度与当前已知的最大长度 ret 进行比较取较大者更新 ret。这样可以保证 ret 始终保存着遇到过的最长无重复字符子串的长度。 遍历结束当右指针 right 遍历到字符串末尾时循环结束返回 ret 作为最终结果。
时间复杂度与空间复杂度
时间复杂度O(n)其中 n 是字符串的长度。每个字符最多被访问两次一次作为右边界扩展一次作为左边界收缩。空间复杂度O(1)虽然使用了 hash 数组但它是一个固定大小的数组128与输入字符串的长度无关因此空间复杂度是常数级别的。
总之这段代码通过巧妙地利用滑动窗口和哈希表在这里是简化版的数组实现减少了不必要的字符比较从而高效地求解了最长无重复字符子串的长度问题。
代码 public int lengthOfLongestSubstring(String s) {int left0,right0;char[] chs.toCharArray();int[] hashnew int[128];//用数组模拟哈希表int ret0;while(rights.length()){hash[ch[right]];while(hash[ch[right]]1){hash[ch[left]]--;}ret Math.max(ret,right-left1);right;}return ret;} 举例
测试用例 abcabcbb
初始化
left 0, right 0char[] ch {a, b, c, a, b, c, b, b}int[] hash 初始化为全0用于记录字符出现次数ret 0用于记录最长无重复子串长度
执行过程 右指针移动 记录字符 right0: ahash[a] 1rightright1: bhash[b] 1rightright2: chash[c] 1right。此时窗口abc无重复字符ret 3 发现重复收缩左边界 right3: ahash[a] 2发现重复开始收缩左边界hash[a]--left 继续扩展与收缩 right4: bhash[b] 2收缩左边界hash[b]--leftright5: chash[c] 2收缩左边界hash[c]--left。此时窗口内为bc无重复字符ret保持为3 重复与扩张 right6: bhash[b] 3收缩左边界hash[b]--leftright7: bhash[b] 3继续收缩左边界hash[b]--left。此时窗口为空ret保持为3
结果
最后所有字符遍历完毕返回 ret 的值即最长无重复字符的子串长度为 3。在这段字符串中满足条件的最长子串是 abc。
这段代码通过动态调整窗口由 left 和 right 定义大小有效利用哈希表此处为简化版的 hash 数组快速判断字符是否重复最终找到了最长的无重复字符子串。
三.最大连续1的个数III 题目链接1004.最大连续1的个数III 算法原理 初始化定义三个指针 left, right, 和一个计数器 zero分别用来表示窗口的左边界、右边界以及窗口内 0 的数量。同时定义 ret 来存储最长子数组的长度初始化为 0。 扩展右边界不断将右指针 right 向右移动每次移动时检查新进入窗口的元素nums[right]是否为 0如果是则将 zero 计数器加 1。这意味着窗口正在尝试包含更多的元素包括 0。 处理限制条件当窗口内 0 的数量超过了允许的最大数量 k 时需要移动左指针 left 来缩小窗口直到窗口内 0 的数量回到 k 或更少。在移动 left 的过程中如果移出窗口的元素是 0则将 zero 减 1。 更新最长子数组长度在每次移动右指针之后即每次尝试扩大窗口或维持窗口大小但可能更新了窗口内容后都会用当前的右指针减去左指针再加 1 来计算当前窗口的长度并用这个长度去更新 ret 的值保持 ret 存储的是最长子数组的长度。 遍历结束当右指针遍历完整个数组后循环结束此时 ret 中存储的就是满足条件的最长连续子数组的长度。
时间复杂度与空间复杂度
时间复杂度O(n)其中 n 是数组 nums 的长度。每个元素最多被遍历一次。空间复杂度O(1)因为使用的变量数量是固定的不依赖于输入数组的大小。
代码
public int longestOnes(int[] nums, int k) {int ret0;for(int left0,right0,zero0;rightnums.length;right){if (nums[right]0) zero;while (zerok){if (nums[left]0) zero--;}retMath.max(ret,right-left1);}return ret;} 举例
测试用例 [1,1,1,0,0,0,1,1,1,1,0]
初始化
left 0, right 0, zero 0, ret 0。
执行过程 右指针移动初始化时数组内的前三个元素都是1右指针向右移动窗口内没有0zero 仍为0此时最长子数组长度为3但随着右指针的移动情况会变化。 遇到0并处理 当 right 3遇到第一个0zero 1。当 right 4遇到第二个0zero 2达到了 k 2 的限制。此时窗口 [1,1,1,0,0]满足条件长度为5更新 ret 5。 收缩左边界 当 right 5遇到第三个0由于 zero 已经是2需要移动左指针。当 left 3nums[left] 是0zero--此时窗口内0的个数回到1窗口变为 [1,0,0,1,0,0]。 继续扩展右边界 继续移动右指针忽略更多的0直到 right 8窗口为 [0,0,1,1,1,1,1,1]此时 zero 2最初的两个0窗口长度为6更新 ret 6。 之后的步骤 当 right 继续移动并遇到更多0时由于已经找到了长度为6且满足条件的子数组即使右边界继续扩大也不会影响最终答案因为任何新加入的0都会导致左侧边界相应移动保持最多2个0在窗口内。
结论
最终返回 ret 6表示最长的连续子数组是 [0,0,1,1,1,1]
四.将x减到0的最小操作数 题目链接11658.将x减到0的最小操作数 算法原理 计算总和首先遍历数组 nums计算其所有元素之和 sum。如果 sum 小于目标值 x直接返回 -1因为无论如何操作都无法使子数组之和等于 x。 确定目标值需要找到一个和为目标 x 的子数组但实际操作中我们是在找一个和为 target sum - x 的子数组。这是因为我们需要从总和中减去 x 来达到操作的目的。 双指针滑动窗口 初始化两个指针 left 和 right 都为 0同时维护一个变量 cur 表示当前窗口内的元素和。右指针 right 向右移动将 nums[right] 加入当前窗口的和 cur。如果 cur 大于目标值 target则说明当前窗口和过大需要减小窗口左侧的值即减去 nums[left] 并将 left 指针右移一位同时更新 cur。当 cur 等于 target 时说明找到了一个符合条件的子数组。此时更新最大长度 ret 为当前子数组的长度right-left1。继续移动右指针重复上述过程直到右指针遍历完整个数组。 结果处理 如果在整个过程中没有找到符合条件的子数组即 ret 仍为初始值 -1返回 -1。若找到了符合条件的子数组返回数组长度减去找到的最长子数组长度即 nums.length - ret。这代表需要的操作次数因为要使得剩下的部分和为 x整个数组的剩余部分非连续子数组需要通过减少操作来匹配。
时间复杂度与空间复杂度
时间复杂度O(n)其中 n 是数组 nums 的长度。每个元素最多被访问两次一次在计算总和时一次在滑动窗口中。空间复杂度O(1)使用的额外空间与输入数组的大小无关只使用了几个固定变量。
代码 public int minOperations(int[] nums, int x) {int sum0;int ret-1;for (int a : nums){suma;}if(sumx){return -1;}int targetsum-x;for (int left0,right0,cur0;rightnums.length;right){curnums[right];while(curtarget){cur-nums[left];}if (curtarget){retMath.max(ret,right-left1);}}if(ret-1){return -1;}return nums.length-ret;}
举例
测试用例 nums[1,1,4,2,3]x5初始化 首先遍历数组 nums 计算所有元素之和 sum。 sum 1 1 4 2 3 11 检查 sum 是否小于 x若小于则直接返回 -1这里不适用因为 11 5。 计算目标和 target 为 sum - x。 target 11 - 5 6
滑动窗口
接下来使用双指针left 和 right进行滑动窗口操作同时维护窗口内元素和 cur。 初始化left 0, right 0, cur 0。 遍历数组 右指针移动right 开始从 0 向右移动每次移动将 nums[right] 加入 cur。 当 right 0, cur 0 1 1此时 cur target当 right 1, cur 1 1 2此时 cur target当 right 2, cur 2 4 6此时 cur target记录子数组长度ret Math.max(ret, right-left1) Math.max(-1, 3) 3并且开始收缩窗口。由于 cur 等于 target无需移动 left。 继续移动右指针 当 right 3, cur 6 2 8此时 cur target需要收缩窗口。 移动 leftcur - nums[left] 8 - 1 7left 1此时 cur target 继续移动 left。再次移动 leftcur - nums[left] 7 - 1 6left 2此时 cur target不需要进一步移动 left。 遍历结束 右指针继续移动但在本次测试用例中不会再次找到满足条件的子数组因此 ret 保持为 3。
结果处理
最后检查 ret 是否为 -1如果不是则返回 nums.length - ret因为这是从整个数组长度中减去满足条件的子数组长度即需要操作的次数。 return nums.length - ret 5 - 3 2
结论
对于测试用例 nums[1,1,4,2,3] 和 x5这段代码会返回 2意味着需要至少操作两次使得数组中某一段连续子数组之和等于 x5。具体来说可以通过减少前两个元素各一次即 1-10 和 1-10使得剩下的数组 [0,0,4,2,3] 中 426 符合要求。 以上就是本期的全部内容啦若有错误疏忽希望各位大佬及时指出 制作不易希望能对各位提供微小的帮助可否留下你免费的赞呢
