[LeetCode] 46. Permutations 全排列

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

這道題是求全排列問題，給的輸入數(shù)組沒有重復(fù)項(xiàng)，這跟之前的那道 Combinations 和類似，解法基本相同，但是不同點(diǎn)在于那道不同的數(shù)字順序只算一種，是一道典型的組合題，而此題是求全排列問題，還是用遞歸 DFS 來求解。這里需要用到一個(gè) visited 數(shù)組來標(biāo)記某個(gè)數(shù)字是否訪問過，然后在 DFS 遞歸函數(shù)從的循環(huán)應(yīng)從頭開始，而不是從 level 開始，這是和 Combinations 不同的地方，其余思路大體相同。這里再說下 level 吧，其本質(zhì)是記錄當(dāng)前已經(jīng)拼出的個(gè)數(shù)，一旦其達(dá)到了 nums 數(shù)組的長(zhǎng)度，說明此時(shí)已經(jīng)是一個(gè)全排列了，因?yàn)樵偌訑?shù)字的話，就會(huì)超出。還有就是，為啥這里的 level 要從0開始遍歷，因?yàn)檫@是求全排列，每個(gè)位置都可能放任意一個(gè)數(shù)字，這樣會(huì)有個(gè)問題，數(shù)字有可能被重復(fù)使用，由于全排列是不能重復(fù)使用數(shù)字的，所以需要用一個(gè) visited 數(shù)組來標(biāo)記某個(gè)數(shù)字是否使用過，代碼如下：

解法一：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& num) {
        vector<vector<int>> res;
        vector<int> out, visited(num.size(), 0);
        permuteDFS(num, 0, visited, out, res);
        return res;
    }
    void permuteDFS(vector<int>& num, int level, vector<int>& visited, vector<int>& out, vector<vector<int>>& res) {
        if (level == num.size()) {res.push_back(out); return;}
        for (int i = 0; i < num.size(); ++i) {
            if (visited[i] == 1) continue;
            visited[i] = 1;
            out.push_back(num[i]);
            permuteDFS(num, level + 1, visited, out, res);
            out.pop_back();
            visited[i] = 0;
        }
    }
};

上述解法的最終生成順序?yàn)椋篬[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] 。

還有一種遞歸的寫法，更簡(jiǎn)單一些，這里是每次交換 num 里面的兩個(gè)數(shù)字，經(jīng)過遞歸可以生成所有的排列情況。這里你可能注意到，為啥在遞歸函數(shù)中， push_back() 了之后沒有返回呢，而解法一或者是 Combinations 的遞歸解法在更新結(jié)果 res 后都 return 了呢？其實(shí)如果你仔細(xì)看代碼的話，此時(shí) start 已經(jīng)大于等于 num.size() 了，而下面的 for 循環(huán)的i是從 start 開始的，根本就不會(huì)執(zhí)行 for 循環(huán)里的內(nèi)容，就相當(dāng)于 return 了，博主偷懶就沒寫了。但其實(shí)為了避免混淆，最好還是加上，免得和前面的搞混了，代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& num) {
        vector<vector<int>> res;
        permuteDFS(num, 0, res);
        return res;
    }
    void permuteDFS(vector<int>& num, int start, vector<vector<int>>& res) {
        if (start >= num.size()) res.push_back(num);
        for (int i = start; i < num.size(); ++i) {
            swap(num[start], num[i]);
            permuteDFS(num, start + 1, res);
            swap(num[start], num[i]);
        }
    }
};

上述解法的最終生成順序?yàn)椋篬[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2]] 

最后再來看一種方法，這種方法是 CareerCup 書上的方法，也挺不錯(cuò)的，這道題是思想是這樣的：

當(dāng) n=1 時(shí)，數(shù)組中只有一個(gè)數(shù) a₁，其全排列只有一種，即為 a₁

當(dāng) n=2 時(shí)，數(shù)組中此時(shí)有 a₁a₂，其全排列有兩種，a₁a₂ 和 a₂a₁，那么此時(shí)考慮和上面那種情況的關(guān)系，可以發(fā)現(xiàn)，其實(shí)就是在 a₁ 的前后兩個(gè)位置分別加入了 a₂ 

當(dāng) n=3 時(shí)，數(shù)組中有 a₁a₂a₃，此時(shí)全排列有六種，分別為 a₁a₂a₃, a₁a₃a₂, a₂a₁a₃, a₂a₃a₁, a₃a₁a₂, 和 a₃a₂a₁。那么根據(jù)上面的結(jié)論，實(shí)際上是在 a₁a₂ 和 a₂a₁ 的基礎(chǔ)上在不同的位置上加入 a₃ 而得到的。

_ a₁ _ a₂ _ : a₃a₁a₂, a₁a₃a₂, a₁a₂a₃

_ a₂ _ a₁ _ : a₃a₂a₁, a₂a₃a₁, a₂a₁a₃

解法三：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& num) {
        if (num.empty()) return vector<vector<int>>(1, vector<int>());
        vector<vector<int>> res;
        int first = num[0];
        num.erase(num.begin());
        vector<vector<int>> words = permute(num);
        for (auto &a : words) {
            for (int i = 0; i <= a.size(); ++i) {
                a.insert(a.begin() + i, first);
                res.push_back(a);
                a.erase(a.begin() + i);
            }
        }   
        return res;
    }
};

上述解法的最終生成順序?yàn)椋篬[1,2,3], [2,1,3], [2,3,1], [1,3,2], [3,1,2], [3,2,1]]

上面的三種解法都是遞歸的，我們也可以使用迭代的方法來做。其實(shí)下面這個(gè)解法就上面解法的迭代寫法，核心思路都是一樣的，都是在現(xiàn)有的排列的基礎(chǔ)上，每個(gè)空位插入一個(gè)數(shù)字，從而生成各種的全排列的情況，參見代碼如下：

解法四：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& num) {
        vector<vector<int>> res{{}};
        for (int a : num) {
            for (int k = res.size(); k > 0; --k) {
                vector<int> t = res.front();
                res.erase(res.begin());
                for (int i = 0; i <= t.size(); ++i) {
                    vector<int> one = t;
                    one.insert(one.begin() + i, a);
                    res.push_back(one);
                }
            }
        }
        return res;
    }
};

上述解法的最終生成順序?yàn)椋篬[3,2,1], [2,3,1], [2,1,3], [3,1,2], [1,3,2], [1,2,3]]

下面這種解法就有些耍賴了，用了 STL 的內(nèi)置函數(shù) next_permutation()，專門就是用來返回下一個(gè)全排列，耳邊又回響起了諸葛孔明的名言，我從未見過如此...投機(jī)取巧...的解法！

解法五：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& num) {
        vector<vector<int>> res;
        sort(num.begin(), num.end());
        res.push_back(num);
        while (next_permutation(num.begin(), num.end())) {
            res.push_back(num);
        }
        return res;
    }
};

上述解法的最終生成順序?yàn)椋篬[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(46.全排列)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)全排列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論