C++實現(xiàn)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]
]
這道題是求全排列問題，給的輸入數(shù)組沒有重復項，這跟之前的那道 Combinations 和類似，解法基本相同，但是不同點在于那道不同的數(shù)字順序只算一種，是一道典型的組合題，而此題是求全排列問題，還是用遞歸 DFS 來求解。這里需要用到一個 visited 數(shù)組來標記某個數(shù)字是否訪問過，然后在 DFS 遞歸函數(shù)從的循環(huán)應(yīng)從頭開始，而不是從 level 開始，這是和 Combinations 不同的地方，其余思路大體相同。這里再說下 level 吧，其本質(zhì)是記錄當前已經(jīng)拼出的個數(shù)，一旦其達到了 nums 數(shù)組的長度，說明此時已經(jīng)是一個全排列了，因為再加數(shù)字的話，就會超出。還有就是，為啥這里的 level 要從0開始遍歷，因為這是求全排列，每個位置都可能放任意一個數(shù)字，這樣會有個問題，數(shù)字有可能被重復使用，由于全排列是不能重復使用數(shù)字的，所以需要用一個 visited 數(shù)組來標記某個數(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;
}
}
};
上述解法的最終生成順序為：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] 。
還有一種遞歸的寫法，更簡單一些，這里是每次交換 num 里面的兩個數(shù)字，經(jīng)過遞歸可以生成所有的排列情況。這里你可能注意到，為啥在遞歸函數(shù)中， push_back() 了之后沒有返回呢，而解法一或者是 Combinations 的遞歸解法在更新結(jié)果 res 后都 return 了呢？其實如果你仔細看代碼的話，此時 start 已經(jīng)大于等于 num.size() 了，而下面的 for 循環(huán)的i是從 start 開始的，根本就不會執(zhí)行 for 循環(huán)里的內(nèi)容，就相當于 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 時，數(shù)組中只有一個數(shù) a1，其全排列只有一種，即為 a1
當 n=2 時，數(shù)組中此時有 a1a2，其全排列有兩種，a1a2 和 a2a1，那么此時考慮和上面那種情況的關(guān)系，可以發(fā)現(xiàn)，其實就是在 a1 的前后兩個位置分別加入了 a2
當 n=3 時，數(shù)組中有 a1a2a3，此時全排列有六種，分別為 a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那么根據(jù)上面的結(jié)論，實際上是在 a1a2 和 a2a1 的基礎(chǔ)上在不同的位置上加入 a3 而得到的。
_ a1 _ a2 _ : a3a1a2, a1a3a2, a1a2a3
_ a2 _ a1 _ : 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]]
上面的三種解法都是遞歸的，我們也可以使用迭代的方法來做。其實下面這個解法就上面解法的迭代寫法，核心思路都是一樣的，都是在現(xiàn)有的排列的基礎(chǔ)上，每個空位插入一個數(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;
}
};
上述解法的最終生成順序為：[[3,2,1], [2,3,1], [2,1,3], [3,1,2], [1,3,2], [1,2,3]]
下面這種解法就有些耍賴了，用了 STL 的內(nèi)置函數(shù) 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]]
到此這篇關(guān)于C++實現(xiàn)LeetCode(46.全排列)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)全排列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++類結(jié)構(gòu)體與json相互轉(zhuǎn)換
這篇文章主要介紹的是C++類結(jié)構(gòu)體與json相互轉(zhuǎn)換，json字符串一般使用的是開源的類庫Newtonsoft.Json，方法十分簡潔，下面就隨小編一起看下面文章內(nèi)容吧2021-09-09
這篇文章主要介紹了C++基于控制臺實現(xiàn)的貪吃蛇小游戲,實例分析了貪吃蛇游戲的原理與C++實現(xiàn)技巧,是非常經(jīng)典的游戲算法,需要的朋友可以參考下2015-04-04
Qt圖片繪圖類之QPixmap/QImage/QPicture詳解
這篇文章主要為大家詳細介紹了Qt圖片繪圖類中QPixmap、QImage和QPicture的使用方法，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學習一下2023-03-03
這篇文章主要介紹了c語言生成隨機uuid編碼示例,需要的朋友可以參考下2014-05-05
本文主要介紹了操作系統(tǒng)中的虛擬地址與物理地址。在早期的計算機中，要運行一個程序，會把這些程序全都裝入內(nèi)存，程序都是直接運行在內(nèi)存上的，也就是說程序中訪問的內(nèi)存地址都是實際的物理內(nèi)存地址。那當程序同時運行多個程序時，操作系統(tǒng)是如何為這些程序分配內(nèi)存的呢2021-06-06
這篇文章主要為大家詳細介紹了OpenCV鼠標繪制矩形和截取矩形區(qū)域圖像，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要介紹了C語言變長數(shù)組使用詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
這篇文章主要為大家詳細介紹了Qt實現(xiàn)柵格布局效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
本文主要介紹了QT多線程編程的深入理解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-06-06
C++中String類的常用接口函數(shù)總結(jié)
這篇文章主要介紹了C++中Stirng類的常用接口函數(shù)，文中有詳細的代碼示例供大家參考，對我們學習C++有一定的幫助，感興趣的同學可以跟著小編一起來學習2023-06-06