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;
    }
};

 2024 考试中最大的困扰度(中等)

 题目：

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。

给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。
请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。

示例：

输入：answerKey = "TTFF", k = 2
输出：4
解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。

解法1：滑动窗口

将1004题的解法1作为一个函数进行调用

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

    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(longestones(answerKey, k, 'T'), longestones(answerKey, k, 'F'));
    }
};

解法2

1004解法2作为一个函数进行调用

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

    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(longestones(answerKey, k, 'T'), longestones(answerKey, k, 'F'));
    }
};