力扣算法题—047全排列2

不念不忘少年蓝@ 2022-01-05 23:59 188阅读 0赞

1 #include "000库函数.h"
      2 
      3 
      4 //使用排序，感觉在作弊，但是题目没说不可以
      5 //36ms
      6 class Solution {
      7 public:
      8     vector<vector<int>> permuteUnique(vector<int>& nums) {
      9         vector<vector<int>>res;
     10         if (nums.empty())return res;
     11         sort(nums.begin(), nums.end());//排序
     12         do {
     13             res.push_back(nums);
     14         } while (next_permutation(nums.begin(), nums.end()));
     15         return res;
     16     }
     17 };
     18 
     19 ////使用递归
     20 class Solution {
     21 public:
     22     vector<vector<int>> permuteUnique(vector<int>& nums) {
     23         vector<vector<int>>Res;
     24         if (nums.empty())return Res;
     25         Combin(Res, nums, 0);//回溯
     26         //set<vector<int>>s;
     27         //s.insert(Res.begin(), Res.end());//去重
     28         //Res.assign(s.cbegin(), s.cend());
     29         return Res;
     30     }
     31     void Combin(vector<vector<int>>&Res, vector<int>v, int s) {
     32         if (s >= v.size()) //此处不return，在for中结束后自动结束
     33             Res.push_back(v);
     34 
     35         for (int i = s; i < v.size(); ++i) {
     36             if (s != i && v[i] == v[s])//去重
     37                 continue;            
     38             swap(v[s], v[i]);//交换
     39             Combin(Res, v, s + 1);//回溯
     40             swap(v[s], v[i]);//换回来
     41         
     42         }
     43     }
     44 
     45 };
     46 //
     47 //使用DFS递归
     48 class Solution {
     49 public:
     50     vector<vector<int>> permuteUnique(vector<int>& num) {
     51         vector<vector<int>> res;
     52         vector<int> out, visited(num.size(), 0);
     53         permuteDFS(num, 0, visited, out, res);
     54         //set<vector<int>>s;
     55         //s.insert(res.begin(), res.end());//去重
     56         //res.assign(s.cbegin(), s.cend());
     57         return res;
     58     }
     59     void permuteDFS(vector<int>& num, int level, vector<int>& visited, vector<int>& out, vector<vector<int>>& res) {
     60         if (level == num.size()) { res.push_back(out); return; }//数字大小达到要求
     61         for (int i = 0; i < num.size(); ++i) {
     62             if (visited[i] == 1) continue;
     63             visited[i] = 1;//该数据已经选用
     64             out.push_back(num[i]);
     65             permuteDFS(num, level + 1, visited, out, res);
     66             out.pop_back();//回溯
     67             visited[i] = 0;
     68         }
     69     }
     70 };
     71 
     72 //当n = 1时，数组中只有一个数a1，其全排列只有一种，即为a1
     73 //
     74 //当n = 2时，数组中此时有a1a2，其全排列有两种，a1a2和a2a1，那么此时我们考虑和上面那种情况的关系，我们发现，其实就是在a1的前后两个位置分别加入了a2
     75 //
     76 //当n = 3时，数组中有a1a2a3，此时全排列有六种，分别为a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那么根据上面的结论，实际上是在a1a2和a2a1的基础上在不同的位置上加入a3而得到的。
     77 //
     78 //_ a1 _ a2 _ : a3a1a2, a1a3a2, a1a2a3
     79 //
     80 //_ a2 _ a1 _ : a3a2a1, a2a3a1, a2a1a3
     81 class Solution {
     82 public:
     83     vector<vector<int>> permute(vector<int>& num) {
     84         vector<vector<int>> res;
     85         if (num.empty()) return res;
     86         int first = num[0];
     87         num.erase(num.begin());//删除此数字
     88         vector<vector<int>> words = permute(num);
     89         for (auto &a : words) {
     90             for (int i = 0; i <= a.size(); ++i) {
     91                 a.insert(a.begin() + i, first);
     92                 res.push_back(a);
     93                 a.erase(a.begin() + i);
     94             }
     95         }
     96         return res;
     97     }
     98 };
     99 
    100 void T047() {
    101     vector<int>n;
    102     Solution s;
    103     n = { 1,1,2 };
    104     for (auto &a : s.permuteUnique(n)) {
    105         for (auto b : a)
    106             cout << b << "  ";
    107         cout << endl;
    108     }
    109 
    110 }

转载于:https://www.cnblogs.com/zzw1024/p/10610201.html