logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
Re: 有人和西人动过手吗？ (转载)
avatar
Re: 有人和西人动过手吗？ (转载)# Joke - 肚皮舞运动
f*w
1 楼
Maximum sum contiguous subsequence的变种
用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列
开始想着用divide and conquer，但是没想明白怎么combine左半部分和右半部分
avatar
p*g
2 楼
【 以下文字转载自 WaterWorld 讨论区 】
发信人: juanxi (胡安 . 克塞), 信区: WaterWorld
标 题: Re: 有人和西人动过手吗？
发信站: BBS 未名空间站 (Tue Jun 19 19:05:32 2012, 美东)
疯狂英语的李阳
avatar
l*e
3 楼
s[i]=\sigma a[i] 对s排序 找相邻gap最小的

【在 f*******w 的大作中提到】
: Maximum sum contiguous subsequence的变种
: 用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列
: 开始想着用divide and conquer，但是没想明白怎么combine左半部分和右半部分
avatar
r*d
4 楼
哈哈。

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

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

【在 l***e 的大作中提到】
: s[i]=\sigma a[i] 对s排序 找相邻gap最小的
avatar
w*r
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 的大作中提到】
: Maximum sum contiguous subsequence的变种
: 用O(nlogn)的方法来check一个实数序列里是否存在和为0的连续子序列
: 开始想着用divide and conquer，但是没想明白怎么combine左半部分和右半部分
avatar
f*w
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++
avatar
y*w
8 楼
why ? sum[left_p -> right_p] is 连续的呀？

【在 f*******w 的大作中提到】
:
: 我开始也是这么想的
: 可是不对啊，这样找到的是和为0的子序列
: 但是不能保证是连续子序列
avatar
f*w
9 楼

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

【在 y*w 的大作中提到】
: why ? sum[left_p -> right_p] is 连续的呀？
avatar
g*u
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
avatar
i*7
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;
avatar
g*e
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;
avatar
i*7
13 楼
在Java里，HashSet是可以有的。
只是在C++里，hash_set是没有的。
要换成unordered_set。

【在 g**e 的大作中提到】
: This HashSet thing does not work. Avoid!
avatar
i*7
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里面测试过了。应该是可以的。
avatar
g*e
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);
: }
avatar
i*7
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
avatar
t*a
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 的大作中提到】
: 通过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;
avatar
i*7
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
avatar
t*e
19 楼
请问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;
相关阅读
可以睡三个人机器人的笑话品位真低Re: 碰到一个维族妇女 (转载)跟猫养在一起太久了 哈士奇忘记自己的真实身份 (转载)汉字就是牛比啊CNN breaking news--美军收到中国海军清晰英语通话 (转载)那是因为它大这个未成年真是现代社会扯犊子的极致留学所在的整个班全是中国人，是一种怎样的体验？(转载）欧洲人民被无人机拍的景象吓坏了 (转载)ATM机坏了，就会不断地往外吐钞票，这是不少电影中的桥段。一小伙信以为真，特地买了饮料请ATM机“喝”，打算把ATM机搞坏弄点钱。但几瓶饮料倒下去，不仅钱没吐出来，ATM机还坏了。近日，该小伙因涉嫌故意毁坏财物罪被南京秦淮警方刑事拘留，他还面临十多万元的赔偿。 9月下旬的一天早上，朝天宫附近一家银行工作人员发现，自助区的一台ATM机坏了，导致其他ATM机前排起了长队，而ATM机损坏的原因却匪夷所思，于是报警。 民警通过监控发现，当天凌晨，一名20岁左右的小伙走进银行的自助区，径直走向了损坏的ATM机。只见他拿出一张银行卡放进ATM机，选择了存款业务。可接下来发生的事让民警瞠目结舌：待ATM机的放钞口打开后，小伙掏出一个饮料瓶，直接朝着ATM机的放钞口开始倒饮料，整整两瓶饮料倒完后，他还击打了两下ATM机。随后，小伙便离开了自助银行。 这是什么情况，画面中的小伙为何要给ATM机“喝”饮料？民警百思不得其解。就在民警调查时，派出所又连续接到另外两家银行的报警，他们同样各有一台ATM机遭“毒手”。经过调取监控，是同一人干的。 种种情况表明，嫌疑人是蓄意作案。经过大量排查走访工作，民警找到了嫌疑人王某。在派出所内，王某交代了事情的经过。今年初，他和哥哥一起到南京打工。由于沉迷赌博，欠了不少钱，于是便想到银行弄些钱花花。王某说，自己曾在网上看到电影桥段：ATM机坏了后，会一直往外吐钞票，好多人疯抢。“所以我想把ATM机搞坏，让它吐钞票。” 王某能想到的让ATM机坏掉的办法就是给它“喝”饮料。案发当天凌晨，王某准备了好几瓶饮料，然后来到自助银行，将饮料灌进了ATM机的放钞口。但他没想到，连试了3台ATM机，没有一台吐钞票。 王某蓄意破坏ATM机的行为已经造成两台ATM损坏，光维修费用就超过14万元。目前，王某因涉嫌故意毁坏财物罪被秦淮警方依法刑事拘留，同时他还要承担给银行带来的损失。中国应该在南海岛上建大餐馆，buffet，或者送外卖老邢的网站发帖响应延迟是不是新的一轮骗帖子数的招数?中国女子携儿带女 持假签证闯关出国 但是被发现的原因居然是。LA是不是每年都有万圣节大游行？【万圣节活动——雷版鬼故事接龙】 (转载)加贝拒绝了孔修斯世界和平奖厉害:西安一名社区主任涉贿1.2亿 (转载)原谅我一生不羁笑点低……男子撞落女子iPhone 被斥拿国产机坐什么飞机
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。