leetcode连续子数组题目汇总

最大连续1的个数

  • 485
  • 487
  • 1004
  • 1438 滑动窗口+连续数组
485. 最大连续 1 的个数

给定一个二进制数组, 计算其中最大连续 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. 最大连续1的个数 III

给定一个由若干 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;
}
1438. 绝对差不超过限制的最长连续子数组

给你一个整数数组 nums ,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组,则返回 0。

思路
  • 用到滑动窗口,判断连续子数组
  • 用到multiset,内部红黑树有序,关键字可以重复
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        //用到滑动窗口
        multiset<int> iset;//关键字可以重复
        int left = 0, right = 0,maxNum = INT_MIN;
        while (right < nums.size()) {
            iset.insert(nums[right]);
            while (*iset.rbegin() - *iset.begin() > limit) {
                iset.erase(iset.find(nums[left++]));
            }
            maxNum = max(maxNum, right-left+1);
            right++;
        }

        return maxNum;
    }
};

评论

暂无评论