C++實現LeetCode(46.全排列)

[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]
]

這道題是求全排列問題,給的輸入數組沒有重復項,這跟之前的那道 Combinations 和類似,解法基本相同,但是不同點在於那道不同的數字順序隻算一種,是一道典型的組合題,而此題是求全排列問題,還是用遞歸 DFS 來求解。這裡需要用到一個 visited 數組來標記某個數字是否訪問過,然後在 DFS 遞歸函數從的循環應從頭開始,而不是從 level 開始,這是和 Combinations 不同的地方,其餘思路大體相同。這裡再說下 level 吧,其本質是記錄當前已經拼出的個數,一旦其達到瞭 nums 數組的長度,說明此時已經是一個全排列瞭,因為再加數字的話,就會超出。還有就是,為啥這裡的 level 要從0開始遍歷,因為這是求全排列,每個位置都可能放任意一個數字,這樣會有個問題,數字有可能被重復使用,由於全排列是不能重復使用數字的,所以需要用一個 visited 數組來標記某個數字是否使用過,代碼如下:

解法一:

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;
        }
    }
};

上述解法的最終生成順序為:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] 。

還有一種遞歸的寫法,更簡單一些,這裡是每次交換 num 裡面的兩個數字,經過遞歸可以生成所有的排列情況。這裡你可能註意到,為啥在遞歸函數中, push_back() 瞭之後沒有返回呢,而解法一或者是 Combinations 的遞歸解法在更新結果 res 後都 return 瞭呢?其實如果你仔細看代碼的話,此時 start 已經大於等於 num.size() 瞭,而下面的 for 循環的i是從 start 開始的,根本就不會執行 for 循環裡的內容,就相當於 return 瞭,博主偷懶就沒寫瞭。但其實為瞭避免混淆,最好還是加上,免得和前面的搞混瞭,代碼如下:

解法二:

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]);
        }
    }
};

上述解法的最終生成順序為:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2]] 

最後再來看一種方法,這種方法是 CareerCup 書上的方法,也挺不錯的,這道題是思想是這樣的:

當 n=1 時,數組中隻有一個數 a1,其全排列隻有一種,即為 a1

當 n=2 時,數組中此時有 a1a2,其全排列有兩種,a1a和 a2a1,那麼此時考慮和上面那種情況的關系,可以發現,其實就是在 a的前後兩個位置分別加入瞭 a

當 n=3 時,數組中有 a1a2a3,此時全排列有六種,分別為 a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那麼根據上面的結論,實際上是在 a1a和 a2a的基礎上在不同的位置上加入 a而得到的。

_ a_ a_ : a3a1a2, a1a3a2, a1a2a3

_ a_ a_ : a3a2a1, a2a3a1, a2a1a3

解法三:

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;
    }
};

上述解法的最終生成順序為:[[1,2,3], [2,1,3], [2,3,1], [1,3,2], [3,1,2], [3,2,1]]

上面的三種解法都是遞歸的,我們也可以使用迭代的方法來做。其實下面這個解法就上面解法的迭代寫法,核心思路都是一樣的,都是在現有的排列的基礎上,每個空位插入一個數字,從而生成各種的全排列的情況,參見代碼如下:

解法四:

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;
    }
};

上述解法的最終生成順序為:[[3,2,1], [2,3,1], [2,1,3], [3,1,2], [1,3,2], [1,2,3]]

下面這種解法就有些耍賴瞭,用瞭 STL 的內置函數 next_permutation(),專門就是用來返回下一個全排列,耳邊又回響起瞭諸葛孔明的名言,我從未見過如此…投機取巧…的解法!

解法五:

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;
    }
};

上述解法的最終生成順序為:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

到此這篇關於C++實現LeetCode(46.全排列)的文章就介紹到這瞭,更多相關C++實現全排列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: