S**I
发帖数: 15689 | 1 子数组里的元素连续的话，有n个元素的数组只有n(n+1)/2个子数组，brute force也是
polynomial的。 |
|
|
|
d*******d
发帖数: 2050 | 4 你这个真的work么?
memset用得就不对.
memset(p, 0, len*sizeof(int)); |
|
a***r
发帖数: 93 | 5
yes, it is a bug, fixed, thanks for pointing it out, should have used calloc in the first place.
The algorithm should work:
If sum(from i to j)==0, then sum(0....i-1) should equal to sum(0...j)
setup an array B, such that B[i]=A[0]+...+A[i]
if A[i]+...+A[j]==0 then B[i-1]==B[j];
so only needs to find if there are duplicate items in B.
binary sort B, find duplicates, if exists then return true;
otherwise return false;
welcome to find more bugs. |
|
B*******1
发帖数: 2454 | 6 弱问这code是找连续的还是不连续的？
calloc in the first place. |
|
|
r*****s
发帖数: 51 | 8 还需要判断 *t==0，若是，则 true。
Ex： [1, 2, 3, 4, -10, 5]
另外，*t==*(t++) 总是成立的吧？
calloc in the first place. |
|
d*******d
发帖数: 2050 | 9 *t == *(t++)
估计是undefined的. |
|
B*******1
发帖数: 2454 | 10 谢谢dino
再弱问
这问题不是用presum array就可以解决了？ 看不是很懂那code
int A[]={1,2,3,4,5,-9,-5,0,4};
presum array ｛1,3,6,10,15,6,1,1,5｝；
不就是找presum array里面 相等得2个数之间的间隔吗？
难道我哪里错了？ |
|
d*******d
发帖数: 2050 | 11 他那个code就是干这个,不过只return个bool.
如果是我的话,我会用个hashmap,不会用那个sort. |
|
|
a***r
发帖数: 93 | 13
yes, good point.
I was meant to use *t==*(++t), but looks like it does not work, not sure why
though. |
|
a***r
发帖数: 93 | 14
why picking hashmap? any time/memory reason? or easier to code?
yes, time can be reduced from O(nlogn) to O(n). |
|
j********x
发帖数: 2330 | 15 很聪明的办法
既然是O(n)space，不如直接上hash table，还可以做到one-pass
calloc in the first place. |
|
d*******l
发帖数: 338 | 16 我能想到nlogn的办法，二分窗口的长度，对每个长度l检查是否有某个长为l的
subarray满足条件，这个有点tricky但我觉得应该可以O(n)做到。
.: |
|
d*******l
发帖数: 338 | 17 我能想到nlogn的办法，二分窗口的长度，对每个长度l检查是否有某个长为l的
subarray满足条件，这个有点tricky但我觉得应该可以O(n)做到。
.: |
|
|
|
|
i**d
发帖数: 357 | 21 火鸡的code并不适应MSFT的那种连续的情况。 |
|
C***y
发帖数: 2546 | 22 稍微改进一下：
1.直接sort原来的数组
2.从第一个元素开始，扫描当前元素a[i]后面的subarray (a[i+1] to a[n-1]，找和为
-a[i]的pair，因为是sorted，所以可以O（n-i)找到
复杂度应该还是O(n^2) |
|
H***e
发帖数: 476 | 23 他给的算法是:
maxsofar = 0;
maxendinghere = 0;
for i = 0: n-1
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
end
这个如果全部都是负数(-5 -1 -2 -4 -3)，算出来的是0，which is not true; 应该是
-1
我觉得应该改下:
maxsofar = -INF;
maxendinghere = -INF;
for i = 0: n-1
maxendinghere = max(maxendinghere + x[i], x[i])
maxsofar = max(maxsofar, maxendinghere)
end
am i missing something?
谢谢 |
|
|
k***t
发帖数: 276 | 25 8.1提到所有输入是负数时，定义和为零的空向量为最大向量。
练习8.7.9 让读者自己计算最大向量定义为最大负元素的情况。 |
|
|
q********c
发帖数: 1774 | 27 This is a variant of binary search. Idea:
Compare the middle item with both item[0] and item[n-1]
return the number that is equal to either one of them.
recursively do this process in both left and right subarray. |
|
q********c
发帖数: 1774 | 28 This is a variant of binary search. Idea:
Compare the middle item with both item[0] and item[n-1]
return the number that is equal to either one of them.
recursively do this process in both left and right subarray. |
|
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******n
发帖数: 3946 | 30 有问题啊：比如01111000，访问最后一个0 |
|
s******n
发帖数: 3946 | 31 不是O(1)space的吧，要判断和previous能否合并，要不就保留以前的结果space>O(1)
，要不重新查time>O(n)。 |
|
s**********e
发帖数: 326 | 32 不需要保留以前的所有结果，只需要记录下previous就可以，扫描的同时更新previous |
|
s******n
发帖数: 3946 | 33 不太明白，你写个例子或者程序
previous |
|
s**********e
发帖数: 326 | 34 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;
... 阅读全帖 |
|
e*****e
发帖数: 1275 | 35 你这个办法应该不行。
想0101010101010101010101
这样的你方法好像就不对。 |
|
|
s******n
发帖数: 3946 | 37 其实有一邪招：用原数组作为DP用，把0/1放最高位，最后恢复。 |
|
e*****e
发帖数: 1275 | 38 这个题目不要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 | 39 上面我的办法稍微改动一下，就是O(N) O(1)space的solution. |
|
|
e*****e
发帖数: 1275 | 41 O(1)不难啊，搞一个
typedef
{
int dif;
int start;
int end;
};
的数组，里面存了这个程序所能支持的所有的diff
因为这个和input 无关，我们假设支持-10，到10. |
|
H****r
发帖数: 2801 | 42 max diff might be of the order of the size of the array
so does min diff |
|
e*****e
发帖数: 1275 | 43 不要钻牛角尖吗，这个方法一般的情况都可以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 | 45 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. |
|
c****l
发帖数: 138 | 46 Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here. |
|
l****o
发帖数: 43 | 47 如何O(1)时间在两组的差里找两个一样的数字（同时const space）？ |
|
|
|
b***e
发帖数: 1419 | 50 // 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;... 阅读全帖 |
|
