p********7
发帖数: 549 | 1 You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
algorithm to find the maximum sub sequence which has equal number of 1s and
0s.
Examples
1) 10101010
The longest sub sequence that satisfies the problem is the input itself
2)1101000
The longest sub sequence that satisfies the problem is 110100
我想到一个办法，不知道是否正确
1.因为不知道1和0谁多，不好执行算法，所以先遍历一次统计下1和0数量，选少的那个
做标准
2.想统计10，想到的办法就是如果是1就+1,如果是0就-1，如果sum ＝＝ 0就统计一次
长度，这样我们发现似乎对于上面例子这个办法可以work，不过如果上面的string反置
，这个办法就不work了，因为以为后面的0太多，而 |
h**k
发帖数: 3368 | 2 How about this case? 10 1s and 11 0s
110001110000011100011
space
and
【在 p********7 的大作中提到】
: You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
: algorithm to find the maximum sub sequence which has equal number of 1s and
: 0s.
: Examples
: 1) 10101010
: The longest sub sequence that satisfies the problem is the input itself
: 2)1101000
: The longest sub sequence that satisfies the problem is 110100
: 我想到一个办法，不知道是否正确
: 1.因为不知道1和0谁多，不好执行算法，所以先遍历一次统计下1和0数量，选少的那个
|
q**r
发帖数: 611 | |
w***h
发帖数: 415 | 4 我的思路: 应该可以观察出关于这个问题的一个数学定理,证明的过程就是这个算法.
space
and
【在 p********7 的大作中提到】
: You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
: algorithm to find the maximum sub sequence which has equal number of 1s and
: 0s.
: Examples
: 1) 10101010
: The longest sub sequence that satisfies the problem is the input itself
: 2)1101000
: The longest sub sequence that satisfies the problem is 110100
: 我想到一个办法，不知道是否正确
: 1.因为不知道1和0谁多，不好执行算法，所以先遍历一次统计下1和0数量，选少的那个
|
p********7
发帖数: 549 | 5 这个case 从左边算最长的是 11100011， 这个时候还是正数，但是已经到尾巴了，所
以长度加上这个正数值 就是6+2 = 8
从右边算也是一样是6+2 = 8
【在 h**k 的大作中提到】
: How about this case? 10 1s and 11 0s
: 110001110000011100011
:
: space
: and
|
p********7
发帖数: 549 | 6 我自己找到个反例 111100000011100000
看来这办法也不行 |
d****2
发帖数: 6250 | 7
俺在那贴给的解是这样的：
不能扫到串balance的时候就停止当前子串，记住当前位置然后继续扫到
imbalance超过余下的1或0。
这个例子有7个1和11个0，所以第二次扫的时候以1为参照
当11110000时此子串是balance的, 还有3个1余下，记住当前位置，继续往前探测
当11110000 00时imbalance是-2，还有3个1余下，继续
当11110000 00 111时没有1余下了，没必要继续了。
还要从此子串的第一个1按同样方法反向扫描看看此串还能增长否(此串前有0个1)。
最多三遍扫描，O(1) space.
【在 p********7 的大作中提到】
: 我自己找到个反例 111100000011100000
: 看来这办法也不行
|
p********7
发帖数: 549 | 8 恩，这样应该是对的
但是有个问题，如果序列很长，这么做实际上复杂度就不是N了，因为你每次扫描到-1的时候就会继续很长
比如 1001001000100010001001001001001001001001001001001001001001001001001
每次1都会向前继续很长，复杂度变成（N/3）^2了
【在 d****2 的大作中提到】
:
: 俺在那贴给的解是这样的：
: 不能扫到串balance的时候就停止当前子串，记住当前位置然后继续扫到
: imbalance超过余下的1或0。
: 这个例子有7个1和11个0，所以第二次扫的时候以1为参照
: 当11110000时此子串是balance的, 还有3个1余下，记住当前位置，继续往前探测
: 当11110000 00时imbalance是-2，还有3个1余下，继续
: 当11110000 00 111时没有1余下了，没必要继续了。
: 还要从此子串的第一个1按同样方法反向扫描看看此串还能增长否(此串前有0个1)。
: 最多三遍扫描，O(1) space.
|
h**k
发帖数: 3368 | 9 这个能处理么？
01110101010101110
【在 d****2 的大作中提到】
:
: 俺在那贴给的解是这样的：
: 不能扫到串balance的时候就停止当前子串，记住当前位置然后继续扫到
: imbalance超过余下的1或0。
: 这个例子有7个1和11个0，所以第二次扫的时候以1为参照
: 当11110000时此子串是balance的, 还有3个1余下，记住当前位置，继续往前探测
: 当11110000 00时imbalance是-2，还有3个1余下，继续
: 当11110000 00 111时没有1余下了，没必要继续了。
: 还要从此子串的第一个1按同样方法反向扫描看看此串还能增长否(此串前有0个1)。
: 最多三遍扫描，O(1) space.
|
p********7
发帖数: 549 | 10 这个1就是多的那个了，1是-1，0就是1了
【在 h**k 的大作中提到】
: 这个能处理么？
: 01110101010101110
|
|
|
w***h
发帖数: 415 | 11 大致想了一下规律，应该可以扫一边Ｏ（Ｎ），加上Ｏ（１）的额外空间．好象很直接
的方法就可以了．或许我漏了什么．
1的时候就会继续很长
【在 p********7 的大作中提到】
: 恩，这样应该是对的
: 但是有个问题，如果序列很长，这么做实际上复杂度就不是N了，因为你每次扫描到-1的时候就会继续很长
: 比如 1001001000100010001001001001001001001001001001001001001001001001001
: 每次1都会向前继续很长，复杂度变成（N/3）^2了
|
w***h
发帖数: 415 | 12 哦，说错了．是扫两遍．
【在 w***h 的大作中提到】
: 大致想了一下规律，应该可以扫一边Ｏ（Ｎ），加上Ｏ（１）的额外空间．好象很直接
: 的方法就可以了．或许我漏了什么．
:
: 1的时候就会继续很长
|
h**k
发帖数: 3368 | 13 你能不能更加准确的叙述一下你的算法？
【在 d****2 的大作中提到】
:
: 俺在那贴给的解是这样的：
: 不能扫到串balance的时候就停止当前子串，记住当前位置然后继续扫到
: imbalance超过余下的1或0。
: 这个例子有7个1和11个0，所以第二次扫的时候以1为参照
: 当11110000时此子串是balance的, 还有3个1余下，记住当前位置，继续往前探测
: 当11110000 00时imbalance是-2，还有3个1余下，继续
: 当11110000 00 111时没有1余下了，没必要继续了。
: 还要从此子串的第一个1按同样方法反向扫描看看此串还能增长否(此串前有0个1)。
: 最多三遍扫描，O(1) space.
|
p********7
发帖数: 549 | 14 我记得上次有人拿出了个dp的办法，其实我想了下，他就是没考虑到一个东西。就是除
非是因为边界限制，所有的最长序列开头都可以转换为至少有1个1的情况。
特例是0011100是因为边界限制。
所以我完全可以用那个dp的办法做
步骤是
1.扫描一次得到1，0个数，以及差值，如果是N
2.从2头遍历这个数组，遇到0，0的情况就开投指针+1 同时差值-1
如果是0/1情况，就移动0 差值-1
如果都是1，比如 10000110001
如果函数名叫int foo（int N,int head,int end）
就是max（foo(N+1,head+1，end),foo(N+1,head,end-1)）
最后就能得到结果。
3.最后再考虑是不是因为边界，这种情况只可能是包含了所有1的序列。所以就把1当作
1，0当作-1，遍历一次，看当最后一个1pass过后，总和是否能为0.
00111100 在倒数第二个就是0了，如果这样的情况存在，那么这个肯定是最长的。如果
没这种情况存在前2步的算法就是对的
【在 h**k 的大作中提到】
: 这个能处理么？
: 01110101010101110
|
p********7
发帖数: 549 | 15 你的办法复杂度变化了，最差情况是(N/3)^2
例子 001001001001001001001001001001001001001001001
【在 d****2 的大作中提到】
:
: 俺在那贴给的解是这样的：
: 不能扫到串balance的时候就停止当前子串，记住当前位置然后继续扫到
: imbalance超过余下的1或0。
: 这个例子有7个1和11个0，所以第二次扫的时候以1为参照
: 当11110000时此子串是balance的, 还有3个1余下，记住当前位置，继续往前探测
: 当11110000 00时imbalance是-2，还有3个1余下，继续
: 当11110000 00 111时没有1余下了，没必要继续了。
: 还要从此子串的第一个1按同样方法反向扫描看看此串还能增长否(此串前有0个1)。
: 最多三遍扫描，O(1) space.
|
