t*a
2 楼
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
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
3 楼
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
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
4 楼
用递归 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
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
5 楼
考虑用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);
可以用一个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
6 楼
把这两个方法综合下改进:
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);
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
右
【在 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
7 楼
谢谢楼上如此详尽的回复。
程序写的很清晰,分类讨论的仔细,但有个地方我弄不明白:
若左0 右 0
{
计算两边连续0个数,取最短的指针走。x1+x2相应减少,继续找。
}
为什么 取最短的指针走?
倘若左边: 0010000000, 右边1111111111000
这种情况应该走右边
程序写的很清晰,分类讨论的仔细,但有个地方我弄不明白:
若左0 右 0
{
计算两边连续0个数,取最短的指针走。x1+x2相应减少,继续找。
}
为什么 取最短的指针走?
倘若左边: 0010000000, 右边1111111111000
这种情况应该走右边
f*g
9 楼
这个不对吧,比如
0111101010,按你的解法答案为111010,六位,实际应该是1101010,七位。
0111101010,按你的解法答案为111010,六位,实际应该是1101010,七位。
b*n
12 楼
感觉这道题是在字符串中找最长anagram的变种.
b*y
13 楼
How to define the longest anagram? Do you mean the longest palindrome?
h*k
14 楼
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?
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
15 楼
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
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
16 楼
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
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
I*g
18 楼
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
【在 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
y*d
21 楼
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.
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.
y*d
23 楼
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.
求和(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
24 楼
靠,如果反方向也来扫一遍结果取两个方向找到的最大值?或者反方向可以从
正方向找到的每个序列的最后一个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
w*3
28 楼
brute force吧,
王道
王道
w*3
30 楼
这题不大可能有线形解,
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)
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)
R*i
38 楼
这个题目可以考虑一次扫描,简单回溯的方法处理,大概是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。
:
: 中
用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
39 楼
突然想到一点,这种方法可能会出现要跟前面的序列合并的情况。
不知道有没有给出正解
【在 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++)
: {
不知道有没有给出正解
【在 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
40 楼
这个挺对的巴,其实可以不用保存最前最后两个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。
:
: 中
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
41 楼
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
modify the array (which is O(n) space anyway).
Xuedong
P*t
42 楼
This is hard. What did the interviewer say?
b*n
43 楼
这题有O(1) space解了吗?
g*t
44 楼
硬想出来的,没什么值得总结的思路,应该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();
}
}
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
45 楼
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 1one 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
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 1one 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
46 楼
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
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
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
47 楼
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
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
48 楼
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*****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
49 楼
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;
}
从零点出发,遇到'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
50 楼
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);
}
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
if(array[i]==0) {
ctZero++;
}
else ctOne++;
int min = ctOne
maxLen = min;
}
}
printf("\n");
ctZero = 0;ctOne = 0;
for(int i=0;i
printf("%d ", array[i]);
}
if(array[i]==1&&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
51 楼
可否这样子做
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。
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
52 楼
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。
不存在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
57 楼
我觉得subsequence不需要连续阿
不然这题为什么叫做subsequence阿
http://www.algorithmist.com/index.php/Longest_Increasing_Subseq
我是因为看了楼上有个c的解法似乎就是求不连续的,没有人出来指正一下,所以迷惑。
【在 g**********y 的大作中提到】
: 不连续就不会是大家热火朝天地讨论的问题了。
:
: subsequence是不是也要连续?
不然这题为什么叫做subsequence阿
http://www.algorithmist.com/index.php/Longest_Increasing_Subseq
我是因为看了楼上有个c的解法似乎就是求不连续的,没有人出来指正一下,所以迷惑。
【在 g**********y 的大作中提到】
: 不连续就不会是大家热火朝天地讨论的问题了。
:
: subsequence是不是也要连续?
UD
58 楼
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);
}
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
59 楼
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.
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
60 楼
011110 then trim either end:
trim start : 11110 -> ends as 10
trim end : 01111 -> ends as 01
UD
61 楼
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.
g*k
63 楼
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.
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
64 楼
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
65 楼
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.
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
66 楼
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
67 楼
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.
initially i=0, j=length-1, then i moves right, j moves left, whenever they
meet, it means nothing found.
m*e
68 楼
#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.
#include
void countOnesAndZeros(int &numZeros, int &numOnes, const std::vector
sequence) {
numOnes = 0;
numZeros = 0;
for(size_t i = 0; i
}
}
int trimLeft(const std::vector
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
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
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.
g*k
70 楼
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.
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
71 楼
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.
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
72 楼
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
73 楼
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
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
74 楼
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
75 楼
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
76 楼
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.
l*b
78 楼
If we can modify the array in the place, it should work in O(n) time and O(1
) space.
) space.
相关阅读
Solution Architect这个职位怎么样?工程PhD Quit后可以找工作么?applied materials in CA想学spark,有书能推荐吗?工作8个月流水帐G 家员工, 你们的股票都能拿全吗求LinkedIn内推面试请教哪位帮忙内推TripAdvisor NYCoffice的thread和process区别,parallel和concurrent 区别谁能end to end解释下user authentication怎么做有人Northrop Grumman Corporation工作吗? (转载)凡是面试回来就骂面试官的IDH1B transfer approved 还没收到邮寄的approval notice可以工作吗2012年年底,有一个进google的华人大牛帮我看看这哪错了? iterative inorder traversal做 internal tools的组有前途么?WISCONSIN EPIC直接来了40个烙印程序员 (转载)经过这几天在这的生死搏斗月光妹妹是码农么?