【代码随想录】刷题笔记Day33

前言

• Day33虽说是一个月，但是从第一篇开始实际上已经过了8个月了，得抓紧啊

46. 全排列 - 力扣（LeetCode）

• 前面组合就强调过差别了，这道题是排序，因此每次要从头到尾扫，结合used数组
• 

• class Solution {
  private:vector<vector<int>> res;vector<int> path;// vector<int> used(10);  // 私有中vector不支持初始化int used[7] = {};         // 私有中静态数组支持初始化void backtracking(vector<int>& nums){if(path.size() == nums.size()){res.push_back(path);return;}for(int i = 0; i < nums.size(); i++){  // 从头开始遍历if(used[i] == 1) continue;  // 数枝上跳过取过的元素 used[i] = 1;path.push_back(nums[i]);backtracking(nums);used[i] = 0;path.pop_back();}}
  public:vector<vector<int>> permute(vector<int>& nums) {backtracking(nums);return res;}
  };

 47. 全排列 II - 力扣（LeetCode）

• 有重复元素，比前一题多两个步骤：排序 + 去重
• 
• 

• class Solution {
  private:vector<vector<int>> res;vector<int> path;int used[9] = {};         // 私有中静态数组支持初始化void backtracking(vector<int>& nums){if(path.size() == nums.size()){res.push_back(path);return;}for(int i = 0; i < nums.size(); i++){  // 从头开始遍历if(used[i] == 1 || i > 0 && used[i - 1] == 0 && nums[i] == nums[i - 1]) continue;  // 去重，used[i - 1] == 0/1都可以通过，0更好（树层上去重）used[i] = 1;path.push_back(nums[i]);backtracking(nums);used[i] = 0;path.pop_back();}}
  public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());  // 先排序backtracking(nums);return res;}
  };

后言

• 搞定咯，前面有组合的铺垫之后这两道都好做很多hhh，明天结束回溯（假装是Life is strange里的MAX伸出双手回溯时间）！