m********g 发帖数: 272 | 1 如题,例子:[0,1,1,1,1,0,0,1], and the result should be [1,1,0,0]
有没有O(n)runtime and O(1) space的solution?
谢谢! | s**********e 发帖数: 326 | 2 dp题,我的思路,大家看看对不对
O(n)runtime and O(n) space的solution:
create an array of length n, len[n], len[i] represent the length of subarray
which has equal number of 1 and 0 ending at index i. Initially, set all the
element len[] to be 0.
len[i] = len[i - 1] + 2 if arr[i] = 1 - arr[i - len[i - 1] - 1]
len[i] = 0 otherwise
then scan array len[], find out the largest one
optimized solution, O(n)runtime and O(1) space的solution:
actaully, we do not need to keep array len[] since len[i] only depends on
len[i - 1], for each i, if we know len[i - 1] we can get len[i], we need
another two variables maxSubarrayLen and maxEndingIndex to record the max
length of subarray and the ending index of this subarray respectively | s******n 发帖数: 3946 | | s**********e 发帖数: 326 | 4 恩,原算法有问题,漏掉了这种情况,不过把这种情况考虑进去应该就对了吧,keep
ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
subarray时,判断是否可以跟previous合并,还是O(1)space的
【在 s******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有问题啊:比如01111000,访问最后一个0
| s******n 发帖数: 3946 | 5 不是O(1)space的吧,要判断和previous能否合并,要不就保留以前的结果space>O(1)
,要不重新查time>O(n)。
【在 s**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩,原算法有问题,漏掉了这种情况,不过把这种情况考虑进去应该就对了吧,keep : ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同 : subarray时,判断是否可以跟previous合并,还是O(1)space的
| s**********e 发帖数: 326 | 6 不需要保留以前的所有结果,只需要记录下previous就可以,扫描的同时更新previous | s******n 发帖数: 3946 | 7 不太明白,你写个例子或者程序
previous
【在 s**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不需要保留以前的所有结果,只需要记录下previous就可以,扫描的同时更新previous
| s**********e 发帖数: 326 | 8 public static void longestSubarray(int[] arr){
int prevSubarrayLen = 0;
int preSubarrayEndingIndex = -1;
int longestLen = 0;
int longestEndingIndex = -1;
int preLen = 0;
for(int i=1;i
if(i-preLen-1 >= 0 && arr[i] == 1-arr[i-preLen-1]){
preLen += 2;
if(i-preLen == preSubarrayEndingIndex)
preLen += prevSubarrayLen;
if(preLen > longestLen){
longestLen = preLen;
longestEndingIndex = i;
}
}else if(preLen > 0){
prevSubarrayLen = preLen;
preSubarrayEndingIndex = i - 1;
preLen = 0;
}
}
System.out.println(
"start index:"+(longestEndingIndex - longestLen + 1) +
" end index:"+ longestEndingIndex +
" length:"+ longestLen);
} | s******n 发帖数: 3946 | 9 感觉有问题,在扩展当前的subarray的时候,因为当前subarray的首端-1,会冲掉
preSubarray,不能单用一个变量来存presubarray。
【在 s**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : public static void longestSubarray(int[] arr){ : int prevSubarrayLen = 0; : int preSubarrayEndingIndex = -1; : int longestLen = 0; : int longestEndingIndex = -1; : int preLen = 0; : for(int i=1;i: if(i-preLen-1 >= 0 && arr[i] == 1-arr[i-preLen-1]){ : preLen += 2; : if(i-preLen == preSubarrayEndingIndex)
| e*****e 发帖数: 1275 | 10 你这个办法应该不行。
想0101010101010101010101
这样的你方法好像就不对。 | | | s**********e 发帖数: 326 | 11 没看明白,能不能给个反例?
【在 s******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉有问题,在扩展当前的subarray的时候,因为当前subarray的首端-1,会冲掉 : preSubarray,不能单用一个变量来存presubarray。
| s******n 发帖数: 3946 | 12 其实有一邪招:用原数组作为DP用,把0/1放最高位,最后恢复。 | e*****e 发帖数: 1275 | 13 这个题目不要DP。
比如如下的数组
0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
求每个位置的和(就是1 的数目)
0,1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
求每个偶数位置需要的1的数字(有相同的0,1)
0,X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
求两组的差
0,X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
找距离最远的两个一样的数字
2,从4,16
注意查查边缘,因为有可能答案是从一个奇数位到另外一个奇数位置。
不过这个答案肯定会包含一个最大的从偶数位到偶数位的。
就是0,0,1,1,0,0,0,0,1,1,1,1 | e*****e 发帖数: 1275 | 14 上面我的办法稍微改动一下,就是O(N) O(1)space的solution. | H****r 发帖数: 2801 | 15 O(1)space 是难点
【在 e*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上面我的办法稍微改动一下,就是O(N) O(1)space的solution.
| e*****e 发帖数: 1275 | 16 O(1)不难啊,搞一个
typedef
{
int dif;
int start;
int end;
};
的数组,里面存了这个程序所能支持的所有的diff
因为这个和input 无关,我们假设支持-10,到10. | H****r 发帖数: 2801 | 17 max diff might be of the order of the size of the array
so does min diff
【在 e*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(1)不难啊,搞一个 : typedef : { : int dif; : int start; : int end; : }; : 的数组,里面存了这个程序所能支持的所有的diff : 因为这个和input 无关,我们假设支持-10,到10.
| e*****e 发帖数: 1275 | 18 不要钻牛角尖吗,这个方法一般的情况都可以handle,handle不了的我就直接说我不能
处理。max diff 要和order of size array 有关,得有多少个1啊,一般面试这么说肯
定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
一定要O(1)space.
那我随便出一题目,你用bitmap做来完成O(1),我给你个数组,1,2,3,4到n+1,你说你这
个bitmap是O(1)space呢,还是O(n). | m****i 发帖数: 650 | | b***e 发帖数: 1419 | 20 His answer is not too far from being correct. In fact, it'd be much easier
if we put -1 at the 0 positions. Then all that we need to do is to get the
sum array and do a counting sort. It's still O(n) space though.
【在 m****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没看懂什么意思 : 这个如何O(n)time
| | | c****l 发帖数: 138 | 21 Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here.
【在 e*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题目不要DP。 : 比如如下的数组 : 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1 : 求每个位置的和(就是1 的数目) : 0,1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12 : 求每个偶数位置需要的1的数字(有相同的0,1) : 0,X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9 : 求两组的差 : 0,X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3 : 找距离最远的两个一样的数字
| l****o 发帖数: 43 | 22 如何O(1)时间在两组的差里找两个一样的数字(同时const space)?
【在 e*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题目不要DP。 : 比如如下的数组 : 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1 : 求每个位置的和(就是1 的数目) : 0,1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12 : 求每个偶数位置需要的1的数字(有相同的0,1) : 0,X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9 : 求两组的差 : 0,X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3 : 找距离最远的两个一样的数字
| l****o 发帖数: 43 | 23 re
【在 c****l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here.
| c****p 发帖数: 6474 | 24 bitmap这个应该还是O(n)的吧。。。
【在 e*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不要钻牛角尖吗,这个方法一般的情况都可以handle,handle不了的我就直接说我不能 : 处理。max diff 要和order of size array 有关,得有多少个1啊,一般面试这么说肯 : 定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有 : 一定要O(1)space. : 那我随便出一题目,你用bitmap做来完成O(1),我给你个数组,1,2,3,4到n+1,你说你这 : 个bitmap是O(1)space呢,还是O(n).
| b***e 发帖数: 1419 | 25 // You can run this code in your browser console, e.g. firebug with
firefox or chrome console.
var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
var getMaxZeroOneSeq = function(a) {
var sum = 0;
var max = 0;
var map = {0: 0}; // <-- here is the O(n) space needed
for (var i = 0; i < a.length; i++) {
if (a[i] == 1) {
sum++;
} else { // if (a[i] == 0)
sum--;
}
if (map[sum] == null) {
map[sum] = i;
} else {
max = Math.max(max, i - map[sum] + 1);
}
}
return max;
};
getMaxZeroOneSeq(a);
【在 l****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如何O(1)时间在两组的差里找两个一样的数字(同时const space)?
| s******o 发帖数: 2233 | 26 for {1,1,0} your method returns 3
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : // You can run this code in your browser console, e.g. firebug with : firefox or chrome console. : var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1]; : var getMaxZeroOneSeq = function(a) { : var sum = 0; : var max = 0; : var map = {0: 0}; // <-- here is the O(n) space needed : for (var i = 0; i < a.length; i++) { : if (a[i] == 1) { : sum++;
| b***e 发帖数: 1419 | 27 Modified boundary condition.
【在 s******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : for {1,1,0} your method returns 3
| c****9 发帖数: 164 | 28 写了一个,感觉上应该满足
void longsubequal(int* a,int len)
{
for(int i=0;i
{
if(a[i]==0)
a[i]=-1;
}
int prevleft = 0;
int prevright = 0;
int currentleft = 0;
int currentright = 0;
int maxlen = 0;
int pos = 0;
while(pos
{
currentleft = pos;
currentright = pos+1;
int sum=0;
while(currentleft>0&¤tright
{
sum = a[currentleft]+a[currentright];
if(currentleft==prevright)
{
currentleft = prevleft;
currentleft--;
currentright++;
}
else if(sum==0)
{
currentleft--;
currentright++;
}
else if(sum!=0)
break;
}
if(currentright-currentleft-1>maxlen)
{
maxlen = currentright-currentleft-1;
prevleft = currentleft+1;
prevright = currentright-1;
}
pos++;
}
int start = prevleft;
for(int i=0;i
{
if(a[start]==-1)
cout<<0;
else
cout<<1;
start++;
}
} | m********g 发帖数: 272 | 29 如题,例子:[0,1,1,1,1,0,0,1], and the result should be [1,1,0,0]
有没有O(n)runtime and O(1) space的solution?
谢谢! | s**********e 发帖数: 326 | 30 dp题,我的思路,大家看看对不对
O(n)runtime and O(n) space的solution:
create an array of length n, len[n], len[i] represent the length of subarray
which has equal number of 1 and 0 ending at index i. Initially, set all the
element len[] to be 0.
len[i] = len[i - 1] + 2 if arr[i] = 1 - arr[i - len[i - 1] - 1]
len[i] = 0 otherwise
then scan array len[], find out the largest one
optimized solution, O(n)runtime and O(1) space的solution:
actaully, we do not need to keep array len[] since len[i] only depends on
len[i - 1], for each i, if we know len[i - 1] we can get len[i], we need
another two variables maxSubarrayLen and maxEndingIndex to record the max
length of subarray and the ending index of this subarray respectively | | | s******n 发帖数: 3946 | 31 有问题啊:比如01111000,访问最后一个0 | s**********e 发帖数: 326 | 32 恩,原算法有问题,漏掉了这种情况,不过把这种情况考虑进去应该就对了吧,keep
ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
subarray时,判断是否可以跟previous合并,还是O(1)space的
【在 s******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有问题啊:比如01111000,访问最后一个0
| s******n 发帖数: 3946 | 33 不是O(1)space的吧,要判断和previous能否合并,要不就保留以前的结果space>O(1)
,要不重新查time>O(n)。
【在 s**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩,原算法有问题,漏掉了这种情况,不过把这种情况考虑进去应该就对了吧,keep : ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同 : subarray时,判断是否可以跟previous合并,还是O(1)space的
| s**********e 发帖数: 326 | 34 不需要保留以前的所有结果,只需要记录下previous就可以,扫描的同时更新previous | s******n 发帖数: 3946 | 35 不太明白,你写个例子或者程序
previous
【在 s**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不需要保留以前的所有结果,只需要记录下previous就可以,扫描的同时更新previous
| s**********e 发帖数: 326 | 36 public static void longestSubarray(int[] arr){
int prevSubarrayLen = 0;
int preSubarrayEndingIndex = -1;
int longestLen = 0;
int longestEndingIndex = -1;
int preLen = 0;
for(int i=1;i
if(i-preLen-1 >= 0 && arr[i] == 1-arr[i-preLen-1]){
preLen += 2;
if(i-preLen == preSubarrayEndingIndex)
preLen += prevSubarrayLen;
if(preLen > longestLen){
longestLen = preLen;
longestEndingIndex = i;
}
}else if(preLen > 0){
prevSubarrayLen = preLen;
preSubarrayEndingIndex = i - 1;
preLen = 0;
}
}
System.out.println(
"start index:"+(longestEndingIndex - longestLen + 1) +
" end index:"+ longestEndingIndex +
" length:"+ longestLen);
} | s******n 发帖数: 3946 | 37 感觉有问题,在扩展当前的subarray的时候,因为当前subarray的首端-1,会冲掉
preSubarray,不能单用一个变量来存presubarray。
【在 s**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : public static void longestSubarray(int[] arr){ : int prevSubarrayLen = 0; : int preSubarrayEndingIndex = -1; : int longestLen = 0; : int longestEndingIndex = -1; : int preLen = 0; : for(int i=1;i: if(i-preLen-1 >= 0 && arr[i] == 1-arr[i-preLen-1]){ : preLen += 2; : if(i-preLen == preSubarrayEndingIndex)
| e*****e 发帖数: 1275 | 38 你这个办法应该不行。
想0101010101010101010101
这样的你方法好像就不对。 | s**********e 发帖数: 326 | 39 没看明白,能不能给个反例?
【在 s******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉有问题,在扩展当前的subarray的时候,因为当前subarray的首端-1,会冲掉 : preSubarray,不能单用一个变量来存presubarray。
| s******n 发帖数: 3946 | 40 其实有一邪招:用原数组作为DP用,把0/1放最高位,最后恢复。 | | | e*****e 发帖数: 1275 | 41 这个题目不要DP。
比如如下的数组
0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
求每个位置的和(就是1 的数目)
0,1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
求每个偶数位置需要的1的数字(有相同的0,1)
0,X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
求两组的差
0,X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
找距离最远的两个一样的数字
2,从4,16
注意查查边缘,因为有可能答案是从一个奇数位到另外一个奇数位置。
不过这个答案肯定会包含一个最大的从偶数位到偶数位的。
就是0,0,1,1,0,0,0,0,1,1,1,1 | e*****e 发帖数: 1275 | 42 上面我的办法稍微改动一下,就是O(N) O(1)space的solution. | H****r 发帖数: 2801 | 43 O(1)space 是难点
【在 e*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上面我的办法稍微改动一下,就是O(N) O(1)space的solution.
| e*****e 发帖数: 1275 | 44 O(1)不难啊,搞一个
typedef
{
int dif;
int start;
int end;
};
的数组,里面存了这个程序所能支持的所有的diff
因为这个和input 无关,我们假设支持-10,到10. | H****r 发帖数: 2801 | 45 max diff might be of the order of the size of the array
so does min diff
【在 e*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(1)不难啊,搞一个 : typedef : { : int dif; : int start; : int end; : }; : 的数组,里面存了这个程序所能支持的所有的diff : 因为这个和input 无关,我们假设支持-10,到10.
| e*****e 发帖数: 1275 | 46 不要钻牛角尖吗,这个方法一般的情况都可以handle,handle不了的我就直接说我不能
处理。max diff 要和order of size array 有关,得有多少个1啊,一般面试这么说肯
定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
一定要O(1)space.
那我随便出一题目,你用bitmap做来完成O(1),我给你个数组,1,2,3,4到n+1,你说你这
个bitmap是O(1)space呢,还是O(n). | m****i 发帖数: 650 | | b***e 发帖数: 1419 | 48 His answer is not too far from being correct. In fact, it'd be much easier
if we put -1 at the 0 positions. Then all that we need to do is to get the
sum array and do a counting sort. It's still O(n) space though.
【在 m****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没看懂什么意思 : 这个如何O(n)time
| c****l 发帖数: 138 | 49 Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here.
【在 e*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题目不要DP。 : 比如如下的数组 : 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1 : 求每个位置的和(就是1 的数目) : 0,1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12 : 求每个偶数位置需要的1的数字(有相同的0,1) : 0,X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9 : 求两组的差 : 0,X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3 : 找距离最远的两个一样的数字
| l****o 发帖数: 43 | 50 如何O(1)时间在两组的差里找两个一样的数字(同时const space)?
【在 e*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题目不要DP。 : 比如如下的数组 : 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1 : 求每个位置的和(就是1 的数目) : 0,1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12 : 求每个偶数位置需要的1的数字(有相同的0,1) : 0,X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9 : 求两组的差 : 0,X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3 : 找距离最远的两个一样的数字
| | | l****o 发帖数: 43 | 51 re
【在 c****l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here.
| c****p 发帖数: 6474 | 52 bitmap这个应该还是O(n)的吧。。。
【在 e*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不要钻牛角尖吗,这个方法一般的情况都可以handle,handle不了的我就直接说我不能 : 处理。max diff 要和order of size array 有关,得有多少个1啊,一般面试这么说肯 : 定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有 : 一定要O(1)space. : 那我随便出一题目,你用bitmap做来完成O(1),我给你个数组,1,2,3,4到n+1,你说你这 : 个bitmap是O(1)space呢,还是O(n).
| b***e 发帖数: 1419 | 53 /*
You can run this code in your browser console, e.g. firebug with
firefox or chrome console.
*/
var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
var getMaxZeroOneSeq = function(a) {
var sum = 0;
var max = 0;
var map = {0: -1}; // <-- here is the O(n) space needed
for (var i = 0; i < a.length; i++) {
if (a[i] == 1) {
sum++;
} else { // if (a[i] == 0)
sum--;
}
if (map[sum] == null) {
map[sum] = i;
} else {
max = Math.max(max, i - map[sum]);
}
}
return max;
};
getMaxZeroOneSeq(a);
【在 l****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如何O(1)时间在两组的差里找两个一样的数字(同时const space)?
| s******o 发帖数: 2233 | 54 for {1,1,0} your method returns 3
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : // You can run this code in your browser console, e.g. firebug with : firefox or chrome console. : var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1]; : var getMaxZeroOneSeq = function(a) { : var sum = 0; : var max = 0; : var map = {0: 0}; // <-- here is the O(n) space needed : for (var i = 0; i < a.length; i++) { : if (a[i] == 1) { : sum++;
| b***e 发帖数: 1419 | 55 Modified boundary condition.
【在 s******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : for {1,1,0} your method returns 3
| c****9 发帖数: 164 | 56 写了一个,感觉上应该满足
void longsubequal(int* a,int len)
{
for(int i=0;i
{
if(a[i]==0)
a[i]=-1;
}
int prevleft = 0;
int prevright = 0;
int currentleft = 0;
int currentright = 0;
int maxlen = 0;
int pos = 0;
while(pos
{
currentleft = pos;
currentright = pos+1;
int sum=0;
while(currentleft>0&¤tright
{
sum = a[currentleft]+a[currentright];
if(currentleft==prevright)
{
currentleft = prevleft;
currentleft--;
currentright++;
}
else if(sum==0)
{
currentleft--;
currentright++;
}
else if(sum!=0)
break;
}
if(currentright-currentleft-1>maxlen)
{
maxlen = currentright-currentleft-1;
prevleft = currentleft+1;
prevright = currentright-1;
}
pos++;
}
int start = prevleft;
for(int i=0;i
{
if(a[start]==-1)
cout<<0;
else
cout<<1;
start++;
}
} |
|