关于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;