• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

leetcode连续子数组题目汇总

互联网 diligentman 2周前 (02-21) 7次浏览

最大连续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;

程序员灯塔
转载请注明原文链接:leetcode连续子数组题目汇总
喜欢 (0)