leetcode里面應(yīng)該有很多個與permutation相關(guān)的問題，那么首先就先寫出一個全排列把酿傍。
code:
#include <iostream>
#include <vector>
using namespace std;
void helper(vector<int>& nums, vector<int> rec, vector<vector<int>>& ans, vector<int> visited){
if( rec.size() == nums.size() ){
ans.push_back(rec);
}
else{
for(int i=0; i<nums.size(); i++){
if( visited[i] == 1 ) continue;
else{
rec.push_back( nums[i] );
visited[i] = 1;
helper(nums, rec, ans, visited);
rec.pop_back();
visited[i] = 0;
}
}
}
}
int main(int argc, char const *argv[])
{
/* code */
// generate a permutation using backtracing
vector<int> nums = {1, 2, 3, 4};
vector<int> rec;
vector<int> visited = {0, 0, 0, 0};
vector< vector<int> > ans;
helper( nums, rec, ans, visited);
int counter = 0;
for(auto a : ans){
counter ++;
for( auto i : a ){
cout << i << " ";
}
cout << endl;
};
cout<< "Total Num is: "<< counter << endl;
return 0;
}
output:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
Total Num is: 24
道理其實(shí)很簡單弛秋，就是簡單的backtracking。其實(shí)用什么樹去解釋會讓人越來越糊涂铺韧，我建議就是自己跟著迭代跑一遍多矮，然后就會非常地清晰了。
但是在這個的基礎(chǔ)上哈打，leetcode又衍生出來許多其他的題型塔逃，下面就列舉幾個。
- Permutation Sequence
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 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.
Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
這道題的意思就是求在全排列當(dāng)中第k個排列料仗，其實(shí)使用我們上面的代碼就可以直接求出來:
class Solution {
void helper(vector<int>& nums, vector<int> rec, vector<vector<int>>& ans, vector<int> visited){
if( rec.size() == nums.size() ){
ans.push_back(rec);
}
else{
for(int i=0; i<nums.size(); i++){
if( visited[i] == 1 ) continue;
else{
rec.push_back( nums[i] );
visited[i] = 1;
helper(nums, rec, ans, visited);
rec.pop_back();
visited[i] = 0;
}
}
}
}
public:
string getPermutation(int n, int k) {
// 先生成數(shù)組
vector<int> nums;
for(int i=0;i<n;i++) nums.push_back(i+1);
// 生成記錄是否訪問過的數(shù)組
vector<int> visited(n);
vector< vector<int>> ans;
vector<int> rec;
helper( nums, rec, ans, visited);
string result;
// 輸出答案
for( auto a: ans[k-1] ){
result.push_back((char)(a + '0'));
}
return result;
}
};
這里有個需要注意的地方湾盗，在C++類型當(dāng)中，char和int類型是可以相互轉(zhuǎn)換的：
內(nèi)容為數(shù)字的char立轧，包含
0,1,2,3,4,5,6,7,8,9
共計(jì)10個字符格粪。
這十個字符在存為字符型時(shí)，其存儲值為對應(yīng)的ascii碼氛改，而這些ascii碼是連續(xù)的帐萎，且按照其本身數(shù)字的大小來排列。
這樣就可以將字符值胜卤，減去起始ascii碼值實(shí)現(xiàn)轉(zhuǎn)為對應(yīng)值的效果疆导。
設(shè)
int a; //轉(zhuǎn)換的目標(biāo)變量。
char c = '7'; //要轉(zhuǎn)換的字符瑰艘。
c = a - '0';
這樣得到的就是對應(yīng)的值了是鬼，即c = 7。
如果在文件中需要多次該操作紫新，則可以定義一個帶參宏均蜜，如下：
#define chartonumber(x) (x-'0')
這樣只需要調(diào)用
c = chartonumber(a);
即可實(shí)現(xiàn)效果。
這樣的答案顯然是沒有錯誤的芒率，但是在這個題目當(dāng)中囤耳，我們使用這個方法不幸就超時(shí)了，因?yàn)槿帕谐时ㄐ栽鲩L，對于我們的回溯法充择，需要的時(shí)間則是其平方次倍的德玫，所以肯定會超時(shí)。
在這里就需要使用一些簡單的數(shù)學(xué)技巧對我們的代碼進(jìn)行改動椎麦。
eg: array = {1,2, 3, 4} target: 尋找第九個排列組合.
觀察我們的代碼的迭代可以發(fā)現(xiàn)宰僧，在迭代過程當(dāng)中，都是固定前n位求解后面(array.length - n)位的排列观挎，然后連接到前面形成答案琴儿。
eg:固定第一位為 1 排列有
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
一共等于 3! = 6 個
固定前兩位為 1 2 排列有
1 2 3 4
1 2 4 3
2！= 2個
于是我們可以反推出來嘁捷，當(dāng)前循環(huán)到的前幾位應(yīng)該是什么造成。
例如讓我們超時(shí)的輸入為
n = 9, k = 331987
8! = 40320 k/8 = 8 k%8 = 9427
因此我們可以知道這個答案是以9開頭的
然后接著計(jì)算下一位
9427 7! = 5040 9427/7! = 1 9427%7! = 4387
所有我們可以知道前兩位是92了
然后以此類推。雄嚣。
a1 = k / (n - 1)!
k1 = k
a2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!
...
an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!
an = kn-1 / 0!
kn = kn-1 % 0!
開始愉快地寫代碼
class Solution {
public:
string getPermutation(int n, int k) {
string res;
string num = "123456789";
vector<int> f(n, 1);
for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i;
--k;
for (int i = n; i >= 1; --i) {
int j = k / f[i - 1];
k %= f[i - 1];
res.push_back(num[j]);
num.erase(j, 1);
}
return res;
}
};
