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 的大作中提到】
: 有问题啊：比如01111000，访问最后一个0
| s******n
发帖数: 3946 | 5 不是O(1)space的吧，要判断和previous能否合并，要不就保留以前的结果space>O(1)
，要不重新查time>O(n)。
【在 s**********e 的大作中提到】
: 恩，原算法有问题，漏掉了这种情况，不过把这种情况考虑进去应该就对了吧，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 的大作中提到】
: 不需要保留以前的所有结果，只需要记录下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 的大作中提到】
: 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 的大作中提到】
: 感觉有问题，在扩展当前的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 的大作中提到】
: 上面我的办法稍微改动一下，就是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 的大作中提到】
: 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 的大作中提到】
: 没看懂什么意思
: 这个如何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 的大作中提到】
: 这个题目不要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 的大作中提到】
: 这个题目不要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 的大作中提到】
: 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 的大作中提到】
: 不要钻牛角尖吗，这个方法一般的情况都可以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 的大作中提到】
: 如何O(1)时间在两组的差里找两个一样的数字（同时const space）？
| s******o
发帖数: 2233 | 26 for {1,1,0} your method returns 3
【在 b***e 的大作中提到】
: // 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 的大作中提到】
: 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 的大作中提到】
: 有问题啊：比如01111000，访问最后一个0
| s******n
发帖数: 3946 | 33 不是O(1)space的吧，要判断和previous能否合并，要不就保留以前的结果space>O(1)
，要不重新查time>O(n)。
【在 s**********e 的大作中提到】
: 恩，原算法有问题，漏掉了这种情况，不过把这种情况考虑进去应该就对了吧，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 的大作中提到】
: 不需要保留以前的所有结果，只需要记录下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 的大作中提到】
: 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 的大作中提到】
: 感觉有问题，在扩展当前的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 的大作中提到】
: 上面我的办法稍微改动一下，就是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 的大作中提到】
: 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 的大作中提到】
: 没看懂什么意思
: 这个如何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 的大作中提到】
: 这个题目不要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 的大作中提到】
: 这个题目不要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 的大作中提到】
: 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 的大作中提到】
: 不要钻牛角尖吗，这个方法一般的情况都可以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 的大作中提到】
: 如何O(1)时间在两组的差里找两个一样的数字（同时const space）？
| s******o
发帖数: 2233 | 54 for {1,1,0} your method returns 3
【在 b***e 的大作中提到】
: // 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 的大作中提到】
: 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++;
}
} |
|
