面试题 08.07. 无重复字符串的排列组合

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例:

输入：S = “qwe”

输出：[“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]

提示:

1. 字符都是英文字母。
2. 字符串长度在[1, 9]之间。

解法：

这题比较特殊，是字符串，而且没有重复，可以不用回溯，直接插入字母实现全排列，经过观察我们可以发现以下规律。

将每个字母插入到前面字符串所有可能的情况：
例如：“qwe”
第一轮：q
第二轮：将w插入q,有两种情况：wq, qw
第三轮：将e插入wq, qw中去 即：ewq,weq,wqe;eqw,qew,qwe六种情况

代码：

class Solution {
private:
    vector res;
public:
    void dfs(string& t, string& s, int k){
        if(t.length()==s.length()){
            res.push_back(t);
            return;
        }
        for(int i=0; i<=t.size(); i++){
            string tmp = t.substr(0,i) + s[k] + t.substr(i);
            dfs(tmp,s,k+1);
        }
    }
    vector permutation(string s) {
        if(s.empty()) return {};
        string t = "";
        t += s[0];
        dfs(t, s, 1);
        return res;
    }
};

46. 全排列

上一题比较tricky，没有用到真正的排列组合算法，由于情况太特殊了，如果换成数字就没法实现了，所以我们还是看一下正常的题目和解法。

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:

[

 [1,2,3],

 [1,3,2],

 [2,1,3],

 [2,3,1],

 [3,1,2],

 [3,2,1]

]

解法：

和上题一样都是全排列，但是变成了一串数字。处理方法和上一题就不一样了，因为字符串插入很简单，但是数组插入的话就会很费时间，所以就不能投机了，这里用最经典的回溯思路来进行数字的全排列。

算法用dfs，用used数组记录当前数字是否选过，然后一直选到不能选为止，记得要恢复状态。（附件有详细图解）

代码：

class Solution {
private:
    vector<vector> res;
public:
    void dfs(vector& tmp, vector& used, vector& nums){
        if(tmp.size()==used.size()){
            res.push_back(tmp);
            return;
        }
        for(int i=0; i<used.size(); i++){="" if(used[i]="=false){" used[i]="true;" tmp.push_back(nums[i]);="" dfs(tmp,used,nums);="" tmp.pop_back();="" }="" vector<vector<int="">> permute(vector& nums) {
        res.clear();
        if(nums.empty()) return res;
        vector tmp;
        vector used(nums.size(),false);
        dfs(tmp,used,nums);
        return res;
    }
};
</used.size();></vector

77. 组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2

输出:

[

 [2,4],

 [3,4],

 [2,3],

 [1,2],

 [1,3],

 [1,4],

]

解法：

组合和排列本来就是分不开的，所以思路和代码和上一题差别不大，判断条件上面有些改变，个数到k就可以插入，然后因为是组合不是排列，所以要判重，这里因为是1~n，所以只要一直递增就行了。（附件有详细图解）

代码：

class Solution {
private:
    vector<vector<int>> res;
public:
    void dfs(vector<int>& tmp, vector<bool>& used, int k){
        if(tmp.size()==k){
            res.push_back(tmp);
            return;
        }
        int p = (tmp.empty())?1:tmp.back()+1;
        for(int i=p; i<used.size(); i++){
            if(used[i]==false){
                tmp.push_back(i);
                used[i] = true;
                dfs(tmp,used,k);
                tmp.pop_back();
                used[i] = false;
            }
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<bool> used(n+1,false);
        vector<int> tmp;
        dfs(tmp,used,k);
        return res;
    }
};

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]

输出:

[

 [1,1,2],

 [1,2,1],

 [2,1,1]

]

解法：

和全排列代码类似，但是要考虑重复的情况，每一层dfs的时候，剪掉重复的元素就行了，不重复搜。（附件有详细图解）

代码：

class Solution {
private:
    vector<vector<int>> res;
public:
    void dfs(vector<int>& tmp, vector<bool>& used, vector<int>& nums){
        if(tmp.size()==used.size()){
            res.push_back(tmp);
            return;
        }
        for(int i=0; i<used.size(); i++){
            if(i>0 && nums[i]==nums[i-1] && !used[i-1])
                continue;
            if(!used[i]){
                used[i] = true;
                tmp.push_back(nums[i]);
                dfs(tmp,used,nums);
                used[i] = false;
                tmp.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        res.clear();
        if(nums.empty()) return res;
        sort(nums.begin(),nums.end());
        vector<int> tmp;
        vector<bool> used(nums.size(),false);
        dfs(tmp,used,nums);
        return res;
    }
};

31. 下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

解法：

求字典序选排列的下一个，这里先找数学规律。

首先可以观察到，如果序列是降序的，说明已经是最后一个的排列了，这时候下一个就是第一个有序的数列。

然后如果不是降序的，这时候从后往前找第一个上升的位置，a[i-1]<a[i]的位置，然后再寻找i-1后面比a[i-1]大的最小的那个数的位置j（有点拗口，细品一下不难理解）,交换a[i-1],a[j]，然后把a[i-1]后面的数从小到大排序。

代码：

class Solution {
public:
    void nextPermutation(vector<int>& a) {
        if(a.empty() || a.size()<=1) return;
        int p = a.size()-1;
        while(p-1>=0 && a[p]<=a[p-1])//寻找升序位置
            p--;
        if(p>0){//判断是不是降序
            int q = p;
            for(int j = p+1; j<a.size(); j++)
                if(a[j]>a[p-1] && a[j]<a[q]){//寻找第二个位置
                    q = j;
                }
            int t = a[q];
            a[q] = a[p-1];
            a[p-1] = t;
        }
        sort(a.begin()+p,a.end());//排序
    }
};

60. 第k个排列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”

“132”

“213”

“231”

“312”

“321”

给定 n 和 k，返回第 k 个排列。

说明：

1. 给定 n 的范围是 [1, 9]。
2. 给定 k 的范围是[1, n!]。

示例 :

输入: n = 3, k = 3

输出: “213”

解法：

康拓编码是本题的标准解法，这里不多赘述了，因为一下子讲不清，这里po一个很详细的题解。

https://leetcode-cn.com/problems/permutation-sequence/solution/di-k-ge-pai-lie-by-leetcode/

代码：

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> fac = {0,1,2,6,24,120,720,5040,40320,362880,3628800};
        string res;
        res.clear();
        string s = string("123456789").substr(0,n);
        --k;
        while(k>0){
            int i = k/fac[n-1];
            res += s[i];
            s.erase(s.begin()+i);
            k %= fac[n-1];
            --n;
        }
        return res+s;
    }
};