Leetcode: 最大连续个数及题目变形（485、487、1004、2024）

本文主要是介绍Leetcode: 最大连续个数及题目变形（485、487、1004、2024），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

485 最大连续1的个数（简单）

题目：给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

 示例 1

输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

解法1：一次遍历

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int cnt = 0;
        int ans = 0;
        for(auto& t : nums){
            if(t == 1) cnt++;  
            else{
                ans = max(cnt, ans);
                cnt = 0;
            }
            
        }
        ans = max(cnt, ans);
        return ans;
    }
};

 487 最大连续1的个数 II(中等)

 题目：给定一个二进制数组 nums ，如果最多可以翻转一个 0 ，则返回数组中连续 1 的最大个数。

 示例1

输入：nums = [1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。
     当翻转以后，最大连续 1 的个数为 4。

解法1：一次遍历

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int cnt = 0;//当前连续1的数量
        int ans = 0;//上一段连续1的数量
        int pre = -1;//幅值-1是为了在nums长度为1时，可以保证争取的输出
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 1){
                cnt++;
            }
            else{
                pre = cnt;
                cnt = 0;
            }
            ans = max(ans, pre + cnt + 1);
        }
        return ans;
    }
};

解法2：动态规划

 首先要可以列出状态转移方程：

//dp0 为无翻转情况下的最长1序列
//dp1 为一次翻转后的最长1序列

//在nums[i]  = 1时
dp0 = dp0 + 1
dp1 = dp1 + 1
//在nums[i] = 0时
dp1 = dp0 + 1
dp0 = 0

代码：

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int dp0 = 0;
        int dp1 = 0;
        int ans = 0;
        for(auto& t : nums){
            if(t == 1){
                dp0++;
                dp1++;
            }
            else{
                dp1 = dp0 + 1;
                dp0 = 0;
            }
            ans = max(ans, max(dp1, dp0));
        }
        return ans;
    }
};

解法3：滑动窗口

此题为滑动窗口模版题。

右端不断增加，直到翻转次数cnt为0后，再一次遇到0时，左端向右移动到遇到的第一个0出。

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int left = 0;
        int ans = 0;
        int cnt = 1;//翻转一次
        for(int right = 0; right < nums.size(); right++){
            if(nums[right] == 0){
                cnt--;
            }
            while(cnt < 0){
                if(nums[left] == 0){
                    cnt++;
                }
                left++;
            }
            ans = max(ans, right-left+1);
        }
        return ans;
    }
};

 1004 最大连续1的个数 III(中等)

题目：给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 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。

解法1：滑动窗口

参考上一题487解法3

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0;
        int ans = 0;
        for(int right = 0; right < nums.size(); right++){
            if(nums[right] == 0){
                k--;
            }
            while(k < 0){
                if(nums[left] == 0){
                    k++;
                }
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

 解法2：双指针(作参考，比较难想到)

先构建一个数组P，其元素大小是当前位置到0位置中所含0的数量。

接下来只要考虑P[right] - P[left]是否小于k即可

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> P(n+1);
        P[0] = 0;
        for(int i = 1; i <= n; i++){
            P[i] = P[i-1] + (1 - nums[i-1]);//统计0-i之间0的个数
        }
        int ans = 0;
        int left = 0;
        for(int right = 1; right < P.size(); right++){
            int dif = P[right] - P[left];//右端-左端的0的个数
            if(dif <= k)
                ans = max(ans, right - left);//因为right在数组nums中是right+1的位置，所以这里不同额外加1
            else{
                left++;
            }
        }
        return ans;
    }
};

这篇关于Leetcode: 最大连续个数及题目变形（485、487、1004、2024）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！