logo
Redian新闻
>未名空间
>gardening - 拈花惹草
>
血皮菜？
avatar
血皮菜？# gardening - 拈花惹草
b*n
1 楼
Problems 8.10 on page 85:
Find a subarray whose sum is closest to a
given value t.
I can only think of a brute-force method:
fist build the cumulation array, then scan
from first element to the last element. Each
scan is O(n). So the solution is O(n^2). I
wonder whether there is a better solution.
Thanks.
avatar
G*h
2 楼
谢谢
avatar
f*c
3 楼
请大家帮我看看，这是血皮菜哇
avatar
h*n
4 楼
1) sort currsum array O(nlogn)
2) for each currsum[i], binary search the nearest number to currsum[i]+t (lo
gn) for each
to sum up O(nlogn)

【在 b*****n 的大作中提到】
: Problems 8.10 on page 85:
: Find a subarray whose sum is closest to a
: given value t.
: I can only think of a brute-force method:
: fist build the cumulation array, then scan
: from first element to the last element. Each
: scan is O(n). So the solution is O(n^2). I
: wonder whether there is a better solution.
: Thanks.
avatar
a*x
5 楼
梁

【在 G*****h 的大作中提到】
: 谢谢
avatar
p*y
6 楼
怎么那么多才俺都听都没听过 要在班上混不下去了
avatar
b*n
7 楼
Thank you for your reply. But there is one problem in this solution:
Suppose when you search currsum[2]+t, the closest element is currsum[0],
then that means the sum of sub-array from 0 to 2 is -t, not t, right?
avatar
n*y
8 楼
有地址或者诊所名字吗？收费怎么样？谢谢

【在 a***x 的大作中提到】
: 梁
avatar
f*c
9 楼
没办法，有的就是地域菜，我也好多没听过

【在 p*****y 的大作中提到】
: 怎么那么多才俺都听都没听过 要在班上混不下去了
avatar
h*n
10 楼
use another array to store currsum's indices to represent sorted currsum
in your case, currsum[2] would have a lower index than currsum[0]

【在 b*****n 的大作中提到】
: Thank you for your reply. But there is one problem in this solution:
: Suppose when you search currsum[2]+t, the closest element is currsum[0],
: then that means the sum of sub-array from 0 to 2 is -t, not t, right?
avatar
r*0
11 楼
这是我去的那家:
陈锐源医师; 中华广场诊所 (China square clinic)
Tel: 312-842-9888; 2171 S China Pl Chicago, IL 60616 (老四川对面)
体检费: $180/人; 打针: $30/针; X-ray:$20 or 30 (记不清了). 好象只收现金.

【在 n********y 的大作中提到】
: 有地址或者诊所名字吗？收费怎么样？谢谢
avatar
D*1
12 楼
no idea 。。。

【在 f*****c 的大作中提到】
: 请大家帮我看看，这是血皮菜哇
avatar
v*y
13 楼
The question is still intened to find a consecuritive sub array.
The solution is still one scan in O(n).
- maintain a sum of a FIFO sub array, one element out when sum > t.
avatar
r*0
14 楼
这是我去的那家:
陈锐源医师; 中华广场诊所 (China square clinic)
Tel: 312-842-9888; 2171 S China Pl Chicago, IL 60616 (老四川对面)
体检费: $180/人; 打针: $30/针; X-ray:$20 or 30 (记不清了). 好象只收现金.

【在 G*****h 的大作中提到】
: 谢谢
avatar
c*e
15 楼

紫背菜?

【在 f*****c 的大作中提到】
: 请大家帮我看看，这是血皮菜哇
avatar
s*e
16 楼
Does this still work if there can be negative numbers?
E.g. 1, -2, 3, -4, 5?
Could you please explain the FIFO sub array in more detail?
What I was thinking about is quite similar to hopen's idea
We can calculate the sum from a[0] to a[i] for each a[i]. (Say b[i]=a[0]+a[1
]+...+a[i])
In the meantime, maintain a BST to store the b[i] values
After getting b[i], we search if the node in the BST which is the most close
to t - b[i].
Then add b[i] to the BST (together with i).
It is nlogn, and one scan is enough.

【在 v******y 的大作中提到】
: The question is still intened to find a consecuritive sub array.
: The solution is still one scan in O(n).
: - maintain a sum of a FIFO sub array, one element out when sum > t.
avatar
s*g
17 楼
刘汉平(老四川对面楼上)
avatar
c*e
18 楼

