【力扣刷题实战】最大连续1的个数 III

大家好，我是小卡皮巴拉

文章目录

目录

力扣题目： 最大连续1的个数 III

题目描述

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C++）

兄弟们共勉 ！！！ 

---

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

力扣题目： 最大连续1的个数 III

原题链接：1004. 最大连续1的个数 III - 力扣（LeetCode）

题目描述

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 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,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

解题思路

问题理解

本题的目标是在给定的二进制数组 nums 中，最多翻转 k 个 0，使得数组中连续 1 的个数达到最大，最终需要返回这个最大的连续 1 的个数。

算法选择

采用滑动窗口算法。滑动窗口算法适合处理数组或字符串中的子数组、子串问题，通过两个指针界定窗口范围并动态调整，能有效解决本题中寻找最大连续 1 个数的问题。

具体思路

1. 初始化变量：

   • 获取数组 nums 的长度 n。

   • 定义变量 ret 用于记录最大连续 1 的个数，初始化为 0。

   • 使用 left 和 right 两个指针来界定滑动窗口的左右边界，初始都指向数组起始位置。

   • 定义变量 zero 用于记录当前窗口内 0 的个数，初始化为 0。

2. 移动右指针：使用 for 循环让 right 指针从左到右遍历数组。当 nums[right] 为 0 时，说明有一个 0 进入窗口，将 zero 的值加 1。

3. 调整窗口：当 zero 的值大于 k 时，意味着当前窗口内 0 的个数超过了允许翻转的最大数量，需要移动 left 指针缩小窗口。如果 nums[left] 为 0，说明移除的是一个 0，将 zero 的值减 1。

4. 更新结果：每次移动 right 指针后，计算当前窗口的长度 right - left + 1，并与 ret 比较，取较大值更新 ret。

5. 返回结果：循环结束后，返回 ret，即最大连续 1 的个数。

解题要点

1. 窗口的动态调整：根据窗口内 0 的个数与 k 的大小关系，合理移动 left 指针调整窗口大小，保证窗口内 0 的个数不超过 k。

2. 记录 0 的个数：使用 zero 变量准确记录窗口内 0 的个数，这是判断是否需要调整窗口的关键。

3. 结果的更新：每次移动 right 指针后，及时更新最大连续 1 的个数，确保最终结果的正确性。

完整代码（C++）

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size(); // 获取数组的长度int ret = 0; // 用于记录最大连续 1 的个数// 初始化左右指针和记录窗口内 0 的个数的变量for(int left = 0, right = 0, zero = 0; right < n; right++){if(nums[right] == 0) // 当前元素为 0，进入窗口，0 的个数加 1zero++;while(zero > k) // 窗口内 0 的个数超过允许翻转的最大数量{if(nums[left++] == 0) // 移除左指针指向的元素，如果是 0，0 的个数减 1zero--;}ret = max(ret, right - left + 1); // 计算当前窗口长度并更新最大连续 1 的个数}return ret; // 返回最大连续 1 的个数}
};

兄弟们共勉 ！！！ 

码字不易，求个三连

抱拳了兄弟们！