Skip to content

Latest commit

 

History

History
118 lines (92 loc) · 4.13 KB

面试题 38：字符串的排列.md

File metadata and controls

118 lines (92 loc) · 4.13 KB
Raw

试题链接：字符串的排列_牛客题霸_牛客网

方法一：回溯

  • 思路：暴力回溯每一种取值，去重可以使用哈希也可以通过排序，然后每次再为当前 idx 选取字符的时候保证重复的只选一次即可，可以只选从左到右第一个未被填过的数字。
  • 时间复杂度：O(n × n!)
  • 空间复杂度：O(n)
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> ans;
        int n = str.size();
        vector<bool> vis(n);
        string path;
        path.reserve(n);

        sort(str.begin(), str.end());

        function<void(int)> backtrack = [&](int idx) {
            if (idx == n) {
                ans.push_back(path);
            }

            for (int i = 0; i < n; i++) {
                if (vis[i] || (i > 0 && str[i - 1] == str[i] && vis[i - 1])) continue;
                vis[i] = true;
                path.push_back(str[i]);
                backtrack(idx + 1);
                path.pop_back();
                vis[i] = false;
            }
        };

        backtrack(0);

        return ans;
    }
};

方法二：下一个排列

  • 思路：next_permutation 算法可以求出一个排列下个字典序更大的排列，因此只要我们对字符串排序后不断求出它的下一个排列，即可得到所有排列。注意到下一个排列总是比当前排列要大，除非该排列已经是最大的排列。我们希望找到一种方法，能够找到一个大于当前序列的新序列，且变大的幅度尽可能小。具体地，该算法主要分为如下几步：
    • 每次从后往前找到第一个满足 str[i] < str[i + 1]的数, 再从 [i + 1, n) 中找到最接近 str[i] 并大于 str[i] 的第一个数 str[j]，要得到下一个排列，我们应该交换 str[i] 和 str[j]，然后让 str[i] 后的数从小到大排列
    • 实际上，我们不必每次都对 [i + 1, n) 的数都进行排序，可以发现，由于 str[j] 是第一个大于 str[i] 的数, 故 str[j + 1] 一定是小于或等于 str[i] 的, 交换 str[i] 和 str[j] 后, [i + 1, n) 一定是从大到小的序列, 我们只需要对其进行翻转即可
  • 时间复杂度：O(n!)
  • 空间复杂度：O(1)
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> ans;
        sort(str.begin(), str.end());
        do {
            ans.push_back(str);
        } while (nextPermutation(str));

        return ans;
    }

    bool nextPermutation(string& str) {
        int n = str.size();

        int i = n - 2;
        while (i >= 0 && str[i] >= str[i + 1]) i--;

        if (i < 0) return false;

        int j = n - 1;
        while (str[i] >= str[j]) j--;
        swap(str[i], str[j]);

        reverse(str.begin() + i + 1, str.end());

        return true;
    }
};

相关题目：N 皇后

试题链接：https://leetcode.cn/problems/n-queens-ii/description/

  • 思路：用一个记录 0 ~ n - 1 元素的数组表示每一行皇后所在的列，这样可以保证行和列都不在同一行列，对这个数组求所有排列情况，然后对每种排列情况进行判断即可，只需要判断对角线是否存在多余数量的皇后。取任意两个皇后，判断它们的行距和列距是否相同。
  • 时间复杂度：O(n!)
  • 空间复杂度：O(n)
class Solution {
public:
    int totalNQueens(int n) {
        int ans = 0;
        vector<int> colIndex(n);
        iota(colIndex.begin(), colIndex.end(), 0);
        
        do {
            bool flag = true;

            for (int i = 0; i < n && flag; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (abs(i - j) == abs(colIndex[i] - colIndex[j]))
                    {
                        flag = false;
                        break;
                    }
                }
            }

            if (flag) ans++;

        } while (next_permutation(colIndex.begin(), colIndex.end()));

        return ans;
    }
};