491.递增子序列
将其看作一个二叉树,可以知道,在二叉树每层中,不能取相同的元素。这题最主要要理解这个点。使用unordered_set对其进行降重。
class Solution {
public:
vector<vector<int>> res;
vector<int> cur;
void backtracking(vector<int>& nums,int index){
if(cur.size()>=2){
res.push_back(cur);
}
unordered_set<int> uset; // 使用set对本层元素进行去重
for (int i = index; i < nums.size(); i++) {
if ((!cur.empty() && nums[i] < cur.back())|| uset.find(nums[i]) != uset.end()) {
continue;
}
uset.insert(nums[i]); // 记录这个元素在本层用过了,本层后面不能再用了
cur.push_back(nums[i]);
backtracking(nums,i+1);
cur.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums,0);
return res;
}
};
46.全排列
这题最重要的是考虑一个数在一个排列中只能出现一次。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, vector<bool>& used){
if(path.size()==nums.size()){
res.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(used[i] == true) continue;
used[i]=true;
path.push_back(nums[i]);
backtracking(nums,used);
path.pop_back();
used[i]=false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(),false);
backtracking(nums,used);
return res;
}
};
47.全排列 II
1.如何去重? 同上题一样。但是我们要注意这题数组中可能出现相同的元素。
2.去重一定要对元素进行排序,这样我们才方便通过相邻的节点来判断是否重复使用了。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, vector<bool>& used){
if(path.size()==nums.size()){
res.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(i>0 && nums[i]==nums[i-1] && used[i-1]==false){
continue;
}
if(used[i] == false){
used[i]=true;
path.push_back(nums[i]);
backtracking(nums,used);
path.pop_back();
used[i]=false;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(),false);
sort(nums.begin(),nums.end());
backtracking(nums,used);
return res;
}
};
标签:vector,排列,nums,46,47,back,used,res,backtracking
From: https://blog.csdn.net/m0_69189584/article/details/140109886