今天才发现 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

今天才发现 (转载)

今天才发现 (转载)# Joke - 肚皮舞运动

r*h2012-12-04 08:12

1 楼

一个

j*y2012-12-04 08:12

2 楼

Given two integers n and k, return all possible combinations of k numbers
out of 1 ... n

z*u2012-12-04 08:12

3 楼

att
有点事情想要问一下

t*e2012-12-04 08:12

4 楼

正好要买个苹果键盘和鼠标，从 FW 看见了这个：
Enter Code GXTPOFES at checkout.
Link to Computer Accessories category:
http://www.amazon.com/b/?node=172456

t*o2012-12-04 08:12

5 楼

【以下文字转载自 Apple 讨论区】
发信人: roadrr (roadrr), 信区: Apple
标题: 今天才发现
发信站: BBS 未名空间站 (Tue Dec 4 17:04:21 2012, 美东)
果版是分在“电脑网络”这个类别下的，
是不是要求版务把果版归在“文学艺术”一类，如果不行，归在“情感杂想”也不错。
来，大家各抒己见。

p*22012-12-04 08:12

6 楼

肯定有呀。最笨的就是先生成k=1的，然后k=2的，最后k=k的。

Y*r2012-12-04 08:12

7 楼

请说

【在 z*****u 的大作中提到】

: att
: 有点事情想要问一下

v*n2012-12-04 08:12

8 楼

赞, coupon有效期??

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

: 正好要买个苹果键盘和鼠标，从 FW 看见了这个：
: Enter Code GXTPOFES at checkout.
: Link to Computer Accessories category:
: http://www.amazon.com/b/?node=172456

R*a2012-12-04 08:12

9 楼

应该归于花木园艺的子版吧

【在 t*****o 的大作中提到】

: 【以下文字转载自 Apple 讨论区】
: 发信人: roadrr (roadrr), 信区: Apple
: 标题: 今天才发现
: 发信站: BBS 未名空间站 (Tue Dec 4 17:04:21 2012, 美东)
: 果版是分在“电脑网络”这个类别下的，
: 是不是要求版务把果版归在“文学艺术”一类，如果不行，归在“情感杂想”也不错。
: 来，大家各抒己见。

j*y2012-12-04 08:12

10 楼

感觉这个方法会产生很多重复阿。比如我要生成一个 k = n 的集合，开始有好多个
集合，最后只有一个

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

: 肯定有呀。最笨的就是先生成k=1的，然后k=2的，最后k=k的。

t*r2012-12-04 08:12

11 楼

不是宗教？

【在 R***a 的大作中提到】

: 应该归于花木园艺的子版吧

p*22012-12-04 08:12

12 楼

怎么会有重复呢？比如n=3, k=2
k=1
1
2
3
k=2
2 1
3 1
3 2
是不是就可以了？

wy2012-12-04 08:12

13 楼

瞧把你酸得

【在 t********r 的大作中提到】

: 不是宗教？

j*y2012-12-04 08:12

14 楼

比如 n = 3, k = 3 呢 ?

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

: 怎么会有重复呢？比如n=3, k=2
: k=1
: 1
: 2
: 3
: k=2
: 2 1
: 3 1
: 3 2
: 是不是就可以了？

H*72012-12-04 08:12

15 楼

敌我分明，归8区

p*22012-12-04 08:12

16 楼

k=2
k=3
3 2 1

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

: 比如 n = 3, k = 3 呢 ?

t*r2012-12-04 08:12

17 楼

擦，俺也是新晋果论牙

【在 wy 的大作中提到】

: 瞧把你酸得

j*y2012-12-04 08:12

18 楼

二爷讲讲如何由 k=2 生成 k = 3 ?

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

:
: k=2
: k=3
: 3 2 1

o*12012-12-04 08:12

19 楼

funny. 既然是苹果，更好的是农业版吧。

【在 t*****o 的大作中提到】

p*22012-12-04 08:12

20 楼

k=2
k=3
3 2 1
第一个是2 1
比2大的是3，因此加入变成 3 2 1
3 1 比3大的没有，因此抛弃
3 2 同理
不过我这个是笨法子，我也没怎么好好想。

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

: 二爷讲讲如何由 k=2 生成 k = 3 ?

l*o2012-12-04 08:12

21 楼

我觉得归时事区比较好。

j*y2012-12-04 08:12

22 楼

这个思路不错

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

:
: k=2
: k=3
: 3 2 1
: 第一个是2 1
: 比2大的是3，因此加入变成 3 2 1
: 3 1 比3大的没有，因此抛弃
: 3 2 同理
: 不过我这个是笨法子，我也没怎么好好想。

M*n2012-12-04 08:12

23 楼

我还是觉得宗教最好

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

: 我觉得归时事区比较好。

j*22012-12-04 08:12

24 楼

用个queue >，把数先都放进取，每次取个vector出来，如果长度够k，就
放到结果里，不然就把末尾追加加一，直到queue空。

s*a2012-12-04 08:12

25 楼

求医问药

p*22012-12-04 08:12

26 楼

大牛还在面啥公司呢？

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

: 这个思路不错

o*12012-12-04 08:12

27 楼

归爱情版，period.

【在 s*******a 的大作中提到】

: 求医问药

j*y2012-12-04 08:12

28 楼

决定效仿二爷，以做题目为第一， offer 第二了 :)

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

