关于leetcode:leetcode连续子数组题目汇总

最大间断1的个数

• 485
• 487
• 1004

485

给定一个二进制数组， 计算其中最大间断 1 的个数
输出：[1,1,0,1,1,1]
输入：3

办法1

int findMaxConsecutiveOnes(vector<int>& nums) {
    int maxNum = 0, tmp = 0; 
    for (int i = 0; i < nums.size(); i++) { 
        if (nums[i] == 1) { 
        tmp++; 
        } else {
            maxNum = max(maxNum, tmp); tmp = 0; 
        } 
    } 
    return max(maxNum, tmp);
}

办法2

//dp[i] = dp[i-1]+1;
int findMaxConsecutiveOnes2(vector<int>& nums) {
    vector<int> dp(nums.size()); 
    for (int i = 0; i < nums.size(); i++) { 
        if (i == 0) { 
            if (nums[i] == 1) { 
                dp[i] = 1; 
            } else { 
                dp[i] = 0; 
            } 
        } else { 
            if (nums[i] == 1) { 
                dp[i] = dp[i-1] + 1; 
            } else { 
                dp[i] = 0; 
            } 
        } 
    } 
    sort(dp.begin(), dp.end()); 
    return dp[nums.size()-1];}

487

给定一个二进制数组，你能够最多将 1 个 0 翻转为 1，找出其中最大间断 1 的个数.
输出：[1,0,1,1,0]
输入：4

思路

• 两个dp， dp1不反转，dp2反转
• dp1[i] = dp1[i-1] + 1;
• dp2[i] = dp2[i-1] + 1; nums[i] = 1
• dp2[i] = dp1[i-1] + 1; nums[i] = 0

int findMaxConsecutiveOnes(vector<int>& nums) {
    vector<int> dp1(nums.size());
    vector<int> dp2(nums.size());
    for (int i = 0; i < nums.size(); i++) {
        if (i == 0) {
            if (nums[i] == 0) {
                dp1[i] = 0;
                dp2[i] = 0;
            } else {
                dp1[i] = 1;
                dp2[i] = 1;
            }
            continue;
        }
        if (nums[i] == 0) {
            dp1[i] = 0;
            dp2[i] = dp1[i-1] + 1;
        } else {
            dp1[i] = dp1[i-1] + 1;
            dp2[i] = dp2[i-1] + 1;
        }
    }
    sort(dp2.begin(), dp2.end());
    return dp2[dp2.size()-1];
}

1004

给定一个由若干 0 和 1 组成的数组 A，咱们最多能够将 K 个值从 0 变成 1 。返回仅蕴含 1 的最长（间断）子数组的长度。
输出：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输入：6

思路

• 双指针

    int temp = 0;
    int res = 0;
    int startIdx = 0, endIdx = 0;
    while (endIdx < A.size()) {
        if (A[endIdx] == 1) {
            temp += 1;
            endIdx += 1;
        } else {
            if (K > 0) {
                temp += 1;
                K -= 1;
                endIdx += 1;
            } else {
                if (A[startIdx] == 1) {
                    bool on_off = true;
                    while (on_off && startIdx <= endIdx) {
                        if (A[startIdx] == 0) {
                            on_off = false;
                        }
                        startIdx += 1;
                        temp -= 1;
                    }
                } else {
                    startIdx += 1;
                    temp -= 1;
                }
                K += 1;
            }
        }
        res = max(temp, res);
    }
    return res;