Combinations
找到 n 中所有 长度为 k 的不重复的组合
my solution (60ms, top 99.97%)
通过问题代换, 可以转换成一种很好理解并易于编写的问题
将问题看做 找出范围 n 中所有满足 p(x) 的整数 x
(和 31. Next Permutation 类似, 我是从中得到的启发)
其中 x 一开始为 ∑k << (n - k); [k=1], 即 n = 4, x = 1234
n = 4, k = 2
1 2 3 4
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4],
n = 4, k = 3
1 2 3 4
[1,2,3],
[1,2,4],
[1,3,4],
[2,3,4]
他们都按照一定规律, 满足下一个数比上一个数大
这个规则 p(x) 用语言描述, 就是:
从后往前找一个当前下标小于当前下标的最大值的数
如果找到了, 当前下标存储的值自增, 后续下标以当前下标为基准, 顺序 +1
如果没找到, 返回所有已找到的
代码描述如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public:
vector<vector<int>> combine(int n, int k) {
if (k > n) return {};
_n = n, _k = k;
for (int i = 1; i <= k; ++i) {
_cur.push_back(i);
}
vector<vector<int>> ret;
ret.emplace_back(_cur);
while (true) {
getNextNums();
if (_cur.size() != 0)
ret.emplace_back(_cur);
else
break;
}
return ret;
}
public:
void getNextNums() {
for (int i = _k - 1; i >= 0; --i) {
if ( _cur[i] < _n - _k + i + 1 ) {
_cur[i] += 1;
for (int j = i + 1, s = _cur[i] + 1; j < _k; ++j)
_cur[j] = s++;
return;
}
}
_cur.clear();
}
vector<int> _cur;
int _n, _k;
};
|
combine 和 getNextNums 的逻辑都相当简单, 写起来很容易
best solution (56ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
void combine(vector<vector<int>> &result, vector<int> &item, int beg, int end, int index) {
int k = item.size() - index;
if (k == 0) {
result.push_back(item);
return;
}
for (int i = beg; i <= end - k + 1; ++i) {
item[index] = i;
combine(result, item, i + 1, end, index + 1);
}
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
if (n <= 0 || k <= 0) {
return result;
}
vector<int> item(k);
item[0] = 1;
combine(result, item, 1, n, 0);
return result;
}
};
|
emmm, 好奇怪啊, 逻辑上来说想的都是一样的, 为什么他少 4ms 呢… ( 或许是因为通过 this 指针获取变量的锅? )
他用递归的形式来实现, 每次递归中会从当前起始索引循环到结束索引
当数组的长度到达 k 的时候, 就返回
值得一提的是, 他用索引的形式避免了那个会被多次修改的 item 以值形式传递
(我放弃使用递归的一部分原因就是因为暂时想不到什么方法避免那个临时的数组, 原来还可以这样…)