网站网页栅格化,如何上传图片到网站,seo免费优化工具,天津市网站建设目录 题目#xff1a;
示例#xff1a;
分析#xff1a;
代码运行结果#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
给一个数组#xff0c;求删除一个元素以后能得到的连续的最长的全是1的子数组。
我们可以先单独统计出连续为1的子数组分别长度…目录 题目
示例
分析
代码运行结果 题目 示例 分析
给一个数组求删除一个元素以后能得到的连续的最长的全是1的子数组。
我们可以先单独统计出连续为1的子数组分别长度是多少然后如果两个全是1的子数组中间刚好隔着一个0因为题目设定这是一个二进制的数组因此除了1就是0那么我们可以通过删除这个0得到一个长度等于这两个全是1的子数组的长度总和的子数组。
不过这里就不演示这种解法了因为在LeetCode75中这题是滑动窗口这一专题的因此我们用滑动窗口来做这题。 和上一题类似只不过本题不是翻转而是删除并且只删除一个。翻转和删除不一样的是翻转以后仍然可以算是1的长度而删除以后就没了则不能算到是连续1的长度里。
滑动窗口我们可以定义左右两个指针不断将右指针右移来收集最多数量的1。
我们再定义一个bool类型的变量用于记录是否已经删除了一个元素。
我们不断右移右指针如果遇到了0那么我们再看看是否已经删除过元素如果没删除过元素那么我们将记录删除元素的标记置false然后接着右移右指针因为我们算是把0删除了因此可以接着往右统计1的个数。
如果遇到0并且我们已经删除过元素了那么我们一样是把当前的0删除但是我们就算是删除两个元素了因此我们需要不断左移左指针直到左指针划出我们删除的第一个元素。这样我们左右指针的范围内就只算是删除了一个元素然后我们接着右移右指针即可。
在滑动窗口的过程中我们记录左右指针包含的最大范围即可。
有一点要注意的是题目要求必须删除一个元素因此如果整个数组都是1的话我们应该返回的是数组长度 -1. 代码运行结果
class Solution {
public:int longestSubarray(vectorint nums) {int res0;int l0;int r0;bool flagtrue; //用于记录是否删除了数int temp0;while(rnums.size()){if(nums[r]1) temp;else{if(flag){flagfalse;}else{resmax(res,temp);while(lrnums[l]1){ //滑动窗口缩短左边界,直到遇到非1,则等于不在第一个非1处删除元素,而是在本次遇到的非1处使用了删除数.l;temp--;}l;}}r;}resmax(res,temp);return resnums.size()?res-1:res; //因为必须删除一个元素,因此如果全为1的最长子数组长度和数组一致则也要减掉一个1.}
};