求来源

【在 f*****c 的大作中提到】
: 请大家帮我看看，这是血皮菜哇
avatar
b*n
19 楼
Thank you for your replies, guys. So after the cumulation array is sorted,
we will ignore the original cum[0] and cum[1] during the binary search of
cum[2]+t. Is this the idea?
By the way, if my memory is correct, "Programming Pearls" claims that the
optimal solution to this kind of problem is nlog(n). So a linear-time
solution doesn't exist. (Note that we are looking for a subarray whose sum
is closest to t. So the sum could be either smaller or larger than t.)
Thanks again.
avatar
l*1
20 楼
看看这个链接，有图片
http://image.baidu.com/i?ct=503316480&z=&tn=baiduimagedetail&ipn=d&word=%E8%A1%80%E7%9A%AE%E8%8F%9C%E5%9B%BE%E7%89%87&ie=utf-8&in=28777&cl=2&lm=-1&st=&pn=14&rn=1&di=99140840951&ln=1416&fr=ala1&&fmq=1372030374759_R&ic=&s=&se=&sme=0&tab=&width=&height=&face=&is=&istype=&ist=&jit=&objurl=http%3A%2F%2Fwww.fpcn.net%2Ffpcn%2Fupimg%2Fsc120.jpg#pn14&-1&di99140840951&objURLhttp%3A%2F%2Fwww.fpcn.net%2Ffpcn%2Fupimg%2Fsc120.jpg&fromURLippr_z2C%24qAzdH3FAzdH3Fooo_z%26e3Burvg_z%26e3BgjpAzdH3Fip4sAzdH3Ffi5ot42_t1_dacm_z%26e3Bip4s&W630&H419&T7480&S132&TPjpg
天哪，这么长的链接！不知道大家能看到么？

【在 f*****c 的大作中提到】
: 请大家帮我看看，这是血皮菜哇
avatar
v*y
21 楼
Oops, you are right, my former solution is not good if there's negative
values... now I could only come up with divide and concur method that is
O(n*log(n)*log(n))
Could anyone explain clearly an O(n*log(n)) solution? Thanks.

