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

算法讲解--最大连续1的个数

news 2025/8/4 19:09:40

一，题目描述

题目中给的k表示最多有k个0翻转为1，反转为1之后。在这个数组中寻找最长个数1的个数。最后返回这个最长的数组个数。如上实例1，将最后一个0和倒数第二个0反转为1。之后组成的子数组返回这个子数组的个数。

二，算法讲解

首先根据这个题的题目意思。本质上来说就是寻找最长的子数组。并且对该子数组进行限制（必须全部为1）。

如果我们算反转0的可能性，会发现在许多个0中选出k个0进行反转有非常非常多种可能性。并且需要在上述的每一种可能性中，选出最长的连续个1的子数组。通过叠加会发现使得算法非常的麻烦。

为此不妨可以换一个思路，不考虑0，在进行挑选最长子数组的过程中，将0也带上，这时只需要确保这个子数组中内部包含的0的个数是要小于等于k。如此这个子数组照经过反转之后也可以满足题目中所说的连续子数组。

在有了上述思路之后：

1，双指针+暴力枚举

通过遍历的方式一个一个进行判读具体如图：

这示例一中，k等于2，表明该子数组组多可以有两个零存在，定义两个指针left，right。起初都指向该数组的开头。只要left到right的数据区域内部的0不超过2。那么该区域的子数组就满足题目中的要求如图：

此时会发现，right如果继续向右出发，该区域的0的个数就超过了题目中的要求。因此right和left此时区间的子数组就是left在这个位置的最大子数组。

之后left++，right和left指向同位置如图：

right继续加加，直到二者的区域内部0的个数刚好为临界，并且下一个数据为0 。换句话说就是right向右走到只要向右就不满足题目要求的临界条件。如图：

此时就是left为第二个位置，该区域能存在的最大子数组。往复上述过程。直到right遍历完整个数组。

最终在这些每个区域的最大的子数组选出最长的一个，这个最长的子数组就是该数组的最长子数组。

2，滑动窗口法：

在上述过程中，前两组实验的现象会发现，只要left向前的位置没有0，right似乎只能走到相同的位置。如法一图：。为此可以发现right不必要重复的回到和left相同的位置。当right走的临界值时如示例1图：

left向右走，right不需要回来重新走。直到left走过一个0如图：

此时right可以继续向右走数据，直到下一次临界条件如图：

当达到临界条件之后，left继续向右走一个0 。如图：
此时right继续走到进到临界条件。直到right遍历完整个数组。该算法结束。如图：

在次算法的过程中，每一次right进行到一次临界条件，就是每一个区域的最长子数组。在所有的最长子数组中选出一个最长的数组，返回这个数组的个数就是该算法的结果。

3，示例

以题目中的示例二再次演示一下滑动窗口算法：

起始位置：

第一步k为3，right第一次临界情况如图：

记录次数，这个区间子数组的个数，left走过第一个0如图：

第二步right继续向右寻找下一个临界条件如图：

记录次数，这个区间子数组的个数，left走过第二个0如图：

第三步right继续向右寻找下一个临界条件如图：

记录次数，这个区间子数组的个数。

第四步......依次往复这个过程。直到最后right遍历完整个数组。

在上述记录的子数组个数，返回最长的子数组个数，就是该题的最长子数组个数。

三，代码实现

int longestOnes(vector<int>& nums, int k) {int i = 0;int nurber = 0;int zero = 0;int left = 0;int right = 0;while( left+nurber< nums.size()){while(zero <= k&&right < nums.size()){if(zero == k && nums[right] == 0){break;}if(nums[right] == 0){zero++;}right++;}if(nurber < right-left){nurber = right-left;}if(nums[left] == 0){zero--;}left++;}return nurber;}

zero变量负责记录该区间有几个0，nurber负责记录子数组长度。题目中用的vector接口可以参考如下链接C++--vector_c++ vector assign-CSDN博客。