2014
11-19

LeetCode-Combinations[暴力枚举]

Combinations

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

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

1. 递归

// LeetCode, Combinations
// 深搜，递归
// 时间复杂度O(n!)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<vector<int> > result;
vector<int> path;
dfs(n, k, 1, 0, path, result);
return result;
}
private:
// start，开始的数, cur，已经选择的数目
static void dfs(int n, int k, int start, int cur,
vector<int> &path, vector<vector<int> > &result) {
if (cur == k) {
result.push_back(path);
}
for (int i = start; i <= n; ++i) {
path.push_back(i);
dfs(n, k, i + 1, cur + 1, path, result);
path.pop_back();
}
}
};

2. 迭代

// LeetCode, Combinations
// use prev_permutation()
// 时间复杂度O((n-k)!)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<int> values(n);
iota(values.begin(), values.end(), 1);

vector<bool> select(n, false);
fill_n(select.begin(), k, true);

vector<vector<int> > result;
do{
vector<int> one(k);
for (int i = 0, index = 0; i < n; ++i)
if (select[i])
one[index++] = values[i];
result.push_back(one);
} while(prev_permutation(select.begin(), select.end()));
return result;
}
};

Java代码:

public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<Integer> temp = new ArrayList<Integer>(k);
List<List<Integer>> result = new ArrayList();
combineRecur(n, 0, k, temp, result);
return result;
}

public void combineRecur(int n,int s, int k,List<Integer> temp,List<List<Integer>> result){
if(temp.size() == k ){
return;
}
if(s + k - temp.size() > n) return;
combineRecur(n, s+1, k, temp,result);
temp.remove(temp.size()-1);
combineRecur(n, s+1, k, temp,result);
}
}

Permutations

Permutations II

Next Permutation

Permutation Sequence

1. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的

2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

3. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}

4. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测