b[i]=a[0]+a[1
close

【在 s*******e 的大作中提到】
: Does this still work if there can be negative numbers?
: E.g. 1, -2, 3, -4, 5?
: Could you please explain the FIFO sub array in more detail?
: What I was thinking about is quite similar to hopen's idea
: We can calculate the sum from a[0] to a[i] for each a[i]. (Say b[i]=a[0]+a[1
: ]+...+a[i])
: In the meantime, maintain a BST to store the b[i] values
: After getting b[i], we search if the node in the BST which is the most close
: to t - b[i].
: Then add b[i] to the BST (together with i).
avatar
j*u
22 楼
the link works

【在 l*****1 的大作中提到】
: 看看这个链接，有图片
: http://image.baidu.com/i?ct=503316480&z=&tn=baiduimagedetail&ipn=d&word=%E8%A1%80%E7%9A%AE%E8%8F%9C%E5%9B%BE%E7%89%87&ie=utf-8&in=28777&cl=2&lm=-1&st=&pn=14&rn=1&di=99140840951&ln=1416&fr=ala1&&fmq=1372030374759_R&ic=&s=&se=&sme=0&tab=&width=&height=&face=&is=&istype=&ist=&jit=&objurl=http%3A%2F%2Fwww.fpcn.net%2Ffpcn%2Fupimg%2Fsc120.jpg#pn14&-1&di99140840951&objURLhttp%3A%2F%2Fwww.fpcn.net%2Ffpcn%2Fupimg%2Fsc120.jpg&fromURLippr_z2C%24qAzdH3FAzdH3Fooo_z%26e3Burvg_z%26e3BgjpAzdH3Fip4sAzdH3Ffi5ot42_t1_dacm_z%26e3Bip4s&W630&H419&T7480&S132&TPjpg
: 天哪，这么长的链接！不知道大家能看到么？
avatar
b*m
23 楼
for each cum[i], should search for cum[i]+/-t. so 2nlog(n) + original sort(n
(logn)) 3nLog(n) ==> nLog(n).
avatar
a*u
24 楼
是的。又叫紫贝菜，红凤菜

【在 f*****c 的大作中提到】
: 请大家帮我看看，这是血皮菜哇
avatar
j*a
25 楼
Thanks for all posts. Just want to confirm I understand right, let me repeat
your ideas.
Assume input: 4, -1, 5, 2, 0, -2.
looks for the closest sub array for 3
0 1 2 3 4 5 get sums sort BS for 3
------------------------------------
0 | 4 3 8 10 10 8 n nlgn lgn
1 | -1 4 6 6 4 lgn lgn
2 | 5 7 7 5 lgn lgn
3 | 2 2 0 lgn lgn
4 | 0 -2 lgn lgn
5 | -2 lgn lgn
In this matrix,
Sum[0][j] is the cumulative sum.
Sum[1][j] is Sum[0][j]-a[0]. However, we don't need to compute all elements
in Sum[1][*]. Instead, we only need to compute the elements which is used in
binary search.
Sum[2][j] is Sum[1][j]-a[1]
...
For binary search, we need to keep the minimum of abs(diff). If we find an
element whose diff=sum-3=0, then it is what we want. If we did not find an
element whose diff=0, then we use the element whose abs(diff) is minimum.
sort: nlgn
binary search: nlgn
Total: nlgn
Correct me if I am wrong. Thanks.
avatar
h*s
26 楼
是自己种的？
野生的还是不要吃。 小心被洒过药
avatar
y*8
27 楼
这个我也从来没听说过，好吃否？
avatar
l*n
28 楼
什么东东，看着不是很好吃啊
avatar
l*o
29 楼
看着很象，掐点来试试。排种子！！！

【在 f*****c 的大作中提到】
: 请大家帮我看看，这是血皮菜哇
avatar
c*e
30 楼

没听说过从种子繁殖，一般插扦

【在 l*****o 的大作中提到】
: 看着很象，掐点来试试。排种子！！！
avatar
l*o
31 楼
难怪上次回国让我爸帮我搞种子没搞到。太想念这个菜了。

【在 c*****e 的大作中提到】
:
: 没听说过从种子繁殖，一般插扦
avatar
f*c
32 楼
资深人士也不知哇

【在 D*******1 的大作中提到】
: no idea 。。。
avatar
f*c
33 楼
觉得像

【在 c*****e 的大作中提到】
:
: 没听说过从种子繁殖，一般插扦
avatar
f*c
34 楼
院子里看到滴

【在 c*****e 的大作中提到】
:
: 没听说过从种子繁殖，一般插扦
avatar
f*c
35 楼
我也是在网上查了查，觉得像

【在 l*****1 的大作中提到】
: 看看这个链接，有图片
: http://image.baidu.com/i?ct=503316480&z=&tn=baiduimagedetail&ipn=d&word=%E8%A1%80%E7%9A%AE%E8%8F%9C%E5%9B%BE%E7%89%87&ie=utf-8&in=28777&cl=2&lm=-1&st=&pn=14&rn=1&di=99140840951&ln=1416&fr=ala1&&fmq=1372030374759_R&ic=&s=&se=&sme=0&tab=&width=&height=&face=&is=&istype=&ist=&jit=&objurl=http%3A%2F%2Fwww.fpcn.net%2Ffpcn%2Fupimg%2Fsc120.jpg#pn14&-1&di99140840951&objURLhttp%3A%2F%2Fwww.fpcn.net%2Ffpcn%2Fupimg%2Fsc120.jpg&fromURLippr_z2C%24qAzdH3FAzdH3Fooo_z%26e3Burvg_z%26e3BgjpAzdH3Fip4sAzdH3Ffi5ot42_t1_dacm_z%26e3Bip4s&W630&H419&T7480&S132&TPjpg
: 天哪，这么长的链接！不知道大家能看到么？
avatar
f*c
36 楼
谢谢，可惜不爱吃

【在 a**u 的大作中提到】
: 是的。又叫紫贝菜，红凤菜
avatar
f*c
37 楼
院子里长的，但我从小就不喜欢吃这东西

【在 h********s 的大作中提到】
: 是自己种的？
: 野生的还是不要吃。 小心被洒过药
avatar
f*c
38 楼
我不喜欢吃，貌似补血的

【在 y*****8 的大作中提到】
: 这个我也从来没听说过，好吃否？
avatar
f*c
39 楼
这东西有人喜欢的

【在 l*******n 的大作中提到】
: 什么东东，看着不是很好吃啊
avatar
l*o
40 楼
不爱吃，能不能拔了寄给我，我出shipping and handling fee。谢谢！

【在 f*****c 的大作中提到】
: 谢谢，可惜不爱吃
avatar
f*c
41 楼
随便来掐，我想消灭掉

【在 l*****o 的大作中提到】
: 看着很象，掐点来试试。排种子！！！
avatar
f*c
42 楼
是的，应该是插扦

【在 c*****e 的大作中提到】
:
: 没听说过从种子繁殖，一般插扦
avatar
l*o
43 楼
嗯，据说炒猪肝，月子菜。

【在 f*****c 的大作中提到】
: 我不喜欢吃，貌似补血的
avatar
f*c
44 楼
来我这里整块搬

【在 l*****o 的大作中提到】
: 难怪上次回国让我爸帮我搞种子没搞到。太想念这个菜了。
avatar
f*c
45 楼
你在哪里，会不会天气太热给闷死了

【在 l*****o 的大作中提到】
: 不爱吃，能不能拔了寄给我，我出shipping and handling fee。谢谢！
avatar
l*o
46 楼
我在德州。你的IP第一位跟我一样！

【在 f*****c 的大作中提到】
: 你在哪里，会不会天气太热给闷死了
avatar
f*c
47 楼
清炒也可以，但我总觉得有不喜欢的味道

【在 l*****o 的大作中提到】
: 嗯，据说炒猪肝，月子菜。
avatar
f*c
48 楼
我在南加，会不会被捂死，或是等天凉了再寄？

【在 l*****o 的大作中提到】
: 我在德州。你的IP第一位跟我一样！
avatar
l*o
49 楼
不知道会不会被捂死，这个东西应该挺贱的。如果能天凉了再寄更好，非常感谢！

【在 f*****c 的大作中提到】
: 我在南加，会不会被捂死，或是等天凉了再寄？
avatar
f*c
50 楼
没事，告诉我地址吧

【在 l*****o 的大作中提到】
: 不知道会不会被捂死，这个东西应该挺贱的。如果能天凉了再寄更好，非常感谢！
avatar
l*o
51 楼
我8月份要搬家，9月份我跟你联系吧。谢谢！

【在 f*****c 的大作中提到】
: 没事，告诉我地址吧
avatar
f*c
52 楼
好

【在 l*****o 的大作中提到】
: 我8月份要搬家，9月份我跟你联系吧。谢谢！
avatar
l*o
53 楼
我家都是凉拌，你可以试一下凉拌，焯一下水，也许就没有你不喜欢的味道了。

【在 f*****c 的大作中提到】
: 清炒也可以，但我总觉得有不喜欢的味道
avatar
f*c
54 楼
好的，我试试

【在 l*****o 的大作中提到】
: 我家都是凉拌，你可以试一下凉拌，焯一下水，也许就没有你不喜欢的味道了。
avatar
c*e
55 楼

也许前任房主种的。妹妹好福气。俺的前任给俺留下了毒藤。

【在 f*****c 的大作中提到】
: 院子里看到滴
avatar
f*c
56 楼
应该是，可我不喜欢吃

【在 c*****e 的大作中提到】
:
: 也许前任房主种的。妹妹好福气。俺的前任给俺留下了毒藤。
avatar
i*t
57 楼
我的前房东说这个抗癌.不过很可能是民科
我也沾酱生吃过.感觉是很健康的菜

【在 f*****c 的大作中提到】
: 请大家帮我看看，这是血皮菜哇
相关阅读
谁知道怎么种陈艾吗？番茄怎么人工授粉枇杷从子种到结果要多久请问哪里有garden里用的绳子卖？植物邮寄问题请问在夹竹桃树下种菜的问题感谢A大烧烤的炭灰能当肥料吗?后院里黑帮火拼－暴徒被成功驱赶友情提醒一下各位节约用水的盆友奔园子全景图 PK Stole的那一个！请置頂“如何贴图的”帖子。新手想贴图。。。专业育种箱$7.99，恒温恒湿今天晚上咋这冷清？水果之夜,也来凑个热闹花瓣迷你浴缸(ZZ)水塘养金鱼的看过来BSO 小兔子苹果红了南加一夜又回到冬天了
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。