s******d
发帖数: 61 | 1 什么是NP-complete呢？看网上有人说这方法？
我的想法是先sort， 然后在从两边开始比较，中途recursion | S**I
发帖数: 15689 | 2 没学过算法课？
http://en.wikipedia.org/wiki/NP-complete
【在 s******d 的大作中提到】
: 什么是NP-complete呢？看网上有人说这方法？
: 我的想法是先sort， 然后在从两边开始比较，中途recursion
| B*******1
发帖数: 2454 | | S**I
发帖数: 15689 | 4 这要看要不要求子数组里的元素是连续的。连续的话是polynomial，不连续的话似乎就
是NP了。
【在 B*******1 的大作中提到】
: 这题是NP-complete?
| c****x
发帖数: 61 | 5
~~NPC
不管连续不连续都是NP
【在 S**I 的大作中提到】
: 这要看要不要求子数组里的元素是连续的。连续的话是polynomial，不连续的话似乎就
: 是NP了。
| S**I
发帖数: 15689 | 6 子数组里的元素连续的话，有n个元素的数组只有n(n+1)/2个子数组，brute force也是
polynomial的。
【在 c****x 的大作中提到】
:
: ~~NPC
: 不管连续不连续都是NP
| c****x
发帖数: 61 | 7 http://en.wikipedia.org/wiki/NP_(complexity)
【在 S**I 的大作中提到】
: 子数组里的元素连续的话，有n个元素的数组只有n(n+1)/2个子数组，brute force也是
: polynomial的。
| B*******1
发帖数: 2454 | 8 en.
agree with you.
【在 S**I 的大作中提到】
: 这要看要不要求子数组里的元素是连续的。连续的话是polynomial，不连续的话似乎就
: 是NP了。
|
| a***r
发帖数: 93 | 9 memory O(n)
time O(nlogn)
//~ Given a array,find out if there exist a subarray such its sum is zero
#include
#include
using namespace std;
static void swap(int *p, int i, int j) {
int t=p[i]; p[i]=p[j];p[j]=t;
}
static int partition(int *p,int left,int right) {
int j=left;
for(int i=left;i
if(p[i]
}
swap(p,j,right);
return j;
}
static void binary_sort(int *p, int left, int right) {
if(left>=right) { return;}
int m=partition(p,left,right);
binary_sort(p,left,m-1);
binary_sort(p,m+1,right);
}
bool exist_zero_subarray(int A[], int len) throw (invalid_argument, bad_
alloc) {
if(A==NULL) { throw invalid_argument("null array"); }
int *p=(int*)calloc(len,sizeof(int));
if(p==NULL) { throw bad_alloc("mem alloc failure"); }
int *t=p;
for(int i=0;i
if(i==0) { *t=A[i]; }
else { *t=*(t-1)+A[i]; }
t++;
}
binary_sort(p,0,len-1);
bool exist = false;
t=p;
for(int i=0;i
if(*t==*(t++)) { exist=true; break; }
}
delete p;
return exist;
}
void main() {
int A[]={1,2,3,4,5,-9,-5,0,4};
cout<
} | d*******d
发帖数: 2050 | 10 你这个真的work么?
memset用得就不对.
memset(p, 0, len*sizeof(int));
【在 a***r 的大作中提到】
: memory O(n)
: time O(nlogn)
: //~ Given a array,find out if there exist a subarray such its sum is zero
: #include
: #include
: using namespace std;
: static void swap(int *p, int i, int j) {
: int t=p[i]; p[i]=p[j];p[j]=t;
: }
: static int partition(int *p,int left,int right) {
| | | a***r
发帖数: 93 | 11
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.
【在 d*******d 的大作中提到】
: 你这个真的work么?
: memset用得就不对.
: memset(p, 0, len*sizeof(int));
| B*******1
发帖数: 2454 | 12 弱问这code是找连续的还是不连续的？
calloc in the first place.
【在 a***r 的大作中提到】
:
: 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.
| d*******d
发帖数: 2050 | 13 他这个是找连续的.
【在 B*******1 的大作中提到】
: 弱问这code是找连续的还是不连续的？
:
: calloc in the first place.
| r*****s
发帖数: 51 | 14 还需要判断 *t==0，若是，则 true。
Ex： [1, 2, 3, 4, -10, 5]
另外，*t==*(t++) 总是成立的吧？
calloc in the first place.
【在 a***r 的大作中提到】
:
: 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.
| d*******d
发帖数: 2050 | 15 *t == *(t++)
估计是undefined的.
【在 r*****s 的大作中提到】
: 还需要判断 *t==0，若是，则 true。
: Ex： [1, 2, 3, 4, -10, 5]
: 另外，*t==*(t++) 总是成立的吧？
:
: calloc in the first place.
| B*******1
发帖数: 2454 | 16 谢谢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 的大作中提到】
: 他这个是找连续的.
| d*******d
发帖数: 2050 | 17 他那个code就是干这个,不过只return个bool.
如果是我的话,我会用个hashmap,不会用那个sort.
【在 B*******1 的大作中提到】
: 谢谢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个数之间的间隔吗？
: 难道我哪里错了？
| B*******1
发帖数: 2454 | 18 是的。
thanks
【在 d*******d 的大作中提到】
: 他那个code就是干这个,不过只return个bool.
: 如果是我的话,我会用个hashmap,不会用那个sort.
| a***r
发帖数: 93 | 19
yes, good point.
I was meant to use *t==*(++t), but looks like it does not work, not sure why
though.
【在 r*****s 的大作中提到】
: 还需要判断 *t==0，若是，则 true。
: Ex： [1, 2, 3, 4, -10, 5]
: 另外，*t==*(t++) 总是成立的吧？
:
: calloc in the first place.
| a***r
发帖数: 93 | 20
why picking hashmap? any time/memory reason? or easier to code?
yes, time can be reduced from O(nlogn) to O(n).
【在 d*******d 的大作中提到】
: 他那个code就是干这个,不过只return个bool.
: 如果是我的话,我会用个hashmap,不会用那个sort.
| | | a***r
发帖数: 93 | 21
The original problem was asking if exist a subarray, I figured it did not
ask for the subarray itself.
Also, it is a subarray, not a sub sequence.
【在 B*******1 的大作中提到】
: 谢谢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个数之间的间隔吗？
: 难道我哪里错了？
| j********x
发帖数: 2330 | 22 照你本来题目的描述，其实是个很简单的问题
这个题目的描述跟subset sum其实是不同的，你这里是subarray，而不是subset
【在 s******d 的大作中提到】
: 什么是NP-complete呢？看网上有人说这方法？
: 我的想法是先sort， 然后在从两边开始比较，中途recursion
| j********x
发帖数: 2330 | 23 很聪明的办法
既然是O(n)space，不如直接上hash table，还可以做到one-pass
calloc in the first place.
【在 a***r 的大作中提到】
:
: The original problem was asking if exist a subarray, I figured it did not
: ask for the subarray itself.
: Also, it is a subarray, not a sub sequence.
|
|
