总览
涉及到的题目有
| 题号 | 名字 | 难度 |
|---|---|---|
| Leetcode 60 | 第k个排列 | 中等 |
| Leetcode 46 | 全排列 | 中等 |
待更新。。。。。。
Leetcode 46 全排列
题目
基础题
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路
很简单就能想到是回溯，这个题也确实是回溯。
但是有两个问题需要注意。
第一，如果要保证数字不重复，那需要一个类似数组的变量去存储这些数字有没有被使用，这是个非常直观的想法。但是这个想法可能会导致严重的错误。因为序列里可能会有负数，而普通的vector<bool>类型是无法索引负数的。所以一旦确定是有负数的，那就要用map<int, bool>来做了。
第二，额外的变量来标记固然简单且直观，但是也会造成额外的开销。所以有一种优化方式，就是把原来的nums分割成两段，比如([0]sim [first-1])和([first] sim [n-1])，左边代表已经固定的，而右边代表待选的元素。这样通过交换来完成选择的过程就可以了。回撤操作只需要再次交换回来即可。
但是第二种做法有一个严重的问题，就是最后的结果不满足字典序，如果想保持字典序，就必须考虑其他的方式。
首先是第一种方法的代码，使用额外的空间去记录元素是否被访问，如下：
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
if(!nums.size()){
return res_;
}
vector<int> temp_res;
// used不能用vector，因为值可能会是负数
map<int, bool> used;
backTrace(nums, temp_res, used);
return res_;
}
private:
vector<vector<int>> res_;
void backTrace(vector<int>& nums, vector<int> temp_res, map<int, bool>& used){
if(temp_res.size() == nums.size()){
res_.push_back(temp_res);
return;
}
for(auto num : nums){
if(!used[num]){
used[num] = true;
temp_res.push_back(num);
backTrace(nums, temp_res, used);
temp_res.pop_back();
used[num] = false;
}
}
}
};
这种方法非常慢，因为反复赋值非常耗费资源。
可以看到上面的方法仅能超过10%，肯定不能作为最终解。
下面给出的代码是利用第二点优化之后的代码，如下：
// 交换法
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
int first=0;
backTrack(nums, first);
return res_;
}
private:
vector<vector<int>> res_;
void backTrack(vector<int>& nums, int first){
int n = nums.size();
if(first == n){
res_.push_back(nums);
return;
}
for(int i = first; i<n; i++){
swap(nums[first], nums[i]);
backTrack(nums, first+1);
swap(nums[first], nums[i]);
}
}
};
结果：
Leetcode 60 第k个排列
题目
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"
思路
这个题如果是按照48题的做法，直接生成所有，然后选出第k个，是会超时的。
正确的做法是利用数学去推，下面结合官方题解和部分博客的思路总结一下。
首先是如何去推算：
上图是官方题解前一部分的解释，下面举一个(n = 4,k = 9)的例子说明一下过程:
n=4时的全排列有：
1234
1243
1324
1342
1423
1432
2134
2143
2314（这里是目标值）
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
为了后面遍历方便，这里首先让k--
第一个数字：
我们要取的是(k/(n-1)! = 8/(4-1)! = 1)（这里的1是下标为1的那个），即{1,2,3,4}中的2（这里下标是从0开始的）。
这时候，问题规模已经缩减了，也就是第一位已经固定，所选择的范围只剩{1,3,4}
2134
2143
2314（这里是目标值）
2341
2413
2431
问题规模缩小了，所以这里k也要变化，方法是(k \% (n-1)! = 8\%(4-1)! = 8\%6 =2)。
第二个数字：
接着利用上面计算第一个的公式继续计算第二个数字，注意这时候n需要减小为3了。
这次我们要取的是(k/(n-1)! = 2/(3-1)! = 1)（这里的1是下标为1的那个）,也就是{1,3,4}中的3了。
这时候范围还剩：
2314（这里是目标值）
2341
k范围缩小，变成(k \% (n-1)! = 2\%(3-1)! = 2\%2 =0)。
n再次减小，变成了2。
第三个数字：
我们要取的是(k/(n-1)! = 0/(2-1)! = 0)（这里的0是下标为0的那个）,也就是{1,4}中的1了。
第四个数字也就只剩下了4
这个过程想明白后，代码也就简单了：
这里参考了HuaHua酱的代码
// Author: Huahua
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> num;
vector<int> fact(10, 1);
for (int i = 1; i <= 9; i++) {
num.push_back(i);
fact[i] = fact[i - 1] * i;
}
string s;
k--;
while (n--) {
int d = k / fact[n];
k %= fact[n];
s += ('0' + num[d]);
for (int i = d + 1; i <= 9; i++)
num[i - 1] = num[i];
}
return s;
}
};