485.Max Consecutive Ones I & II

最大连续1的个数,以及 带翻转的最大连续1的个数

最大连续1的个数

题目链接:https://leetcode.com/problems/max-consecutive-ones

这是个签到题,就不浪费时间描述了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int temp_max = 0, all_max = 0;
for (int p : nums) {
if (p)
temp_max++;
else {
all_max = max(all_max, temp_max);
temp_max = 0;
}
}
return max(all_max, temp_max);
}
};

带翻转的最大连续1的个数

这个题是美团的笔试题,不过跟leetcode上的 https://leetcode.com/problems/max-consecutive-ones-ii 是一个路子,而且这道题目竟然还要钱…

我们可以维护一个窗口[left,right]来容纳至少k个0。

我们遇到了0,就累加zero的个数,

然后判断如果此时0的个数大于k,那么我们我们右移左边界left,

如果移除掉的nums[left]为0,那么我们zero自减1。

如果不大于k,那么我们用窗口中数字的个数来更新res,参见代码如下:

k 就是最多可以翻转的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums,int k) {
int res = 0, zero = 0, left = 0;
for (int right = 0; right < nums.size(); ++right) {
if (nums[right] == 0) ++zero;
while (zero > k) {
if (nums[left++] == 0) --zero;
}
res = max(res, right - left + 1);
}
return res;
}
};

举个例子: [1,0,0,1,0,1,0,1]

窗口大小是k,这里取2

  • 初始化
    [{1,0,0,1},0,1,0,1]

  • 进一步
    又发现了一个0,所以left++ ,直到移除掉nums[left]的0,其实就是为了保证窗口内有两个0
    [1,0,{0,1,0},1,0,1]

  • 进一步
    [1,0,0,{1,0,1,0,1}]

485.Max Consecutive Ones I &amp; II

https://iii.run/archives/61215d597ddd.html

作者

mmmwhy

发布于

2018-09-07

更新于

2022-10-30

许可协议

评论