f*******w
发帖数: 1243 | 1 Maximum sum contiguous subsequence的变种
用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列
开始想着用divide and conquer，但是没想明白怎么combine左半部分和右半部分 |
l***e
发帖数: 6 | 2 s[i]=\sigma a[i] 对s排序 找相邻gap最小的
【在 f*******w 的大作中提到】
: Maximum sum contiguous subsequence的变种
: 用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列
: 开始想着用divide and conquer，但是没想明白怎么combine左半部分和右半部分
|
f*******w
发帖数: 1243 | 3
所以意思是如果存在和为0的子序列，对s排序之后一定有相等的2个元素吗？
好像是对的，谢谢！
【在 l***e 的大作中提到】
: s[i]=\sigma a[i] 对s排序 找相邻gap最小的
|
w*********r
发帖数: 2192 | 4 1. sorting A in ascending order
2. find the closest two points where A[i] < 0 < A[j]
3. initialize: left_p = i; right_p = j
4. if sum[left_p -> right_p] > 0; left_p--
else if (sum[left_p -> right_p] < 0); right_p++
【在 f*******w 的大作中提到】
: Maximum sum contiguous subsequence的变种
: 用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列
: 开始想着用divide and conquer，但是没想明白怎么combine左半部分和右半部分
|
f*******w
发帖数: 1243 | 5
我开始也是这么想的
可是不对啊，这样找到的是和为0的子序列
但是不能保证是连续子序列
【在 w*********r 的大作中提到】
: 1. sorting A in ascending order
: 2. find the closest two points where A[i] < 0 < A[j]
: 3. initialize: left_p = i; right_p = j
: 4. if sum[left_p -> right_p] > 0; left_p--
: else if (sum[left_p -> right_p] < 0); right_p++
|
y*w
发帖数: 42 | 6 why ? sum[left_p -> right_p] is 连续的呀？
【在 f*******w 的大作中提到】
:
: 我开始也是这么想的
: 可是不对啊，这样找到的是和为0的子序列
: 但是不能保证是连续子序列
|
f*******w
发帖数: 1243 | 7
因为你是排过序之后的连续
排序之前的不是被打乱了
【在 y*w 的大作中提到】
: why ? sum[left_p -> right_p] is 连续的呀？
|
g**u
发帖数: 583 | 8 how about this?
(1) define
b[i]=sum_{a[i]} {i=0,1,...,n-1}
(2) sort b[i]
(3) find the index j, k, such that
b[j]+b[k]=0, then we know in original array sum[ a[min{i,j}],..., a[
min{i,j}] ] =0 |
i*********7
发帖数: 348 | 9 通过A[i]序列得到sum[i]序列。
然后进行排序，排序的过程里要记录下它原先的index。
有相等的sum值就可以返回true了。
当然，也有O(n)的解法。
Double sum = 0;
HashSet hs = new HashSet
for(int i = 0; i < a.length; i++){
sum += a[i];
if(hs.contains(sum))
return true;
hs.add(sum);
}
return false; |
g**e
发帖数: 6127 | 10 This HashSet thing does not work. Avoid!
【在 i*********7 的大作中提到】
: 通过A[i]序列得到sum[i]序列。
: 然后进行排序，排序的过程里要记录下它原先的index。
: 有相等的sum值就可以返回true了。
: 当然，也有O(n)的解法。
: Double sum = 0;
: HashSet hs = new HashSet
: for(int i = 0; i < a.length; i++){
: sum += a[i];
: if(hs.contains(sum))
: return true;
|
|
|
i*********7
发帖数: 348 | 11 在Java里，HashSet是可以有的。
只是在C++里，hash_set是没有的。
要换成unordered_set。
【在 g**e 的大作中提到】
: This HashSet thing does not work. Avoid!
|
i*********7
发帖数: 348 | 12 public static boolean testDoubleHS(Double a[]){
Double sum = 0.0;
HashSet hs = new HashSet();
hs.add(sum);
for(int i = 0; i < a.length; i++){
sum += a[i];
if(hs.contains(sum))
return true;
hs.add(sum);
}
return false;
}
这个是我刚才在eclipse里面测试过了。应该是可以的。 |
g**e
发帖数: 6127 | 13 换台机器换个系统换个JVM就不一定可以了。关键问题在那个加法
[0.1, 0.2, -0.2] 当你加到第三个数的时候，很可能结果是0.10000000001，这时候
contains返回false
【在 i*********7 的大作中提到】
: public static boolean testDoubleHS(Double a[]){
: Double sum = 0.0;
: HashSet hs = new HashSet();
: hs.add(sum);
: for(int i = 0; i < a.length; i++){
: sum += a[i];
: if(hs.contains(sum))
: return true;
: hs.add(sum);
: }
|
i*********7
发帖数: 348 | 14 我明白你的意思。
双精度数的处理多少会有小数点后几位的偏差。
所以我自己才测试了一下。感觉数目比较小的时候适用。比较大的情况下我也不好说。
这本身就是C++和Java对浮点数的处理导致的。算法本身是没错的。
我也就提供一下思路。因为毕竟就算法本身而言，这个是time on, space on
而对sum排序后再比较的算法，是time onlogn, space on的。要稍微好一些。
【在 g**e 的大作中提到】
: 换台机器换个系统换个JVM就不一定可以了。关键问题在那个加法
: [0.1, 0.2, -0.2] 当你加到第三个数的时候，很可能结果是0.10000000001，这时候
: contains返回false
|
t****a
发帖数: 1212 | 15 谢谢提示。据此写clojure code如下，调试成功
(use 'incanter.core)
(defn subseqzero? [a]
(let [ac (cumulative-sum (cons 0 a))
acf (frequencies ac)]
(some #(> % 1) (vals acf))))
(def a [1 -3 4 1 -2 9])
(subseqzero? a) ; true
(def a [1 -3 4 3 -2 9])
(subseqzero? a) ; nil
【在 i*********7 的大作中提到】
: 通过A[i]序列得到sum[i]序列。
: 然后进行排序，排序的过程里要记录下它原先的index。
: 有相等的sum值就可以返回true了。
: 当然，也有O(n)的解法。
: Double sum = 0;
: HashSet hs = new HashSet
: for(int i = 0; i < a.length; i++){
: sum += a[i];
: if(hs.contains(sum))
: return true;
|
i*********7
发帖数: 348 | 16 我擦。。你的什么代码。。完全看不懂。。
好吧。。clojure是啥。。。
【在 t****a 的大作中提到】
: 谢谢提示。据此写clojure code如下，调试成功
: (use 'incanter.core)
: (defn subseqzero? [a]
: (let [ac (cumulative-sum (cons 0 a))
: acf (frequencies ac)]
: (some #(> % 1) (vals acf))))
: (def a [1 -3 4 1 -2 9])
: (subseqzero? a) ; true
: (def a [1 -3 4 3 -2 9])
: (subseqzero? a) ; nil
|
t********e
发帖数: 344 | 17 请问sum[i]序列是什么？
【在 i*********7 的大作中提到】
: 通过A[i]序列得到sum[i]序列。
: 然后进行排序，排序的过程里要记录下它原先的index。
: 有相等的sum值就可以返回true了。
: 当然，也有O(n)的解法。
: Double sum = 0;
: HashSet hs = new HashSet
: for(int i = 0; i < a.length; i++){
: sum += a[i];
: if(hs.contains(sum))
: return true;
|
