最大间断 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;