:
: 大牛还在面啥公司呢？

i*a2012-12-04 08:12

29 楼

应该放Joke板，省了ZT的麻烦.
[发表自未名空间手机版 - m.mitbbs.com]

p*22012-12-04 08:12

30 楼

握爪。要做好长期打算。

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

: 决定效仿二爷，以做题目为第一， offer 第二了 :)

l*o2012-12-04 08:12

31 楼

要不我退一步，fashion版吧。

【在 M******n 的大作中提到】

: 我还是觉得宗教最好

s*s2012-12-04 08:12

32 楼

这个心态好，娱乐为主啊。

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

:
: 握爪。要做好长期打算。

g*n2012-12-04 08:12

33 楼

果版应该跟彩虹版放一个板块。

x*y2012-12-04 08:12

34 楼

和打印电话号码的所有字母组合挺像的；只是要保证给定k位数A，从个位到高位上每
个位置的数字大小非递减来避免重复。初始值A=11.。。。1;从低位到高位搜索，第一
个i
, A[i+1]-A[i]>=1, A[i]++, A[0 to i-1] 回到初始值；如果不存在， A[k-1]++， A[
0 to k-2]回到初始值；如果不存在，而且A[k-1] =N, 则结束。这张两个loop 就行
了。
A=....
while(True）{
for(i....){
update A
}
}

l*k2012-12-04 08:12

35 楼

看来看去，还是这个建议最靠谱

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

: 要不我退一步，fashion版吧。

r*n2012-12-04 08:12

36 楼

基本上就是类似生成all subsets的方法，只不过要判断一下长度是不是等于k
list comb(const string& alphabet, int k){
if( alphabet.empty() || k == 0 ) return list();
list sets(1), tmp, ret;
for(const auto& x:alphabet){
for(const auto& r:sets){
if( r.size() + 1 == k ) ret.push_back(r+x);
else tmp.push_back(r+x);
}
sets.splice(sets.end(),tmp);
}
return ret;
}

d*32012-12-04 08:12

37 楼

我发现你的c++代码写得好高级

【在 r*********n 的大作中提到】

: 基本上就是类似生成all subsets的方法，只不过要判断一下长度是不是等于k
: list comb(const string& alphabet, int k){
: if( alphabet.empty() || k == 0 ) return list();
: list sets(1), tmp, ret;
: for(const auto& x:alphabet){
: for(const auto& r:sets){
: if( r.size() + 1 == k ) ret.push_back(r+x);
: else tmp.push_back(r+x);
: }
: sets.splice(sets.end(),tmp);

h*02012-12-04 08:12

38 楼

同握, 水到渠自成

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

:
: 握爪。要做好长期打算。

h*02012-12-04 08:12

39 楼

public ArrayList> combine_iterative(int n, int k) {
ArrayList> result = new ArrayList>
();

ArrayList list;
int end = n-k+1;
for(int i=1; i<= end; i++){
list = new ArrayList();
list.add(i);

result.add(list);
}

ArrayList listTmp;
for(int i = 1; i< k; i++){
//int len = result.size();
for(int j = result.size(); j>0; j-- ){
list = result.get(0);
result.remove(0);

for(int p = list.get(list.size() - 1) + 1; p <= end + i; p++ ){
listTmp = new ArrayList();
listTmp.addAll(list);
listTmp.add(p);
result.add(listTmp);
}

}
}

return result;
}

【在 j******2 的大作中提到】

: 用个queue >，把数先都放进取，每次取个vector出来，如果长度够k，就
: 放到结果里，不然就把末尾追加加一，直到queue空。

r*n2012-12-04 08:12

40 楼

不会吧，就是用了个c++11的range for loop和auto吧，其实就是懒人code，大多数算
法题还是要老老实实的用index写
还有这里用list的好处是减少copy，不过这些都是marginal concern

【在 d*******3 的大作中提到】

: 我发现你的c++代码写得好高级

j*y2012-12-04 08:12

41 楼

能写个 code吗？ thanks.

A[

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

: 和打印电话号码的所有字母组合挺像的；只是要保证给定k位数A，从个位到高位上每
: 个位置的数字大小非递减来避免重复。初始值A=11.。。。1;从低位到高位搜索，第一
: 个i
: , A[i+1]-A[i]>=1, A[i]++, A[0 to i-1] 回到初始值；如果不存在， A[k-1]++， A[
: 0 to k-2]回到初始值；如果不存在，而且A[k-1] =N, 则结束。这张两个loop 就行
: 了。
: A=....
: while(True）{
: for(i....){
: update A

x*y2012-12-04 08:12

42 楼

大概就是那个思路了(我好久没写C++了)
int A[k];
int i,j;
for(i=0; iA[i] = 1;
}
//print A
while(true){
for(j=0; jif(A[j]A[j]++;
break;
}
A[j] = 1；
}
if(j==k-1)
A[k-1]++;
if(A[k-1]==N+1){
break;
}
//print A
}

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

: 能写个 code吗？ thanks.
:
: A[

d*32012-12-04 08:12

43 楼

看来是我out了~我这土鳖连C++98都没整明白，还得向大牛学习啊。。。

【在 r*********n 的大作中提到】

: 不会吧，就是用了个c++11的range for loop和auto吧，其实就是懒人code，大多数算
: 法题还是要老老实实的用index写
: 还有这里用list的好处是减少copy，不过这些都是marginal concern