s******i
发帖数: 236 | 1 一个0和1组成的数组，改变其中一个数（0变1或者1变0），使得改变后数组里连续的0
或者1的长度最大，返回这个最大长度。要求O(N)。
比如[1 0 1]，改变0，返回3
[1 1 0 1 0 0]，改变中间的0或者1，返回4 |
m*****n
发帖数: 2152 | 2 很简单啊，
第一遍算每个区间的连续0或者1的长度，
比如[1 0 1]，就是[1 1 1]
[1 1 0 1 0 0] 就是[2 1 1 2]
然后，第二遍扫看看[x 1 y]这个pattern的最大的和x+1+y是多少。
对不符合这种pattern的情况，就是最大的串的长度+1 或者是 最大的串的长度（这儿
有个问
题，如果全0或者全1，必须改吗？）。
其实实际编程，只要一遍就行了，用个 3 elements的moving window，有点DP的意思。
0
【在 s******i 的大作中提到】
: 一个0和1组成的数组，改变其中一个数（0变1或者1变0），使得改变后数组里连续的0
: 或者1的长度最大，返回这个最大长度。要求O(N)。
: 比如[1 0 1]，改变0，返回3
: [1 1 0 1 0 0]，改变中间的0或者1，返回4
|
f******t
发帖数: 18 | 3 //f1，f2分别表示0次改变跟1次改变时，当前的最长连续1的长度
int longestOne(const vector& arr) {
int f1 = 0, f2 = 0, ret = 0;
for (int i = 0; i < arr.size(); ++i) {
if (arr[i]) {
++f1; ++f2;
} else {
f2 = f1 + 1;
f1 = 0;
}
ret = max(ret, f2);
}
return ret;
} |
m*****n
发帖数: 2152 | 4 如果数组全0，你是result是 1？
【在 f******t 的大作中提到】
: //f1，f2分别表示0次改变跟1次改变时，当前的最长连续1的长度
: int longestOne(const vector& arr) {
: int f1 = 0, f2 = 0, ret = 0;
: for (int i = 0; i < arr.size(); ++i) {
: if (arr[i]) {
: ++f1; ++f2;
: } else {
: f2 = f1 + 1;
: f1 = 0;
: }
|
l*********8
发帖数: 4642 | 5 int maxConsecutive(const vector & ary) {
int changed[2] = {0, 0};
int noChange[2] = {0, 0};
int maxL = 0;
for (bool x : ary) {
maxL = max(maxL, ++changed[x]);
maxL = max(maxL, ++noChange[x]);
changed[1-x] = noChange[1-x];
noChange[1-x] = 0;
}
return maxL;
}
0
【在 s******i 的大作中提到】
: 一个0和1组成的数组，改变其中一个数（0变1或者1变0），使得改变后数组里连续的0
: 或者1的长度最大，返回这个最大长度。要求O(N)。
: 比如[1 0 1]，改变0，返回3
: [1 1 0 1 0 0]，改变中间的0或者1，返回4
|
m*****n
发帖数: 2152 | 6 不对吧，[0 1]的result是1？
【在 l*********8 的大作中提到】
: int maxConsecutive(const vector & ary) {
: int changed[2] = {0, 0};
: int noChange[2] = {0, 0};
: int maxL = 0;
: for (bool x : ary) {
: maxL = max(maxL, ++changed[x]);
: maxL = max(maxL, ++noChange[x]);
: changed[1-x] = noChange[1-x];
: noChange[1-x] = 0;
: }
|
l*********8
发帖数: 4642 | 7 写错了， 谢谢指出。
loop 里面第三行少了个 加1
int maxConsecutive(const vector & ary) {
int changed[2] = {0, 0};
int noChange[2] = {0, 0};
int maxL = 0;
for (bool x : ary) {
maxL = max(maxL, ++changed[x]);
maxL = max(maxL, ++noChange[x]);
changed[1-x] = 1 + noChange[1-x];
noChange[1-x] = 0;
}
return maxL;
}
【在 m*****n 的大作中提到】
: 不对吧，[0 1]的result是1？
|
f******n
发帖数: 279 | |
s******i
发帖数: 236 | 9
如果全是0也要改，所以应该是最长长度-1
【在 m*****n 的大作中提到】
: 很简单啊，
: 第一遍算每个区间的连续0或者1的长度，
: 比如[1 0 1]，就是[1 1 1]
: [1 1 0 1 0 0] 就是[2 1 1 2]
: 然后，第二遍扫看看[x 1 y]这个pattern的最大的和x+1+y是多少。
: 对不符合这种pattern的情况，就是最大的串的长度+1 或者是 最大的串的长度（这儿
: 有个问
: 题，如果全0或者全1，必须改吗？）。
: 其实实际编程，只要一遍就行了，用个 3 elements的moving window，有点DP的意思。
:
|
f******t
发帖数: 18 | 10
原來是0或1？我之前看以為是連續1~我的代碼是連續1最長長度
【在 m*****n 的大作中提到】
: 如果数组全0，你是result是 1？
|
|
|
M**a
发帖数: 848 | |
m******3
发帖数: 346 | 12 能解释一下思路么，没太明白
【在 l*********8 的大作中提到】
: 写错了， 谢谢指出。
: loop 里面第三行少了个 加1
: int maxConsecutive(const vector & ary) {
: int changed[2] = {0, 0};
: int noChange[2] = {0, 0};
: int maxL = 0;
: for (bool x : ary) {
: maxL = max(maxL, ++changed[x]);
: maxL = max(maxL, ++noChange[x]);
: changed[1-x] = 1 + noChange[1-x];
|
a**********0
发帖数: 422 | 13 我来解释一下？
int changed[2] = {0, 0};
记录 0或者1组成的连续串最长是多少 此串变化过一次
int noChange[2] = {0, 0};
记录 0或者1组成的连续串最长是多少 此串没有变化过
change【1】 可以理解为 1的通过俘虏0的连续串得到的 so far的连续串长度
扫描每一个数 有几种操作
此数必定破坏原来对手的unchange过的串 也就是使之归零
此数可以变化为对手 这样 对手的change = 对手unchange +1
无论如何情况 都破坏了对手的unchange的串 必须归零 因为即使第二种情况 对手的
unchange的串也不再是unchange了
当然此数也做 这么两件事
使自己change的串长度加一
使自己未经change的串长度加一
如果可以把这部分逻辑从max函数中拿出来会清晰很多吧
两个max是如果不去change应该如何
后边的两个语句是如果x变成对手应该如何
longway太牛了 其实这是dp
maxL = max(maxL, ++changed[x]);
maxL = max(maxL, ++noChange[x]);
下标如果换成 if x == else 可能更清楚
【在 m******3 的大作中提到】
: 能解释一下思路么，没太明白
|
l*********8
发帖数: 4642 | 14 谢谢apprentice00, 解释得很清楚。
【在 a**********0 的大作中提到】
: 我来解释一下？
: int changed[2] = {0, 0};
: 记录 0或者1组成的连续串最长是多少 此串变化过一次
: int noChange[2] = {0, 0};
: 记录 0或者1组成的连续串最长是多少 此串没有变化过
: change【1】 可以理解为 1的通过俘虏0的连续串得到的 so far的连续串长度
: 扫描每一个数 有几种操作
: 此数必定破坏原来对手的unchange过的串 也就是使之归零
: 此数可以变化为对手 这样 对手的change = 对手unchange +1
: 无论如何情况 都破坏了对手的unchange的串 必须归零 因为即使第二种情况 对手的
|
y***n
发帖数: 1594 | |
a***n
发帖数: 623 | 16 你这个还是不对吧。
比如 [1,1,0,1,0,0,0,0,0,0,0,0,0,0]的结果是4？不过思路挺好的，再加一个变量就
可以0空间开销了。
【在 f******t 的大作中提到】
: //f1，f2分别表示0次改变跟1次改变时，当前的最长连续1的长度
: int longestOne(const vector& arr) {
: int f1 = 0, f2 = 0, ret = 0;
: for (int i = 0; i < arr.size(); ++i) {
: if (arr[i]) {
: ++f1; ++f2;
: } else {
: f2 = f1 + 1;
: f1 = 0;
: }
|
a***n
发帖数: 623 | 17 赞解释，我是把changed数组作为大小为1的cache……
这代码面试的时候写出来估计面试官都要跪了。
【在 a**********0 的大作中提到】
: 我来解释一下？
: int changed[2] = {0, 0};
: 记录 0或者1组成的连续串最长是多少 此串变化过一次
: int noChange[2] = {0, 0};
: 记录 0或者1组成的连续串最长是多少 此串没有变化过
: change【1】 可以理解为 1的通过俘虏0的连续串得到的 so far的连续串长度
: 扫描每一个数 有几种操作
: 此数必定破坏原来对手的unchange过的串 也就是使之归零
: 此数可以变化为对手 这样 对手的change = 对手unchange +1
: 无论如何情况 都破坏了对手的unchange的串 必须归零 因为即使第二种情况 对手的
|
a***n
发帖数: 623 | 18 是不是还是有点小bug
比如[1,1,0]的时候最后一个0就没有计算，返回是2？
【在 l*********8 的大作中提到】
: int maxConsecutive(const vector & ary) {
: int changed[2] = {0, 0};
: int noChange[2] = {0, 0};
: int maxL = 0;
: for (bool x : ary) {
: maxL = max(maxL, ++changed[x]);
: maxL = max(maxL, ++noChange[x]);
: changed[1-x] = noChange[1-x];
: noChange[1-x] = 0;
: }
|
l*********8
发帖数: 4642 | 19 赞！
还是出bug啊，
改正了：
int maxConsecutive(const vector & ary) {
int changed[2] = {0, 0};
int noChange[2] = {0, 0};
int maxL = 0;
for (bool x : ary) {
++changed[x];
++noChange[x];
changed[1-x] = 1 + noChange[1-x];
noChange[1-x] = 0;
maxL = max(maxL, changed[x]);
maxL = max(maxL, changed[1-x]);
}
return maxL;
}
【在 a***n 的大作中提到】
: 是不是还是有点小bug
: 比如[1,1,0]的时候最后一个0就没有计算，返回是2？
|
y***n
发帖数: 1594 | 20 又看了一遍，太牛了。这就是差距。想想自己工资低一点，也认了。。 |
|
|
k**8
发帖数: 186 | |
c*******r
发帖数: 610 | |
b*********t
发帖数: 170 | 23 还有点问题吧，如果0000就输出4了，按题意应该是3？
【在 l*********8 的大作中提到】
: 赞！
: 还是出bug啊，
: 改正了：
: int maxConsecutive(const vector & ary) {
: int changed[2] = {0, 0};
: int noChange[2] = {0, 0};
: int maxL = 0;
: for (bool x : ary) {
: ++changed[x];
: ++noChange[x];
|
l*********8
发帖数: 4642 | 24 是的，谢谢指出。
我开始是按照“改不改一个数字都行”来做的，后来楼主clarify 要求后，我没改干净
。。。。
看似简单的题目，一定要小心再小心。
【在 b*********t 的大作中提到】
: 还有点问题吧，如果0000就输出4了，按题意应该是3？
|
m*****k
发帖数: 731 | 25 你不是说了：一个0和1组成的数组
【在 s******i 的大作中提到】
:
: 如果全是0也要改，所以应该是最长长度-1
|
h****j
发帖数: 15 | 26 Here are my 5 cents.
It will be easier to understand if we denote the position explicitly in the
iteration.
Let g_k[x] be the longest continuous `x` ending at position k, (exactly, not
at most) one change has been made.
Let f_k[x] represent the longest continous `x` ending at position k, no
change has been made.
Then we have the following iterative equations.
Update changed
g_{k+1} [x] = g_k [x] + 1
g_{k+1} [1-x] = f_k [1-x] + 1
Update unchanged
f_{k+1} [x] = f_k[x] + 1
f_{k+1} [1-x] = 0
----------------------------------------------
The corresponding code is:
int maxConsecNumChangeOne(vector &A) {
vector f(2, 0), g(2, -1);
int maxL = 0;
for (int x : A) {
g[x]++;
g[1-x] = f[1-x] + 1;
f[x]++;
f[1-x] = 0;
maxL = max(maxL, g[x]);
}
return maxL;
}
Welcome to point it out if you find any bug in the code. |
b********r
发帖数: 620 | 27
the
not
【在 h****j 的大作中提到】
: Here are my 5 cents.
: It will be easier to understand if we denote the position explicitly in the
: iteration.
: Let g_k[x] be the longest continuous `x` ending at position k, (exactly, not
: at most) one change has been made.
: Let f_k[x] represent the longest continous `x` ending at position k, no
: change has been made.
: Then we have the following iterative equations.
: Update changed
: g_{k+1} [x] = g_k [x] + 1
|
