Re: 有人和西人动过手吗？ (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

Re: 有人和西人动过手吗？ (转载)

Re: 有人和西人动过手吗？ (转载)# Joke - 肚皮舞运动

f*w2012-06-19 07:06

1 楼

Maximum sum contiguous subsequence的变种
用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列
开始想着用divide and conquer，但是没想明白怎么combine左半部分和右半部分

p*g2012-06-19 07:06

2 楼

【以下文字转载自 WaterWorld 讨论区】
发信人: juanxi (胡安 . 克塞), 信区: WaterWorld
标题: Re: 有人和西人动过手吗？
发信站: BBS 未名空间站 (Tue Jun 19 19:05:32 2012, 美东)
疯狂英语的李阳

l*e2012-06-19 07:06

3 楼

s[i]=\sigma a[i] 对s排序找相邻gap最小的

【在 f*******w 的大作中提到】

: Maximum sum contiguous subsequence的变种
: 用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列
: 开始想着用divide and conquer，但是没想明白怎么combine左半部分和右半部分

r*d2012-06-19 07:06

4 楼

哈哈。

【在 p*********g 的大作中提到】

: 【以下文字转载自 WaterWorld 讨论区】
: 发信人: juanxi (胡安 . 克塞), 信区: WaterWorld
: 标题: Re: 有人和西人动过手吗？
: 发信站: BBS 未名空间站 (Tue Jun 19 19:05:32 2012, 美东)
: 疯狂英语的李阳

f*w2012-06-19 07:06

5 楼

所以意思是如果存在和为0的子序列，对s排序之后一定有相等的2个元素吗？
好像是对的，谢谢！

【在 l***e 的大作中提到】

: s[i]=\sigma a[i] 对s排序找相邻gap最小的

w*r2012-06-19 07:06

6 楼

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 的大作中提到】

f*w2012-06-19 07:06

7 楼

我开始也是这么想的
可是不对啊，这样找到的是和为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*w2012-06-19 07:06

8 楼

why ? sum[left_p -> right_p] is 连续的呀？

【在 f*******w 的大作中提到】

:
: 我开始也是这么想的
: 可是不对啊，这样找到的是和为0的子序列
: 但是不能保证是连续子序列

f*w2012-06-19 07:06

9 楼

因为你是排过序之后的连续
排序之前的不是被打乱了

【在 y*w 的大作中提到】

: why ? sum[left_p -> right_p] is 连续的呀？

g*u2012-06-19 07:06

10 楼

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*72012-06-19 07:06

11 楼

通过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*e2012-06-19 07:06

12 楼

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*72012-06-19 07:06

13 楼

在Java里，HashSet是可以有的。
只是在C++里，hash_set是没有的。
要换成unordered_set。

【在 g**e 的大作中提到】

: This HashSet thing does not work. Avoid!

i*72012-06-19 07:06

14 楼

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*e2012-06-19 07:06

15 楼

换台机器换个系统换个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*72012-06-19 07:06

16 楼

我明白你的意思。
双精度数的处理多少会有小数点后几位的偏差。
所以我自己才测试了一下。感觉数目比较小的时候适用。比较大的情况下我也不好说。
这本身就是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*a2012-06-19 07:06

17 楼

谢谢提示。据此写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 的大作中提到】

i*72012-06-19 07:06

18 楼

我擦。。你的什么代码。。完全看不懂。。
好吧。。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*e2012-06-19 07:06

19 楼

请问sum[i]序列是什么？

【在 i*********7 的大作中提到】