t****a
发帖数: 1212 | 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 | z****n
发帖数: 1379 | 2 sub-sequense还是subarray?
sub-sequense可以不连续的吧，那这题就没意义了
space
and
【在 t****a 的大作中提到】
: 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
| t*****j
发帖数: 1105 | 3 用递归 dynamic programming解。
1.先第一遍扫描出总共有多少个0，多少个1. 假设扫描结果是1的个数比0多n个的话。
2.array两头各用两个指针, 设函数 int Maxtring(int start, int end, int x), 其中
x是从start到end这两个指针之间的substring中1比0多的个数，返回的是string长度。
Maxstring的逻辑大概是：
1. 如果x=0,则return start-end+1;
2. 如果x>0,则考察start和end的string数值。
if (array[start] == 1 && array[end]== 0)
{
return Maxtring(start+1, end, x-1);
}else if (array[start] == 0 && array[end]== 1)
{
return Maxtring(start, end-1, x-1);
}else if (array[start] == 1 && array[end
【在 t****a 的大作中提到】
: 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
| t*****j
发帖数: 1105 | 4 考虑用Hash表解的话，
可以用一个variable,先从左到右扫描，累计从左到现在累计当前的1和0个数的差。
建个这么大长度的array. 扫描到某个array[i]，根据这个差hash，把i的数值存
下。如果有collision则保存最前和最后的两个位数。
扫描完以后，对每个hash地址扫描，计算最大的 最前最后两位差。
昏，这个是O(n) time, O（string的最大01差）space。
中
【在 t*****j 的大作中提到】
: 用递归 dynamic programming解。
: 1.先第一遍扫描出总共有多少个0，多少个1. 假设扫描结果是1的个数比0多n个的话。
: 2.array两头各用两个指针, 设函数 int Maxtring(int start, int end, int x), 其中
: x是从start到end这两个指针之间的substring中1比0多的个数，返回的是string长度。
: Maxstring的逻辑大概是：
: 1. 如果x=0,则return start-end+1;
: 2. 如果x>0,则考察start和end的string数值。
: if (array[start] == 1 && array[end]== 0)
: {
: return Maxtring(start+1, end, x-1);
| t*****j
发帖数: 1105 | 5 把这两个方法综合下改进：
1. 设一variable从左到右扫描，假设1比0多，则找出1比0多的个数 n. 满足条件的最长string
两头的相邻字母一定都为1或者是边境。
2. array两个各设一指针，start, end, 各设一个variable x1,x2分别对应于最左到
start指针的1比0多的个数，以及end到最右的string的1比0多的个数。
3. 若x1+x2=n,则中间的string就是最长的，问题转化为要找最小的 end-start并满足
条件的x1+x2。一步步把两边指针按照最小步速向中间挪，once x1+x2 = n，则停止。
while(x1+x2
{
if array[start]==1 && array[end]==1
{
查看两边最长的连续1,
如左边最长,且连续1个数为m，且m
若m>=n-x1-x2 则 start+n-x1-x2, return;
右
【在 t*****j 的大作中提到】
: 用递归 dynamic programming解。
: 1.先第一遍扫描出总共有多少个0，多少个1. 假设扫描结果是1的个数比0多n个的话。
: 2.array两头各用两个指针, 设函数 int Maxtring(int start, int end, int x), 其中
: x是从start到end这两个指针之间的substring中1比0多的个数，返回的是string长度。
: Maxstring的逻辑大概是：
: 1. 如果x=0,则return start-end+1;
: 2. 如果x>0,则考察start和end的string数值。
: if (array[start] == 1 && array[end]== 0)
: {
: return Maxtring(start+1, end, x-1);
| t****a
发帖数: 1212 | 6 谢谢楼上如此详尽的回复。
程序写的很清晰，分类讨论的仔细，但有个地方我弄不明白：
若左0 右 0
{
计算两边连续0个数，取最短的指针走。x1+x2相应减少，继续找。
}
为什么 取最短的指针走？
倘若左边: 0010000000, 右边1111111111000
这种情况应该走右边 | t*****j
发帖数: 1105 | 7 嗯，我说的不清楚，是计算两边连续0的个数，若左边指针的连续0个数少的话，走左边
指针。反之走右
边。这算法是我临时想的，不是啥标准答案，所以也烦请帮我验证下正确性。谢了！
【在 t****a 的大作中提到】
: 谢谢楼上如此详尽的回复。
: 程序写的很清晰，分类讨论的仔细，但有个地方我弄不明白：
: 若左0 右 0
: {
: 计算两边连续0个数，取最短的指针走。x1+x2相应减少，继续找。
: }
: 为什么 取最短的指针走？
: 倘若左边: 0010000000, 右边1111111111000
: 这种情况应该走右边
| f*********g
发帖数: 207 | 8 这个不对吧，比如
0111101010，按你的解法答案为111010，六位，实际应该是1101010，七位。 | t*****j
发帖数: 1105 | 9 之前那个解法里忘了考虑
在左右指针同0的情况下，到最近的1的距离相等的情况。这种情况下应该根据连续个1
的个数判断，
移动连续个1的个数最多的那边的指针。这样就对了。
这个序列里，6个1，4个0，则n=2.
比如开始 两个指针是同指0的，然后数，到最近1的位数都是1，这种情况下判断，左边
指针连续1个数
多，则连续移动左边指针至1，则n=3. 然后左边连移三位到n=0即停止。
【在 f*********g 的大作中提到】
: 这个不对吧，比如
: 0111101010，按你的解法答案为111010，六位，实际应该是1101010，七位。
| f*********g
发帖数: 207 | 10 不光是连续１，中间夹杂着０时一样有类似问题。
1
【在 t*****j 的大作中提到】
: 之前那个解法里忘了考虑
: 在左右指针同0的情况下，到最近的1的距离相等的情况。这种情况下应该根据连续个1
: 的个数判断，
: 移动连续个1的个数最多的那边的指针。这样就对了。
: 这个序列里，6个1，4个0，则n=2.
: 比如开始 两个指针是同指0的，然后数，到最近1的位数都是1，这种情况下判断，左边
: 指针连续1个数
: 多，则连续移动左边指针至1，则n=3. 然后左边连移三位到n=0即停止。
| | | b*****n
发帖数: 221 | 11 感觉这道题是在字符串中找最长anagram的变种. | b******y
发帖数: 126 | 12 How to define the longest anagram? Do you mean the longest palindrome? | h**k
发帖数: 3368 | 13 Give you two sequences of length N, how to find the max window of matching
patterns. The patterns can be mutated.
For example, seq1 = "ABCDEFG", seq2 = "DBCAPFG", then the max window is 4. (
ABCD from seq1 and DBCA from seq2). 起始位置无需相同。
这个我知道有O(nlogn)的算法，不知道是否有O(n)的算法。
【在 b******y 的大作中提到】
: How to define the longest anagram? Do you mean the longest palindrome?
| d****2
发帖数: 6250 | 14 1. scan first round, WLOG, assuming the number of 1 is smaller, let this
number m
2. scan from first again, find the first 1, keep it as the candidate of
current sequence start, now the remaining 1's is m-1
3. scan next element, keep tracking the balance of 1's and 0's in this
sequence, keep track of remaining 1's in the whole array
4. if 0's outnumber 1's by the remaining 1's, stop this sequence and this
seqence length is the number of 1's seen so far in this sequence, bookkeep
current maximum | f*********5
发帖数: 576 | 15 this is O(n)???
this
bookkeep
【在 d****2 的大作中提到】
: 1. scan first round, WLOG, assuming the number of 1 is smaller, let this
: number m
: 2. scan from first again, find the first 1, keep it as the candidate of
: current sequence start, now the remaining 1's is m-1
: 3. scan next element, keep tracking the balance of 1's and 0's in this
: sequence, keep track of remaining 1's in the whole array
: 4. if 0's outnumber 1's by the remaining 1's, stop this sequence and this
: seqence length is the number of 1's seen so far in this sequence, bookkeep
: current maximum
| d****2
发帖数: 6250 | 16
scanning always forward, no backtracking.
【在 f*********5 的大作中提到】
: this is O(n)???
:
: this
: bookkeep
| I*********g
发帖数: 93 | 17 could you prove it?
【在 d****2 的大作中提到】
: 1. scan first round, WLOG, assuming the number of 1 is smaller, let this
: number m
: 2. scan from first again, find the first 1, keep it as the candidate of
: current sequence start, now the remaining 1's is m-1
: 3. scan next element, keep tracking the balance of 1's and 0's in this
: sequence, keep track of remaining 1's in the whole array
: 4. if 0's outnumber 1's by the remaining 1's, stop this sequence and this
: seqence length is the number of 1's seen so far in this sequence, bookkeep
: current maximum
| f*********5
发帖数: 576 | 18 for each step,
u need O(1) or O(n) ?
【在 d****2 的大作中提到】
:
: scanning always forward, no backtracking.
| d****2
发帖数: 6250 | 19
hehe, i am waiting for someone prove it for me. try to prove when the 0's outnumber 1's
by the remaining 1's left in the array, the next sequence starting point won't be from
current sequence. there is an exception to this rule but it is ok.
【在 I*********g 的大作中提到】
: could you prove it?
| y***d
发帖数: 2330 | 20 how about 00001?
outnumber 1's
won't be from
【在 d****2 的大作中提到】
:
: hehe, i am waiting for someone prove it for me. try to prove when the 0's outnumber 1's
: by the remaining 1's left in the array, the next sequence starting point won't be from
: current sequence. there is an exception to this rule but it is ok.
| | | d****2
发帖数: 6250 | 21
algorithm works. this is THE exception for the end sequence.
length found is 1 (number of 1's) x 2 (double for 1 and 0) but
the sequence has to go back from leading 1 to fill out 0's which is
O(n) time max.
【在 y***d 的大作中提到】
: how about 00001?
:
: outnumber 1's
: won't be from
| y***d
发帖数: 2330 | 22 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0
求和（0当-1)，两个位置和一样就是一个符合条件的序列
0 1 0-1-2-3-4-3-2-1 0 1 0-1-2-3-4-3-4-3-4-3-4-3-4-3-4-5-6-7-8
按照你的扫描，
第一次从第一个 1 开始，扫描出 1 0 0 0 0 0 1 1 1 1 1 0,
第二次扫描跳过这段，接着扫描出 1 0 1 0 1 0 1 0 1 0
可是实际最大是 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1
【在 d****2 的大作中提到】
:
: algorithm works. this is THE exception for the end sequence.
: length found is 1 (number of 1's) x 2 (double for 1 and 0) but
: the sequence has to go back from leading 1 to fill out 0's which is
: O(n) time max.
| d****2
发帖数: 6250 | 23
靠，如果反方向也来扫一遍结果取两个方向找到的最大值？或者反方向可以从
正方向找到的每个序列的最后一个1开始找？？
【在 y***d 的大作中提到】
: 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0
: 求和（0当-1)，两个位置和一样就是一个符合条件的序列
: 0 1 0-1-2-3-4-3-2-1 0 1 0-1-2-3-4-3-4-3-4-3-4-3-4-3-4-5-6-7-8
: 按照你的扫描，
: 第一次从第一个 1 开始，扫描出 1 0 0 0 0 0 1 1 1 1 1 0,
: 第二次扫描跳过这段，接着扫描出 1 0 1 0 1 0 1 0 1 0
: 可是实际最大是 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1
| y***d
发帖数: 2330 | 24 恐怕也不行，关键是一些 seq 可以左右挪动，从而跟别的 seq merge
【在 d****2 的大作中提到】
:
: 靠，如果反方向也来扫一遍结果取两个方向找到的最大值？或者反方向可以从
: 正方向找到的每个序列的最后一个1开始找？？
| t*****j
发帖数: 1105 | 25 嗯，这步是有点问题，我再想想。
【在 f*********g 的大作中提到】
: 不光是连续１，中间夹杂着０时一样有类似问题。
:
: 1
| d****2
发帖数: 6250 | 26
try to prove 正方向找到的连续两个序列不可能头一个的tail和下一个的head组成一个更
大的序列？这个tail 和 head是按 1 来算得。
【在 y***d 的大作中提到】
: 恐怕也不行，关键是一些 seq 可以左右挪动，从而跟别的 seq merge
| w*****3
发帖数: 101 | | y***d
发帖数: 2330 | 28 我上面给给的那个就是反例，所以不行
一个更
【在 d****2 的大作中提到】
:
: try to prove 正方向找到的连续两个序列不可能头一个的tail和下一个的head组成一个更
: 大的序列？这个tail 和 head是按 1 来算得。
| w*****3
发帖数: 101 | 29 这题不大可能有线形解,
brute force ,O（n2）
0看成-1 第一遍扫过,序列长度减去最后一个值的绝对值就是理论上存在的最长序列L,
然后用相隔为L-1的两个指针p1,p2同时遍历,直到*p2 = 0 或者*p1 == *p2
如果没有就缩小间距直到2
最坏情况序列如下：
1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1
1 0 1 2 3 2 3 4 5 4 5 6 7 6
n 序列， 多出n/2 ，从间隔n/2扫描到间隔为2 O（n2） | b*****n
发帖数: 221 | 30 应该是palindrome.想错了.
这题O(1) space要求很苛刻.
【在 b******y 的大作中提到】
: How to define the longest anagram? Do you mean the longest palindrome?
| | | d****2
发帖数: 6250 | 31
那个例子反方向扫就找到了，俺指的是正反两方向cover all bases，所以要prove.
【在 y***d 的大作中提到】
: 我上面给给的那个就是反例，所以不行
:
: 一个更
| y***d
发帖数: 2330 | 32 这样肯定不完善，如果有三个字串的 merge，不管从哪边扫，都会有遗漏；我都懒得找
反例了
【在 d****2 的大作中提到】
:
: 那个例子反方向扫就找到了，俺指的是正反两方向cover all bases，所以要prove.
| d****2
发帖数: 6250 | 33
well, there must be some rules in the problem, otherwise it is impossible for O(
n) time and O(1) space algorithm exists.
改进算法，正方向找到一个序列后从头第一个 1 反方向扫描，看看能不能扩大。
【在 y***d 的大作中提到】
: 这样肯定不完善，如果有三个字串的 merge，不管从哪边扫，都会有遗漏；我都懒得找
: 反例了
| t**r
发帖数: 512 | 34 谁说这题一定有解？
careercup上讨论了30多个帖子，都是不正确的
impossible for O(
【在 d****2 的大作中提到】
:
: well, there must be some rules in the problem, otherwise it is impossible for O(
: n) time and O(1) space algorithm exists.
: 改进算法，正方向找到一个序列后从头第一个 1 反方向扫描，看看能不能扩大。
| d****2
发帖数: 6250 | 35
careercup是啥？网上讨论的很多都不靠谱是共识吧？
【在 t**r 的大作中提到】
: 谁说这题一定有解？
: careercup上讨论了30多个帖子，都是不正确的
:
: impossible for O(
| t**r
发帖数: 512 | 36 yes
here is not 网上
【在 d****2 的大作中提到】
:
: careercup是啥？网上讨论的很多都不靠谱是共识吧？
| R****i
发帖数: 104 | 37 这个题目可以考虑一次扫描，简单回溯的方法处理，大概是O(n)的time。
用C#检验了阿一下，好像边界处理的不够好，有些情况不能作出正确的判断，不知道各
位有没有好的办法处理
算法大概是这样的：
private string StartSearch(string str0s1s)
{
// 不知道把这一步去掉之后算不算O（1）space的了。
int[] replaceStr = new int[str0s1s.Length];
for (int i = 0; i < replaceStr.Length; i++)
{
replaceStr[i] = str0s1s[i] == '1' ? 1 : -1;
}
int iPreStart = 0;
int iPreLen = 0;
int iStart = 0;
int iE
【在 t*****j 的大作中提到】
: 考虑用Hash表解的话，
: 可以用一个variable,先从左到右扫描，累计从左到现在累计当前的1和0个数的差。
: 建个这么大长度的array. 扫描到某个array[i]，根据这个差hash，把i的数值存
: 下。如果有collision则保存最前和最后的两个位数。
: 扫描完以后，对每个hash地址扫描，计算最大的 最前最后两位差。
: 昏，这个是O(n) time, O（string的最大01差）space。
:
: 中
| R****i
发帖数: 104 | 38 突然想到一点，这种方法可能会出现要跟前面的序列合并的情况。
不知道有没有给出正解
【在 R****i 的大作中提到】
: 这个题目可以考虑一次扫描，简单回溯的方法处理，大概是O(n)的time。
: 用C#检验了阿一下，好像边界处理的不够好，有些情况不能作出正确的判断，不知道各
: 位有没有好的办法处理
: 算法大概是这样的：
: private string StartSearch(string str0s1s)
: {
: // 不知道把这一步去掉之后算不算O（1）space的了。
: int[] replaceStr = new int[str0s1s.Length];
: for (int i = 0; i < replaceStr.Length; i++)
: {
| v********w
发帖数: 136 | 39 这个挺对的巴，其实可以不用保存最前最后两个index,只保存第一次出现某个和的
index,扫描一遍不断更新max window
只不过每满足O(1)space的要求
【在 t*****j 的大作中提到】
: 考虑用Hash表解的话，
: 可以用一个variable,先从左到右扫描，累计从左到现在累计当前的1和0个数的差。
: 建个这么大长度的array. 扫描到某个array[i]，根据这个差hash，把i的数值存
: 下。如果有collision则保存最前和最后的两个位数。
: 扫描完以后，对每个hash地址扫描，计算最大的 最前最后两位差。
: 昏，这个是O(n) time, O（string的最大01差）space。
:
: 中
| s****a
发帖数: 528 | 40 I don't think there is O(1) space solution with O(n) time, unless you can
modify the array (which is O(n) space anyway).
Xuedong | | | P***t
发帖数: 1006 | 41 This is hard. What did the interviewer say? | b*****n
发帖数: 221 | | g**t
发帖数: 3 | 43 硬想出来的，没什么值得总结的思路，应该work，也满足条件。大家测测吧
public class Longest10Substring {
public static void main(String[] args) {
calc(new int[] { 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0 });
calc(new int[] { 0 });
}
public static void calc(int[] a) {
int n = a.length;
int minority = 0, cnt = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 1) {
cnt++;
}
}
if (cnt == 0 || cnt == n) {
print(a, 0, 0);
return;
}
if (cnt < n / 2) {
minority = 1;
} else if (cnt > n / 2) {
minority = 0;
} else if ((n & 1) == 0) {
print(a, 0, n);
return;
} else {
minority = 1;
}
int numofMinority = 0, sum = 0, start = 0, end = 0;
int longestStart = 0, maxLength = 0;
for (int i = 0; i < n; i++) {
if (sum == 0) {
end = i - 1;
}
if (a[i] == minority) {
if ((-sum) > cnt - numofMinority) {
if (end - start > maxLength) {
longestStart = start;
maxLength = end - start + 1;
}
start = i;
end = i;
cnt -= numofMinority;
numofMinority = 0;
sum = 0;
}
numofMinority += 1;
sum += 1;
} else {
sum -= 1;
}
}
if (sum == 0) {
end = n - 1;
} else if (sum > 0) {
end = n - 1;
start = start - sum;
}
if (end - start + 1 > maxLength) {
longestStart = start;
maxLength = end - start + 1;
}
print(a, longestStart, maxLength);
}
public static void print(int[] a, int start, int length) {
System.out.println("start at: " + start);
System.out.println("length: " + length);
for (int i = start; i < start + length; i++) {
System.out.print(a[i]);
}
System.out.println();
}
} | k****n
发帖数: 369 | 44 I have following observations:
the longest subsequence must be one of following cases:
1) the whole sequence
2) starts from one end and ends at some middle point
3) starts from mid point A and ends at mid point B
1) is trivial
2) is also easy, in O(n) time can do
so what we need to do is find the longest subsequence for case 3)
suppose the longest subsequence is
b_i, b_i+1, ..., b_j-1, b_j
where 1
one immediate conclusion is b_i-1 and b_j+1 cannot be different.
without loss of generality, assume we have u 1's and v 0's and u>v
can b_i-1 and a_j+1 be both 0's? apparently not
so the form must be
...1[xxxx...xxx]1...
So we can come up with a O(n^2) solution, that is, for each 1, test
all other 1's whether the string between them are 01 balanced.
after this, a O(n) solution is almost ready:
1) find the leftmost 1, mark with lcursor
2) from the right end, find the first position that gives a balanced 01
string
mark with rcursor
3) move lcursor right to the next 1
4) move rcursor right to the next balanced 01 string
5) loop 3, until (lcursor is too right OR right cursor reaches the right end)
apparently this is O(n)
space
and
【在 t****a 的大作中提到】
: 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
| k****n
发帖数: 369 | 45 code:
int testOneWay(int b[], int size, int start, int step, int w[], int diff);
int longest01(int b[], int n) {
int n0=0, n1=0;
count(b, n, &n0, &n1);
if (n0==n1) return n;
int w[2];
w[0]=1, w[1]=-1, more=0;
if (n0
int l1 = testOneWay(b, n, 0, 1, w, abs(n0-n1));
if (l1 == 2*MIN(n0,n1)) return l1;
l1 = testOneWay(b, n, n-1, -1, w, abs(n0-n1));
if (l1 == 2*MIN(n0,n1)) return l1;
int lc=0, rc=n-1;
int diff = abs(n0-n1);
while (b[lc+1] != more) {
diff += w[b[lc++]];
}
while (b[rc-1] != more && diff != 0) {
diff += w[b[rc--]];
}
//since 1 side balanced sequence has been tested, so it guarantees
// a mid solution can be found
int maxl = rc - lc - 1;
while (n - lc > maxl && rc < n) {
do {
diff += w[b[++lc]];
} while (b[lc+1] != more && n-lc > maxl);
if (n-lc <= maxl) return maxl;
do {
diff += w[b[++rc]];
} while (diff != 0 && rc < n);
if (rc >= n) return maxl;
}
return maxl;
}
a little too complicated... will skip the oneway probing function...
【在 k****n 的大作中提到】
: I have following observations:
: the longest subsequence must be one of following cases:
: 1) the whole sequence
: 2) starts from one end and ends at some middle point
: 3) starts from mid point A and ends at mid point B
: 1) is trivial
: 2) is also easy, in O(n) time can do
: so what we need to do is find the longest subsequence for case 3)
: suppose the longest subsequence is
: b_i, b_i+1, ..., b_j-1, b_j
| g*****k
发帖数: 623 | 46 It seems not true.
Here is a counter example.
0011111100011111
It is obvious that longest subarray is 111000 or 000111
but according to your algorithm, initially lcursor points the left most 1
and I'm not sure about what do you mean lcursor is too right.
In this case, rcursor should point to the second left 0. (is lcursor too
right?)
Anyway, when you move lcursor right, now rcursor will go the right end and
miss finding 111000.
I'm not sure if there is O(n) time and O(1) space solution for this.
Just very hard to prove the correctness of any proposed algorithm.
【在 k****n 的大作中提到】
: I have following observations:
: the longest subsequence must be one of following cases:
: 1) the whole sequence
: 2) starts from one end and ends at some middle point
: 3) starts from mid point A and ends at mid point B
: 1) is trivial
: 2) is also easy, in O(n) time can do
: so what we need to do is find the longest subsequence for case 3)
: suppose the longest subsequence is
: b_i, b_i+1, ..., b_j-1, b_j
| k****n
发帖数: 369 | 47 you're right...
【在 g*****k 的大作中提到】
: It seems not true.
: Here is a counter example.
: 0011111100011111
: It is obvious that longest subarray is 111000 or 000111
: but according to your algorithm, initially lcursor points the left most 1
: and I'm not sure about what do you mean lcursor is too right.
: In this case, rcursor should point to the second left 0. (is lcursor too
: right?)
: Anyway, when you move lcursor right, now rcursor will go the right end and
: miss finding 111000.
| g**********y
发帖数: 14569 | 48 Time O(n), Space O(n)的解法，版上给的例子都能运行过。
从零点出发，遇到'0'加1，遇到'1'减1, 这个图是个单步只增1或减1的连续函数。假设
0比1多k
从左到右找第一个值为-t(0<=t<=k)的位置，保存在数组left
从右到左找第一个值为t(-k>=t>=0)的位置，保存在数组right
right和left对应位置的最大差就是解。
解释可能不太清楚，见code.
public int longest(String a) {
char[] c = a.toCharArray();
int N = a.length();
int[] b = new int[N+1];
b[0] = 0;
for (int i=1; i<=N; i++) {
b[i] = b[i-1] + (c[i-1]=='0'? 1 : -1);
}
if (b[N] > 0) for (int i=0; i<=N; i++) b[i] = -b[i];
int k = -b[N];
int[] left = new int[k+1];
int[] right = new int[k+1];
int t = 0;
for (int i=0; i<=N; i++) {
if (b[i] == -t) {
left[t] = i;
t++;
if (t > k) break;
}
}
t = -k;
for (int i=N; i>=0; i--) {
if (b[i] == t) {
right[-t] = i;
t++;
if (t > 0) break;
}
}
int max = 0;
for (int i=0; i<=k; i++) {
max = Math.max(max, right[i] - left[i]);
}
return max;
} | d***e
发帖数: 793 | 49 We are not finding the longest substring here. so any longest subsequence
will do.
This method scans twice which is O(n) and use no buffer only integer
variables which O(1)space.
void getSubseq(int *array, int len){
int maxLen = 0;
int ctZero = 0, ctOne = 0;
for(int i=0;i
printf("%d ", array[i]);
if(array[i]==0) {
ctZero++;
}
else ctOne++;
int min = ctOne
if(min>maxLen){
maxLen = min;
}
}
printf("\n");
ctZero = 0;ctOne = 0;
for(int i=0;i
if(array[i]==0&&ctZero
ctZero++;
printf("%d ", array[i]);
}
if(array[i]==1&&ctOne
ctOne++;
printf("%d ", array[i]);
}
}
//printf("\n");
}
int main (int argc, const char * argv[]) {
int array[10] = {0,1,1,1,1,0,0,1,1};
getSubseq(array, 10);
} | s*****y
发帖数: 897 | 50 可否这样子做
1.扫描array,得到0的数目cntZero, 和1的数目cntOne.
如果cntZero 〉cntOne 那么这个subsequence一定是有cntOne 个1和cntOne 个0
2.如果cntZero 〉cntOne,从左向右扫描，从第一个遇到的1开始count，记下这个起点
，定义两个变量，stack = 0 ones = 0，接着望右扫描，遇到0就stack-1 ,遇到就
stack-1和ones +1，一直到某个点，stack ==0 和ones == cntOne 记下这个终点，就
退出。
但是有特殊情况就是这种 0000000001111，那么在整个array都scan完以后如果stack!=
0 和ones == cntOne,那么就从起点往左扫描，直到找到一个点stack == 0 和ones == cntOne。
只定义了2个变量，scan了2次array。 | | | g**********y
发帖数: 14569 | 51 11000010
不存在stack=0, ones=cntOne(3)的时候。
!=
= cntOne。
【在 s*****y 的大作中提到】
: 可否这样子做
: 1.扫描array,得到0的数目cntZero, 和1的数目cntOne.
: 如果cntZero 〉cntOne 那么这个subsequence一定是有cntOne 个1和cntOne 个0
: 2.如果cntZero 〉cntOne,从左向右扫描，从第一个遇到的1开始count，记下这个起点
: ，定义两个变量，stack = 0 ones = 0，接着望右扫描，遇到0就stack-1 ,遇到就
: stack-1和ones +1，一直到某个点，stack ==0 和ones == cntOne 记下这个终点，就
: 退出。
: 但是有特殊情况就是这种 0000000001111，那么在整个array都scan完以后如果stack!=
: 0 和ones == cntOne,那么就从起点往左扫描，直到找到一个点stack == 0 和ones == cntOne。
: 只定义了2个变量，scan了2次array。
| s*****y
发帖数: 897 | 52 thanks
的确不work，考虑不周全。
By the way,这个subsequence就是要不要连续的啊？subarray是连续的，subsequence是不是也要连续？
【在 g**********y 的大作中提到】
: 11000010
: 不存在stack=0, ones=cntOne(3)的时候。
:
: !=
: = cntOne。
| g**********y
发帖数: 14569 | 53 不连续就不会是大家热火朝天地讨论的问题了。
subsequence是不是也要连续？
【在 s*****y 的大作中提到】
: thanks
: 的确不work，考虑不周全。
: By the way,这个subsequence就是要不要连续的啊？subarray是连续的，subsequence是不是也要连续？
| k****n
发帖数: 369 | 54 不连续还有啥可讨论的。。。
subsequence是不是也要连续？
【在 s*****y 的大作中提到】
: thanks
: 的确不work，考虑不周全。
: By the way,这个subsequence就是要不要连续的啊？subarray是连续的，subsequence是不是也要连续？
| g*****k
发帖数: 623 | 55 要是不连续这题做不了面试题吧。
【在 k****n 的大作中提到】
: 不连续还有啥可讨论的。。。
:
: subsequence是不是也要连续？
| s*****y
发帖数: 897 | 56 我觉得subsequence不需要连续阿
不然这题为什么叫做subsequence阿
http://www.algorithmist.com/index.php/Longest_Increasing_Subseq
我是因为看了楼上有个c的解法似乎就是求不连续的，没有人出来指正一下，所以迷惑。
【在 g**********y 的大作中提到】
: 不连续就不会是大家热火朝天地讨论的问题了。
:
: subsequence是不是也要连续？
| UD
发帖数: 182 | 57 below code seems to work, and should be O(n) time and O(1) space, if you disagree, please list your argument.
The idea behind is the use and resue of sum(i,j), that's why the O(1) space.
sum(i,j)=sum of all the 1s between i and j.
sub-seq(i,j) has equal 1s and 0s when sum(i,j)*2=j-i+1, we start by setting i=0,j=A.length-1, then searching from both ends.
1. if sum(i,j)*2==j-i+1, then found it
2. else if sum(i,j)*2>j-i+1, we have more 1s then 0s, then we check A[i] and A[j]:
a. if A[i]==A[j], then we can skip either i or j, for example, we can set i+=1 or j-=1, and sum-=A[i], and search recursively.
b. else if A[i] == 1, then we skip i, reset i,j,sum, search recursively
c. else, skip j, reset i,j,sum, search recursively
3. else, we have more 0s then 1s, then we apply almost the same logic as step 2.
sum is the only space used, and since it is being reused, thus O(1)
#include
#include
void print_array(int A[], int left, int right)
{
for(int i=left; i
{
printf("%d ", A[i]);
}
printf("\n");
}
long cal_sum(int A[], int left, int right)
{
long sum = 0;
for(int i=left; i
{
sum = sum + A[i];
}
return sum;
}
void find_subseq(int A[], long sum, int left, int right)
{
if(right==left)
{
printf("not found");
return;
}
int length = right-left+1;
if(sum*2 == length)
{
// found it
print_array(A, left, right);
return;
}
if(A[left]==A[right])
{
// when head and tail are the same, we can skip either head or tail
// let's skip head.
sum -= A[left];
left +=1;
}
else if(A[left]==1) // A[right]==0
{
if(sum*2>length) // more 1 then 0
{
sum-=A[left];
left+=1;
}
else // more 0 than 1
{
sum -=A[right];
right -=1;
}
}
else // A[left]==0, A[right]==1
{
if(sum*2>length) // more 1 then 0
{
sum-=A[right];
right-=1;
}
else // more 0 than 1
{
sum -=A[left];
left+=1;
}
}
find_subseq(A, sum, left,right);
}
void main(int argc, char* argv[])
{
int A[] = {0,0,0,1,1,1,1,0,0,0,0,0};
long sum = cal_sum(A, 0, sizeof(A)/sizeof(A[0])-1);
find_subseq(A, sum, 0, sizeof(A)/sizeof(A[0])-1);
} | g**********y
发帖数: 14569 | 58 how come sum(i, j) be constant space? 0<=i
disagree, please list your argument.
space.
setting i=0,j=A.length-1, then searching from both ends.
and A[j]:
set i+=1 or j-=1, and sum-=A[i], and search recursively.
step 2.
【在 UD 的大作中提到】
: below code seems to work, and should be O(n) time and O(1) space, if you disagree, please list your argument.
: The idea behind is the use and resue of sum(i,j), that's why the O(1) space.
: sum(i,j)=sum of all the 1s between i and j.
: sub-seq(i,j) has equal 1s and 0s when sum(i,j)*2=j-i+1, we start by setting i=0,j=A.length-1, then searching from both ends.
: 1. if sum(i,j)*2==j-i+1, then found it
: 2. else if sum(i,j)*2>j-i+1, we have more 1s then 0s, then we check A[i] and A[j]:
: a. if A[i]==A[j], then we can skip either i or j, for example, we can set i+=1 or j-=1, and sum-=A[i], and search recursively.
: b. else if A[i] == 1, then we skip i, reset i,j,sum, search recursively
: c. else, skip j, reset i,j,sum, search recursively
: 3. else, we have more 0s then 1s, then we apply almost the same logic as step 2.
| UD
发帖数: 182 | 59
011110 then trim either end:
trim start : 11110 -> ends as 10
trim end : 01111 -> ends as 01 | UD
发帖数: 182 | 60
this is sum(i,j), i as left, j as right.
long cal_sum(int A[], int left, int right)
{
long sum = 0;
for(int i=left; i
{
sum = sum + A[i];
}
return sum;
}
say A[5]=11100
sum(0,5)=A[0]+A[1]+...+A[5]=3 --> this is time O(n), n=5, space O(1)
【在 g**********y 的大作中提到】
: how come sum(i, j) be constant space? 0<=i:
: disagree, please list your argument.
: space.
: setting i=0,j=A.length-1, then searching from both ends.
: and A[j]:
: set i+=1 or j-=1, and sum-=A[i], and search recursively.
: step 2.
| | | m******e
发帖数: 353 | 61 xixi
【在 UD 的大作中提到】
:
: this is sum(i,j), i as left, j as right.
: long cal_sum(int A[], int left, int right)
: {
: long sum = 0;
: for(int i=left; i: {
: sum = sum + A[i];
: }
: return sum;
| g*****k
发帖数: 623 | 62 wrong,
you can't prove your second step would get the longest subarray in O(1) time.
I think you can come up with a counter example easily by yourself
disagree, please list your argument.
space.
setting i=0,j=A.length-1, then searching from both ends.
and A[j]:
set i+=1 or j-=1, and sum-=A[i], and search recursively.
step 2.
【在 UD 的大作中提到】
: below code seems to work, and should be O(n) time and O(1) space, if you disagree, please list your argument.
: The idea behind is the use and resue of sum(i,j), that's why the O(1) space.
: sum(i,j)=sum of all the 1s between i and j.
: sub-seq(i,j) has equal 1s and 0s when sum(i,j)*2=j-i+1, we start by setting i=0,j=A.length-1, then searching from both ends.
: 1. if sum(i,j)*2==j-i+1, then found it
: 2. else if sum(i,j)*2>j-i+1, we have more 1s then 0s, then we check A[i] and A[j]:
: a. if A[i]==A[j], then we can skip either i or j, for example, we can set i+=1 or j-=1, and sum-=A[i], and search recursively.
: b. else if A[i] == 1, then we skip i, reset i,j,sum, search recursively
: c. else, skip j, reset i,j,sum, search recursively
: 3. else, we have more 0s then 1s, then we apply almost the same logic as step 2.
| UD
发帖数: 182 | 63
time.
Not sure what do you mean? isn't O(1) for space? do you mind giving more
details?
I actually tried to find counter examples, so far I was not successful.
【在 g*****k 的大作中提到】
: wrong,
: you can't prove your second step would get the longest subarray in O(1) time.
: I think you can come up with a counter example easily by yourself
:
: disagree, please list your argument.
: space.
: setting i=0,j=A.length-1, then searching from both ends.
: and A[j]:
: set i+=1 or j-=1, and sum-=A[i], and search recursively.
: step 2.
| g*****k
发帖数: 623 | 64 your second step using O(1) space, but you can't find the longest subarray
in O(1) time in the second step. In order to have O(n) time, your second
step has to be in O(1) or in other words, i and j only need to move O(n)
times in total. Then it comes to show
It can be done by just moving i always right and moving j always left.
for your algorithm, I do not see this property.
Let me give a counter example, you will see.
1100101101010111111111111
^ ^
i j
let's say i points to the 1th and j points to 6th, 110010 is the longest
subarray starting from i.
Now when you move i to the 2th position, what happens?
the longest subarray is 1001011010. in this case, j should moves right!
and there is no guarantee, you can find j in O(1) time.
【在 UD 的大作中提到】
:
: time.
: Not sure what do you mean? isn't O(1) for space? do you mind giving more
: details?
: I actually tried to find counter examples, so far I was not successful.
| UD
发帖数: 182 | 65
time.
I think I actually can prove my step 2 will return the longest subarray:
say A[i,j] have more 1s than 0s, to get the longest subarray, you will need
to trim from either head or tail:
when head and tail are not equal, trim the end with 1 -> this is obvious
when both head and tail are 1 or 0, we need to prove trimming from head or
tail are the same:
trimming from head we get: [[subsub]0]
trimming from tail we get : [0[subsub]]
since the order of 0 does not change the totally 1s and 0s, this proves
that trimming from head or tail are the same.
overall proves step 2 will return the longest subarray.
There is exactly n=A.length iterations, in each iteration, we trim one
element and set left/right/sum once. so overall time is O(n).
【在 g*****k 的大作中提到】
: wrong,
: you can't prove your second step would get the longest subarray in O(1) time.
: I think you can come up with a counter example easily by yourself
:
: disagree, please list your argument.
: space.
: setting i=0,j=A.length-1, then searching from both ends.
: and A[j]:
: set i+=1 or j-=1, and sum-=A[i], and search recursively.
: step 2.
| UD
发帖数: 182 | 66 hm... not sure if I misunderstand something, but my code always move i to right and j to left:
initially i=0, j=length-1, then i moves right, j moves left, whenever they
meet, it means nothing found. | m******e
发帖数: 353 | 67 #include
#include
void countOnesAndZeros(int &numZeros, int &numOnes, const std::vector &
sequence) {
numOnes = 0;
numZeros = 0;
for(size_t i = 0; i
sequence[i] == 1 ? ++ numOnes : ++ numZeros;
}
}
int trimLeft(const std::vector &sequence, int start, int numToTrim, int
untilSeenSymbol) {
int trimCnt = 0;
while(start + trimCnt >= 0 && start + trimCnt < (int) sequence.size() &&
numToTrim > 0) {
if(sequence[start+trimCnt] != untilSeenSymbol) {
++trimCnt;
--numToTrim;
} else {
break;
}
}
return trimCnt;
}
int trimRight(const std::vector &sequence, int start, int numToTrim,
int untilSeenSymbol) {
int trimCnt = 0;
while(start - trimCnt >= 0 && start - trimCnt < (int) sequence.size() &&
numToTrim > 0) {
if(sequence[start-trimCnt] != untilSeenSymbol) {
++trimCnt;
--numToTrim;
} else {
break;
}
}
return trimCnt;
}
void lessMore(int numZero, int numOne, int &numLess, int &numMore, int &
lessSymbol, int &moreSymbol, int &numToTrim) {
if(numOne < numZero) {
numLess = numOne;
numMore = numZero;
lessSymbol = 1;
moreSymbol = 0;
} else {
numLess = numZero;
numMore = numOne;
lessSymbol = 0;
moreSymbol = 0;
}
numToTrim = numMore - numLess;
std::cout << numZero << " " << numOne << " " << numLess << " " <<
numMore << " " << lessSymbol << " " << moreSymbol << " " << numToTrim << "\n
";
}
int main(int argc, const char* argv[]) {
std::vector sequence;
for(int i=1; i < argc; ++i) {
int n;
if(sscanf(argv[i], "%d", &n) > 0) {
sequence.push_back(n);
std::cout << n << " ";
}
}
std::cout << std::endl;
int num[] = {0, 0};
countOnesAndZeros(num[0], num[1], sequence);
int numLess, numMore, lessSymbol, moreSymbol, numToTrim;
lessMore(num[0], num[1], numLess, numMore, lessSymbol, moreSymbol,
numToTrim);
int low = 0;
int high = (int) sequence.size()-1;
while(numLess >= 0 && numMore >= 0 && numToTrim >=0) {
int trimCnt = trimLeft(sequence, low, numToTrim, lessSymbol);
numToTrim -= trimCnt;
low += trimCnt;
num[moreSymbol] -= trimCnt;
std::cout << "trimed less " << trimCnt << " from left, " <<
numToTrim << " to trim\n";
if(numToTrim == 0) break;
trimCnt = trimRight(sequence, high, numToTrim, lessSymbol);
numToTrim -= trimCnt;
high -= trimCnt;
num[moreSymbol] -= trimCnt;
std::cout << "trimed less " << trimCnt << " from right, "<<
numToTrim << " to trim\n";
if(numToTrim == 0) break;
//we have trimmed what we can...
trimCnt = trimLeft(sequence, low, 1, moreSymbol);
if(trimCnt == 0) {
std::cout << "Empty\n";
return -1;
}
++low;
++numToTrim;
--num[lessSymbol];
std::cout << "trimed more " << trimCnt << " from left, "<< numToTrim
<< " to trim\n";
lessMore(num[0], num[1], numLess, numMore, lessSymbol, moreSymbol,
numToTrim);
}
for(int i=low; i<=high; i++) {
std::cout << sequence[i] << " ";
}
std::cout << std::endl;
return 0;
}
right and j to left:
【在 UD 的大作中提到】
: hm... not sure if I misunderstand something, but my code always move i to right and j to left:
: initially i=0, j=length-1, then i moves right, j moves left, whenever they
: meet, it means nothing found.
| m******e
发帖数: 353 | 68 may not be pretty but i think it works...
&
【在 m******e 的大作中提到】
: #include
: #include
: void countOnesAndZeros(int &numZeros, int &numOnes, const std::vector &
: sequence) {
: numOnes = 0;
: numZeros = 0;
: for(size_t i = 0; i: sequence[i] == 1 ? ++ numOnes : ++ numZeros;
: }
: }
| g*****k
发帖数: 623 | 69 your proof is totally wrong, I have to say.
when head and tail are equal, it is not same to trim from either end.
when head and tail are not equal, and it is not always true to trim the end
that is 1.
need
or
【在 UD 的大作中提到】
: hm... not sure if I misunderstand something, but my code always move i to right and j to left:
: initially i=0, j=length-1, then i moves right, j moves left, whenever they
: meet, it means nothing found.
| g*****k
发帖数: 623 | 70 if you could not understand, then run your code or algorithm for the example
I gave to you.
right and j to left:
【在 UD 的大作中提到】
: hm... not sure if I misunderstand something, but my code always move i to right and j to left:
: initially i=0, j=length-1, then i moves right, j moves left, whenever they
: meet, it means nothing found.
| | | UD
发帖数: 182 | 71
example
this is your example:
1100101101010111111111111
I am getting this result:
>./array_find_subseq
0 0 1 0 1 1 0 1 0 1 0 1
>Exit code: 0
it is one of the right answers.
the answer in your previous post, seems not right, there should be 6 0s.
>>the longest subarray is 1001011010. in this case, j should moves right!
and there is no guarantee, you can find j in O(1) time.
【在 g*****k 的大作中提到】
: if you could not understand, then run your code or algorithm for the example
: I gave to you.
:
: right and j to left:
| g*****k
发帖数: 623 | 72 sorry, my bad,
it seems that it is true that we can always trim the end that is 1 when head
and tail are not equal, we can prove it by induction, I believe.
I'll try to prove the first claim then
end
【在 g*****k 的大作中提到】
: your proof is totally wrong, I have to say.
: when head and tail are equal, it is not same to trim from either end.
: when head and tail are not equal, and it is not always true to trim the end
: that is 1.
:
: need
: or
| UD
发帖数: 182 | 73
end
I kind of believe trim from head or tail, only affects which one of all the
correct results to return - there could be many good results.
for example: for your input
1,1,0,0,1,0,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1
if I trim from head, I will eventually get 001011010101
if I trim from tail, I will eventually get 100101101010
they are both correct answers.
【在 g*****k 的大作中提到】
: your proof is totally wrong, I have to say.
: when head and tail are equal, it is not same to trim from either end.
: when head and tail are not equal, and it is not always true to trim the end
: that is 1.
:
: need
: or
| UD
发帖数: 182 | 74
head
head
There were more context in my original post:
when there are more 1s than 0s, when head and tail are not equal, trim end
with value 1.
when there are more 0s than 1s, when head and tail are not equal, trim end
with value 0.
So, not always trim the end with value 1.
【在 g*****k 的大作中提到】
: sorry, my bad,
: it seems that it is true that we can always trim the end that is 1 when head
: and tail are not equal, we can prove it by induction, I believe.
: I'll try to prove the first claim then
:
: end
| UD
发帖数: 182 | 75
the
hm.... this is incorrect.
does not work when input is for example : 00011111100
【在 UD 的大作中提到】
:
: head
: head
: There were more context in my original post:
: when there are more 1s than 0s, when head and tail are not equal, trim end
: with value 1.
: when there are more 0s than 1s, when head and tail are not equal, trim end
: with value 0.
: So, not always trim the end with value 1.
| s*****y
发帖数: 897 | 76 Also this one does not work:
{1,1,0,0,0,0,1,0};
【在 UD 的大作中提到】
:
: the
: hm.... this is incorrect.
: does not work when input is for example : 00011111100
| l*********b
发帖数: 1541 | 77 If we can modify the array in the place, it should work in O(n) time and O(1
) space. |
|
