前言
- 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伸出双手回溯时间)!