【Leetcode】最大连续1的个数
leetcode中最大连续1的个数类题目的汇总。
最大连续1的个数Ⅰ
1. 题目描述
leetcode题目链接：
2. 思路分析
方法一：一次遍历
遇到nums[i] == 1，则count++，遇到nums[i] == 0, 则count=0，然后更新最大连续1的个数。
方法二：双指针
固定左边界，然后判断右边界，更新最大值和右边界减去左边界的差值。
方法三：动态规划
dp[i]表示以第i个元素结尾的最大连续1的个数。
其中：双指针方法运行时间最短。
3. 参考代码
方法一：一次遍历
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int res = 0, count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
count++;
} else {
count = 0;
}
res = Math.max(res, count);
}
return res;
}
}
方法二：双指针
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; i++) {
int j = i;
while (j < nums.length && nums[j] == 1) {
j++;
}
res = Math.max(res, j - i);
i = j;
}
return res;
}
}
方法三：动态规划
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int n = nums.length;
int[] dp = new int[n + 1];
int res = 0;
for (int i = 1; i <= n; i++) {
if (nums[i - 1] == 1) {
dp[i] = dp[i - 1] + 1;
res = Math.max(res, dp[i]);
}
}
return res;
}
}
最大连续1的个数Ⅱ
1. 题目描述
leetcode题目链接：，plus会员题目，直接看题。
给定一个二进制数组，你可以最多将 1 个 0 翻转为 1，找出其中最大连续 1 的个数。
输入：[1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。
当翻转以后，最大连续 1 的个数为 4。
2. 思路分析
双指针，当右指针遇到第二个0时，左指针移动直到遇到0，更新最大值。（右边无脑滑动，左边看情况收缩）
3. 参考代码
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int left = 0, right = 0;
int res = 0, count = 0;
while (right < nums.length) {
if (nums[right++] == 0) {
// 先判断nums[right]==0,再执行right++
count++;
}
while (count > 1) {
if (nums[left++] == 0) {
count--;
}
}
res = Math.max(res, right - left);
}
return res;
}
}
最大连续1的个数Ⅲ
1. 题目描述
leetcode题目链接：
2. 思路分析
最大连续1的个数Ⅱ的进阶版，有k个0翻转为1。双指针。
3. 参考代码
class Solution {
public int longestOnes(int[] nums, int k) {
int n = nums.length, res = 0, count = 0;
int left = 0, right = 0;
while (right < n) {
if (nums[right++] == 0) {
count++;
}
while (count > k) {
if (nums[left++] == 0) {
count--;
}
}
res = Math.max(res, right - left);
}
return res;
}
}