最大间断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] = 1dp2[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;