珠海做网站的公司介绍权威网站优化价格

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

珠海做网站的公司介绍,权威网站优化价格,做网站的时候旋转图片,禁用wordpress裁剪文章目录 C 滑动窗口详解#xff1a;基础题解与思维分析前言第一章#xff1a;热身练习1.1 长度最小的子数组解法一#xff08;暴力求解#xff09;解法二#xff08;滑动窗口#xff09;滑动窗口的核心思想图解分析滑动窗口的有效性时间复杂度分析易错点提示 1.2 无重复… 文章目录 C 滑动窗口详解基础题解与思维分析前言第一章热身练习1.1 长度最小的子数组解法一暴力求解解法二滑动窗口滑动窗口的核心思想图解分析滑动窗口的有效性时间复杂度分析易错点提示 1.2 无重复字符的最长子串解法一暴力求解解法二滑动窗口图解分析详细说明 1.3 最大连续 1 的个数 III解法滑动窗口滑动窗口的核心思想图解分析详细说明 关键点 1.4 将 x 减到 0 的最小操作数解法滑动窗口算法流程代码实现图解分析详细说明 写在最后 C 滑动窗口详解基础题解与思维分析 欢迎讨论如有疑问或见解欢迎在评论区留言互动。 点赞、收藏与分享如觉得这篇文章对您有帮助请点赞、收藏并分享 分享给更多人欢迎分享给更多对 C 感兴趣的朋友一起学习滑动窗口的基础与进阶 前言 滑动窗口是一种常用的算法技巧主要用于处理子数组、子串等具有“窗口”特性的题目。在本篇博客中我们将通过具体的例题讲解深入剖析滑动窗口的思想和它的应用场景。滑动窗口法能够在保持高效计算的同时减少重复的工作因而在处理某些连续区间问题时常常是最优解法。 第一章热身练习 1.1 长度最小的子数组 题目链接209. 长度最小的子数组 题目描述 给定一个含有 n 个正整数的数组 nums 和一个正整数 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 解法一暴力求解 算法思路 通过枚举数组中的所有子数组计算它们的和并检查是否大于等于 target从中找出符合条件的最小子数组。暴力解法虽然简单直接但在处理大规模数据时效率较低容易超时。 具体步骤 枚举数组中的所有子数组。计算每个子数组的和。如果子数组的和大于等于 target记录其长度并在所有子数组中找出最小的长度。 代码实现 class Solution { public:int minSubArrayLen(int target, vectorint nums) {int n nums.size();int result INT_MAX;for (int start 0; start n; start) {int sum 0;for (int end start; end n; end) {sum nums[end];if (sum target) {result min(result, end - start 1);break;}}}return result INT_MAX ? 0 : result;} };复杂度分析 时间复杂度O(n^2)需要枚举所有可能的子数组。空间复杂度O(1)仅使用常量级的额外空间。 暴力求解的缺点 对于大数据集如 10^5 级别该方法会导致时间超限。我们需要一种更高效的算法来解决这个问题。 解法二滑动窗口 算法思路 滑动窗口是一种高效的解决方法它通过两个指针 left 和 right动态调整窗口的大小来找到满足条件的最短子数组。具体过程如下 初始化 left 和 right从数组左端开始。将 right 向右移动扩大窗口并计算窗口内元素的和。如果窗口内的和 ≥ target尝试收缩窗口即将 left 向右移动尽可能缩小窗口并更新最小子数组的长度。重复上述过程直到 right 遍历完整个数组。 代码实现 class Solution { public:int minSubArrayLen(int target, vectorint nums) {int left 0, sum 0, result INT_MAX;for (int right 0; right nums.size(); right) {sum nums[right];while (sum target) {result min(result, right - left 1);sum - nums[left];}}return result INT_MAX ? 0 : result;} };复杂度分析 时间复杂度O(n)每个元素最多被访问两次一次是加入窗口一次是移出窗口。空间复杂度O(1)只使用了固定的额外空间。 滑动窗口的核心思想 滑动窗口法通过调整窗口的大小来找到满足条件的最优解。当窗口内元素的和大于等于 target 时我们尝试缩小窗口这样可以找到满足条件的最短子数组。 图解分析 假设 target 7, nums [2, 3, 1, 2, 4, 3] 初始状态left 0, right 0, sum 2窗口未达到 target。扩大窗口将 right 向右移动直到窗口和 sum 9满足条件。缩小窗口移动 left将子数组 [4, 3] 缩小到长度 2。 步骤图解 IterationLeftRightSumSubarrayResult1038[2, 3, 1, 2]42136[3, 1, 2]431410[3, 1, 2, 4]44247[1, 2, 4]35346[2, 4]36359[2, 4, 3]37457[4, 3]2 图解说明 Iteration 1从左端 left 0右端扩展到 right 3子数组 [2, 3, 1, 2] 的和为 8大于 target记录最小长度为 4。Iteration 2缩小窗口将 left 右移到 1新窗口和为 6小于 target不更新结果。Iteration 3右端扩展到 4子数组和为 10更新最小长度为 4。Iteration 4继续缩小窗口将 left 右移到 2子数组 [1, 2, 4] 的和为 7更新最小长度为 3。Iteration 5left 再次右移和降到 6小于 target不更新结果。Iteration 6right 扩展到 5子数组 [2, 4, 3] 的和为 9不更新最小长度。Iteration 7最后left 移到 4子数组 [4, 3] 的和为 7最终更新最小长度为 2。 滑动窗口的有效性 滑动窗口是一种高效的算法思想特别适用于处理子数组和子串等问题。下面详细解释其原理以及为何时间复杂度较低 滑动窗口的核心思想 滑动窗口寻找的是以当前窗口最左侧元素记为 left1为基准找出从 left1 开始满足条件的区间也就是使得子数组的和 sum 大于等于 target 时的最右侧记为 right1。在这道题中当 sum target 时说明从 left1 到 right1 的子数组满足条件并且我们可以记录这个窗口的长度。 避免重复计算 当我们已经找到从 left1 开始的最优区间后left1 就可以被舍弃。此时如果继续像暴力解法那样重新从 left2 开始计算后续的子数组和会导致大量重复的计算。因为从 left1 到 right1 的区间中许多元素的和已经被计算过了我们可以充分利用这个已有的信息。 优化窗口的移动 此时right1 的作用就显现出来了。通过滑动窗口我们不需要重新计算新的区间而是将 left1 从窗口内移除即从 sum 中减去 left1 对应的值。然后我们直接从 right1 开始继续向右扩展 right 来寻找下一个满足条件的区间即 left2 开始的最短区间。这样当 sum target 的条件不再满足时我们再次缩小窗口从而达到寻找最优解的目的。 高效性 滑动窗口法使得我们可以避免重新从头计算每个子数组的和。每当一个区间满足条件时我们就可以通过缩小窗口来检查是否有更短的区间可以满足条件。通过这种滑动的方式我们不仅能解决问题还大幅减少了重复计算从而提高了算法效率。
核心就是left和right指针不会回退也称为同向指针 时间复杂度分析 滑动窗口虽然看起来有两层循环外层控制 right 的扩展内层控制 left 的缩小但实际上每个指针left 和 right最多只会遍历数组 n 次。 right 指针从左向右遍历整个数组每个元素最多只被访问一次。left 指针每当 sum target 时left 会右移以缩小窗口每个元素也最多只会被访问一次。 因此left 和 right 指针都是单调递增的不会回退二者在整个过程中最多各自移动 n 次最终的时间复杂度为 O(n)。 易错点提示 窗口的收缩条件当窗口内的和 ≥ target 时我们才能缩小窗口。窗口最小长度的更新每次缩小窗口时都要更新最小长度否则可能遗漏最优解。 1.2 无重复字符的最长子串 题目链接3. 无重复字符的最长子串 题目描述 给定一个字符串 s 请你找出其中不含有重复字符的最长子串的长度。 示例 1 输入s abcabcbb输出3解释因为无重复字符的最长子串是 abc所以其长度为 3。 示例 2 输入s bbbbb输出1解释因为无重复字符的最长子串是 b所以其长度为 1。 示例 3 输入s pwwkew输出3解释因为无重复字符的最长子串是 wke所以其长度为 3。 请注意答案必须是 子串 的长度pwke 是一个 子序列不是子串。 提示 0 s.length 5 * 10^4s 由英文字母、数字、符号和空格组成 解法一暴力求解 算法思路 通过枚举从每个位置开始向后寻找无重复字符的子串能到达的位置记录其中最长的子串长度即可。在寻找无重复子串时可以使用哈希表统计字符出现的频次遇到重复字符时停止。 具体步骤 枚举每个起始位置 i从该位置开始寻找最长的无重复子串。使用哈希表统计字符出现的频次一旦出现重复字符终止当前枚举。更新最长无重复子串的长度。返回结果。 代码实现 class Solution { public:int lengthOfLongestSubstring(string s) {int ret 0; // 记录结果int n s.length();// 枚举从不同位置开始的无重复子串for (int i 0; i n; i) {int hash[128] { 0 }; // 记录字符频次for (int j i; j n; j) {hash[s[j]]; // 统计字符频次if (hash[s[j]] 1) // 出现重复终止break;ret max(ret, j - i 1); // 更新结果}}return ret;} };复杂度分析 时间复杂度O(n^2)枚举每个起点并从该起点向后查找无重复字符的子串。空间复杂度O(1)只需常量空间存储字符频次。 缺点 对于大数据集如 10^5 级别该算法会超时因此需要一种更高效的解法。 解法二滑动窗口 算法思路 滑动窗口是一种高效解决子串问题的方式。使用滑动窗口法时维持一个窗口使得窗口内的所有字符都是不重复的。当窗口右端进入新字符时更新哈希表记录字符频次 如果字符频次大于 1则窗口内出现了重复字符开始从左侧缩小窗口直到频次恢复为 1。如果没有重复字符直接更新最长无重复子串的长度。 代码实现 class Solution { public:int lengthOfLongestSubstring(string s) {int hash[128] { 0 }; // 使用数组模拟哈希表int left 0, right 0, n s.size();int ret 0; // 记录结果while (right n) {hash[s[right]]; // 将右端字符加入窗口// 如果窗口内出现重复字符移动左端直到没有重复while (hash[s[right]] 1) {hash[s[left]]–;}// 更新最长子串的长度ret max(ret, right - left 1);right; // 移动右端}return ret;} };复杂度分析 时间复杂度O(n)每个字符最多被左右指针访问两次因此时间复杂度为线性。空间复杂度O(1)只需常量空间存储字符频次。 图解分析 假设 s abcabcbb滑动窗口的执行过程如下 IterationLeftRightHash TableSubstringLength (Result)100a:1“a”1201a:1, b:1“ab”2302a:1, b:1, c:1“abc”3403a:2, b:1, c:1 → 左移 left1“bca”3514b:2, c:1, a:1 → 左移 left2“cab”3625b:1, c:2, a:1 → 左移 left3“abc”3736b:2, c:1 → 左移 left5“cb”3857b:2 → 左移 left6“b”3 详细说明 Iteration 1 Left0Right0加入字符 a哈希表为 a:1当前子串为 a长度为 1。 Iteration 2 Right1加入字符 b哈希表为 a:1, b:1当前子串为 ab长度为 2。 Iteration 3 Right2加入字符 c哈希表为 a:1, b:1, c:1当前子串为 abc长度为 3。 Iteration 4 Right3加入字符 a哈希表更新为 a:2, b:1, c:1。由于字符 a 出现两次移动 Left 指针到 1此时子串变为 bca长度仍然是 3。 Iteration 5 Right4加入字符 b哈希表更新为 b:2, c:1, a:1。由于字符 b 出现两次移动 Left 到 2子串变为 cab长度保持为 3。 Iteration 6 Right5加入字符 c哈希表更新为 b:1, c:2, a:1。此时字符 c 出现两次需要再次移动 Left将 Left 移到 3此时子串变为 abc长度为 3。 Iteration 7 Right6加入字符 b哈希表更新为 b:2, c:1。由于 b 出现两次移动 Left 到 left5此时子串应为 cb长度为 2。 Iteration 8 Right7继续加入字符 b哈希表更新为 b:2再次出现重复字符移动 Left 到 6子串为 b长度为 2。 1.3 最大连续 1 的个数 III 题目链接1004. 最大连续 1 的个数 III 题目描述 给定一个二进制数组 nums 和一个整数 k如果可以翻转最多 k 个 0则返回数组中 连续 1 的最大个数。 示例 1 输入nums [1,1,1,0,0,0,1,1,1,1,0], K 2 输出6 解释翻转红色标记的 0 变为 1最长的子数组长度为 6。 [1,1,1,0,0,1,1,1,1,1]
示例 2 输入nums [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K 3 输出10 解释翻转红色标记的 0 变为 1最长的子数组长度为 10。 [0,0,1,1,1,1,1,1,1,1,1,1] 解法滑动窗口 算法思路 这道题可以简化为求解一段 连续的 1 中包含最多 k 个 0 的最长子数组。由于这个子数组是 连续区间因此可以使用滑动窗口来解决。 具体步骤 初始化左右指针 left 和 right以及记录窗口内 0 的个数的变量 zero。当 right 指针向右扩展时 如果当前元素是 0增加 zero 计数。如果 zero 超过了 k需要通过移动 left 指针来移出窗口内的 0直到 zero 恢复到不超过 k 的状态。 在窗口合法时更新最大长度 ret。循环结束后ret 保存的即为最大连续 1 的长度。 代码实现 class Solution { public:int longestOnes(vectorint nums, int k) {int ret 0;for (int left 0, right 0, zero 0; right nums.size(); right) {if (nums[right] 0) zero; // 窗口内增加一个 0// 如果 0 的数量超过 k移动 left 指针while (zero k) {if (nums[left] 0) zero–; // 窗口左边界收缩减少一个 0}// 更新最大长度ret max(ret, right - left 1);}return ret;} };复杂度分析 时间复杂度O(n)每个元素最多被左右指针访问两次一次进入窗口一次被移出窗口。空间复杂度O(1)只使用了几个固定的额外变量存储当前状态。 滑动窗口的核心思想 滑动窗口方法通过不断扩展和收缩窗口来保证窗口内的 0 不超过 k。当窗口内的 0 超过 k 时移动左边界 left保持窗口内的 0 不超过 k。在每次移动时记录下窗口的最大长度。 图解分析 假设 nums [1,1,1,0,0,0,1,1,1,1,0]K2以下是滑动窗口的执行过程 步骤图解 IterationLeftRightZero CountSubarrayLength (Result)1000[1]12010[1, 1]23020[1, 1, 1]34031[1, 1, 1, 0]45042[1, 1, 1, 0, 0]56053[1, 1, 1, 0, 0, 0]57452[0, 0]58462[0, 0, 1]59472[0, 0, 1, 1]510482[0, 0, 1, 1, 1]511492[0, 0, 1, 1, 1, 1]6124103[0, 0, 1, 1, 1, 1, 0]6135102[0, 1, 1, 1, 1, 0]6 详细说明 Iteration 1-3从 Right0 到 Right2我们持续遇到 1所以窗口扩展Zero Count 仍为 0子数组 [1,1,1] 长度逐渐增加到 3。 Iteration 4Right3遇到一个 0Zero Count1但还在 k2 的允许范围内子数组 [1,1,1,0] 长度为 4。 Iteration 5Right4再遇到一个 0Zero Count2此时子数组 [1,1,1,0,0] 满足条件长度增加到 5。 Iteration 6Right5再遇到一个 0Zero Count3超出 k2 的限制。因此需要缩小窗口Left 开始向右移动。最终 Left 移动到 4窗口变为 [0, 0]Zero Count 恢复到 2子数组长度保持为 5。 Iteration 7-10Right 不断扩展子数组逐渐变为 [0,0,1,1,1]虽然 Zero Count 始终为 2但最大长度仍为 5。 Iteration 11Right9加入一个 1窗口变为 [0,0,1,1,1,1]满足 Zero Count2子数组长度增加到 6。 Iteration 12-13Right10遇到一个 0Zero Count3再次超过限制因此移动 Left直到 Left5窗口变为 [0, 1, 1, 1, 1, 0]最大长度仍为 6。 关键点 每次当 0 的数量超过 k 时我们通过移动 left 指针来缩小窗口直到窗口内的 0 的数量不超过 k。当窗口合法时不断更新最长子数组的长度。 1.4 将 x 减到 0 的最小操作数 题目链接1658. 将 x 减到 0 的最小操作数 题目描述 给你一个整数数组 nums 和一个整数 x。每次操作时你可以移除数组 nums 的最左边或最右边的元素然后从 x 中减去该元素的值。请注意你需要修改数组以供接下来的操作使用。如果可以将 x 恰好减到 0返回最少的操作数否则返回 -1。 示例 1 输入nums [1,1,4,2,3], x 5输出2解释最佳解决方案是移除数组末尾的两个元素 [2,3]将 x 减为 0。 示例 2 输入nums [5,6,7,8,9], x 4输出-1解释无法将 x 减到 0。 示例 3 输入nums [3,2,20,1,1,3], x 10输出5解释最佳解决方案是移除前三个元素 [3,2,20] 和后两个元素 [1,3]共计 5 次操作。 提示 1 nums.length 1051 nums[i] 1041 x 109 解法滑动窗口 算法思路 题目要求找到移除的最少操作数使得 x被减为0。实际上这可以转换为在数组中找到和为 sum(nums) - x 的最长子数组剩下的部分就是需要移除的最小操作数。问题本质是找到和为 target sum(nums) - x 的最长连续子数组然后通过滑动窗口进行求解。 算法流程 计算目标和先计算数组的总和 sum然后求出 target sum - x。如果 target 0直接返回 -1。滑动窗口初始化使用两个指针 left 和 right 来控制窗口并通过维护一个窗口的和 sum 来查找目标值。滑动窗口操作 扩展窗口时右移 right 指针增加窗口的和。收缩窗口时左移 left 指针减小窗口的和。当窗口和等于 target 时更新最长子数组的长度。 返回结果如果找到满足条件的最长子数组返回 nums.size() - maxLen否则返回 -1。 代码实现 class Solution { public:int minOperations(vectorint nums, int x) {// 1. 计算数组总和和目标和int sum 0;for (int a : nums) sum a;int target sum - x;if (target 0) return -1;// 2. 滑动窗口查找和为 target 的最长子数组int ret -1;for (int left 0, right 0, tmp 0; right nums.size(); right) {tmp nums[right]; // 扩展窗口while (tmp target) tmp - nums[left]; // 收缩窗口if (tmp target) ret max(ret, right - left 1); // 更新最大长度}// 3. 返回结果数组总长度减去最长子数组长度return ret -1 ? -1 : nums.size() - ret;} };图解分析 假设 nums [1,1,4,2,3]x 5即目标是找到和为 sum(nums) - x 11 - 5 6 的最长子数组。 步骤图解 IterationLeftRightWindow SumSubarrayMax Length (Result)1001[1]-12012[1, 1]-13026[1, 1, 4]34038[1, 1, 4, 2]35137[1, 4, 2]36236[4, 2]37249[4, 2, 3]38345[2, 3]3 详细说明 Iteration 1Right0加入元素 1窗口和为 1还没达到目标和 6最大长度保持 -1。Iteration 2Right1加入元素 1窗口和为 2还没达到目标和最大长度保持 -1。Iteration 3Right2加入元素 4窗口和为 6正好达到了目标和 6最大子数组长度更新为 3。Iteration 4Right3加入元素 2窗口和为 8超出目标和 6开始移动 left 指针缩小窗口。Iteration 5Left1去掉左侧元素 1窗口和为 7仍然超出目标和继续移动 left。Iteration 6Left2去掉左侧元素 1窗口和为 6再次达到了目标和但最大子数组长度仍然为 3。Iteration 7Right4加入元素 3窗口和为 9超过目标和继续移动 left。Iteration 8Left3去掉左侧元素 4窗口和为 5窗口不再满足条件结束循环。 写在最后 在这篇文章中我们详细介绍了滑动窗口这一高效的算法技巧并通过四道经典题目逐步剖析了它的核心思想和实际应用。在长度最小的子数组、无重复字符的最长子串、最大连续 1 的个数 III 以及将 x 减到 0 的最小操作数等问题中滑动窗口均展现了其强大的解决区间问题的能力。 通过这篇文章读者不仅可以掌握滑动窗口的基础原理还能够通过具体的题目理解如何灵活运用滑动窗口解决实际的算法问题。从优化时间复杂度到减少重复计算滑动窗口无疑是处理连续区间问题的强力工具。希望大家在理解并掌握这些基础应用后能够在更复杂的场景中灵活应用这一技巧。 我们将在下一篇文章中深入探讨滑动窗口的进阶应用包括处理更复杂的数据结构、动态窗口调整等内容进一步提升大家在算法优化中的实战能力。 以上就是关于【优选算法篇】双指针的华丽探戈深入C算法殿堂的优雅追寻的内容啦各位大佬有什么问题欢迎在评论区指正或者私信我也是可以的啦您的支持是我创作的最大动力❤️