Permutation Sequence题目描述代码实现Subsets题目描述代码实现Combinations题目描述代码实现
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
"123""132""213""231""312""321"Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
法一：使用递归计算这道题目。然后会发生超时。
class Solution {public: bool isSatisRule(string tmp) { char cnt[10] = {0}; int tlen = tmp.size(); for(int i = 0; i < tlen; i++) { cnt[tmp[i]-'0']++; if(cnt[tmp[i]-'0'] > 1) return false; } return true; } void permutation(string &str, string tmp, int n, int stt, int k, int &num) { if(n == stt) { num++; if(num == k) str = tmp; return; } for(int i = 1; i <= n; i++) { if(num >= k) break; string t = tmp; if(isSatisRule(tmp+char(i+'0'))) permutation(str, tmp+char(i+'0'), n, stt+1, k, num); } } string getPermutation(int n, int k) { string st; string tmp = ""; int num = 0; permutation(st, tmp, n, 0, k, num); return st; }};法二：使用回溯。然后又超时了。
class Solution {public: bool isSatisRule(string tmp) { char cnt[10] = {0}; int tlen = tmp.size(); for(int i = 0; i < tlen; i++) { cnt[tmp[i]-'0']++; if(cnt[tmp[i]-'0'] > 1) return false; } return true; } void permutation(string &str, string &tmp, int n, int stt, int k, int &num) { if(n == stt) { num++; if(num == k) str = tmp; return; } for(int i = 1; i <= n; i++) { if(num >= k) break; string t = tmp; tmp += char(i+'0'); if(isSatisRule(tmp)) permutation(str, tmp, n, stt+1, k, num); tmp = t; } } string getPermutation(int n, int k) { string st; string tmp = ""; int num = 0; permutation(st, tmp, n, 0, k, num); return st; }};法三：既然这些方法不能用，这种情况下使用公式就可以了。
class Solution {public: string getPermutation(int n, int k) { string ans = ""; int i, j, t, sum, jie; jie = 1; for (i = 1; i <= n; i++){ jie = i * jie; ans += to_string(i); } for (i = 0; i < n; i++){ jie /= n - i; for (sum = 0, j = 1; j <= n; j++){ if (sum + jie >= k) break; sum += jie; swap(ans[i], ans[i + j]); } k -= sum; } return ans; }};class Solution {public: string getPermutation(int n, int k) { int pTable[10] = {1}; for(int i = 1; i <= 9; i++) pTable[i] = i * pTable[i - 1]; string result; vector<char> numSet; numSet.push_back('1'); numSet.push_back('2'); numSet.push_back('3'); numSet.push_back('4'); numSet.push_back('5'); numSet.push_back('6'); numSet.push_back('7'); numSet.push_back('8'); numSet.push_back('9'); while(n > 0){ int temp = (k - 1) / pTable[n - 1]; result += numSet[temp]; numSet.erase(numSet.begin() + temp); k = k - temp * pTable[n - 1]; n--; } return result; }};这一题是非常典型的回溯类型的题目，就是找到一个字符串的所有的子集。
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example, If nums = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]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],]当然直接用递归的话，可以更快一些：这个思路也比较好理解。
class Solution {public: vector<vector<int> > combine(int n, int k) { vector<vector<int> > rslt; vector<int> path(k, 0); combine(n, k, rslt, path); return rslt; }PRivate: void combine(int n, int k, vector<vector<int> > &rslt, vector<int> &path) { if (k == 0) { rslt.push_back(path); return; } for (int i = n; i >= 1; i--) { path[k - 1] = i; combine(i - 1, k - 1, rslt, path); } }};新闻热点
疑难解答
