j*****y
发帖数: 1071 | 1 Given two integers n and k, return all possible combinations of k numbers
out of 1 ... n |
p*****2
发帖数: 21240 | 2 肯定有呀。最笨的就是先生成k=1的，然后k=2的，最后k=k的。 |
j*****y
发帖数: 1071 | 3 感觉这个方法会产生很多重复阿。 比如 我要生成一个 k = n 的集合，开始有好多个
集合，最后只有一个
【在 p*****2 的大作中提到】
: 肯定有呀。最笨的就是先生成k=1的，然后k=2的，最后k=k的。
|
p*****2
发帖数: 21240 | 4 怎么会有重复呢？比如n=3, k=2
k=1
1
2
3
k=2
2 1
3 1
3 2
是不是就可以了？ |
j*****y
发帖数: 1071 | 5 比如 n = 3, k = 3 呢 ?
【在 p*****2 的大作中提到】
: 怎么会有重复呢？比如n=3, k=2
: k=1
: 1
: 2
: 3
: k=2
: 2 1
: 3 1
: 3 2
: 是不是就可以了？
|
p*****2
发帖数: 21240 | 6
k=2
k=3
3 2 1
【在 j*****y 的大作中提到】
: 比如 n = 3, k = 3 呢 ?
|
j*****y
发帖数: 1071 | 7 二爷讲讲如何由 k=2 生成 k = 3 ?
【在 p*****2 的大作中提到】
:
: k=2
: k=3
: 3 2 1
|
p*****2
发帖数: 21240 | 8
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 ?
|
j*****y
发帖数: 1071 | 9 这个思路不错
【在 p*****2 的大作中提到】
:
: k=2
: k=3
: 3 2 1
: 第一个是2 1
: 比2大的是3， 因此加入变成 3 2 1
: 3 1 比3大的没有，因此抛弃
: 3 2 同理
: 不过我这个是笨法子，我也没怎么好好想。
|
j******2
发帖数: 362 | 10 用个queue >，把数先都放进取，每次取个vector出来，如果长度够k，就
放到结果里，不然就把末尾追加加一，直到queue空。 |
|
|
p*****2
发帖数: 21240 | 11
大牛还在面啥公司呢？
【在 j*****y 的大作中提到】
: 这个思路不错
|
j*****y
发帖数: 1071 | 12 决定效仿二爷，以做题目为第一， offer 第二了 :)
【在 p*****2 的大作中提到】
:
: 大牛还在面啥公司呢？
|
p*****2
发帖数: 21240 | 13
握爪。要做好长期打算。
【在 j*****y 的大作中提到】
: 决定效仿二爷，以做题目为第一， offer 第二了 :)
|
s**s
发帖数: 70 | 14 这个心态好，娱乐为主啊。
【在 p*****2 的大作中提到】
:
: 握爪。要做好长期打算。
|
x***y
发帖数: 633 | 15 和打印电话号码的所有字母组合挺像的；只是要保证给定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
}
} |
r*********n
发帖数: 4553 | 16 基本上就是类似生成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*******3
发帖数: 58 | 17 我发现你的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********0
发帖数: 74 | 18 同握, 水到渠自成
【在 p*****2 的大作中提到】
:
: 握爪。要做好长期打算。
|
h********0
发帖数: 74 | 19 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*********n
发帖数: 4553 | 20 不会吧，就是用了个c++11的range for loop和auto吧，其实就是懒人code，大多数算
法题还是要老老实实的用index写
还有这里用list的好处是减少copy，不过这些都是marginal concern
【在 d*******3 的大作中提到】
: 我发现你的c++代码写得好高级
|
|
|
j*****y
发帖数: 1071 | 21 能写个 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***y
发帖数: 633 | 22 大概就是那个思路了(我好久没写C++了)
int A[k];
int i,j;
for(i=0; i
A[i] = 1;
}
//print A
while(true){
for(j=0; j
if(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*******3
发帖数: 58 | 23 看来是我out了~我这土鳖连C++98都没整明白，还得向大牛学习啊。。。
【在 r*********n 的大作中提到】
: 不会吧，就是用了个c++11的range for loop和auto吧，其实就是懒人code，大多数算
: 法题还是要老老实实的用index写
: 还有这里用list的好处是减少copy，不过这些都是marginal concern
|
