【每日刷题】Day124
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. LCR 079. 子集 - 力扣（LeetCode）
2. 1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）
3. LCR 084. 全排列 II - 力扣（LeetCode）
1. LCR 079. 子集 - 力扣（LeetCode）
//思路：深搜+回溯。
//解决这类问题我们首先要画出决策树
//这里代码供参考，最好还是自己思考如何将决策树转换为代码。
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
bool hash[11];
void _subsets(vector<int>& nums,int i)
{
if(i==nums.size())
{
ans.push_back(tmp);
return;
}
_subsets(nums,i+1);
tmp.push_back(nums[i]);
_subsets(nums,i+1);
tmp.pop_back();;
}
vector<vector<int>> subsets(vector<int>& nums)
{
_subsets(nums,0);
return ans;
}
};
2. 1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）
//思路：深搜+回溯。
//本题思路与上题 "子集" 完全一样。找完所有子集后我们对这些子集进行遍历，算出所有子集的异或和再求和。
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
void _subsetXORSum(vector<int> nums,int i)
{
if(i==nums.size())
{
ans.push_back(tmp);
return;
}
_subsetXORSum(nums,i+1);
tmp.push_back(nums[i]);
_subsetXORSum(nums,i+1);
tmp.pop_back();
}
int subsetXORSum(vector<int>& nums)
{
int ret = 0;
_subsetXORSum(nums,0);
for(int i = 0;i<ans.size();i++)
{
int tmp = 0;
for(int j = 0;j<ans[i].size();j++) tmp^=ans[i][j];
ret+=tmp;
}
return ret;
}
};
3. LCR 084. 全排列 II - 力扣（LeetCode）
//思路：深搜+回溯。
//本题大体思路与 Day123 中的 "全排列" 完全相同，区别在于需要额外处理特殊的剪枝操作
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
bool hash[9];
void _permuteUnique(vector<int>& nums)
{
if(tmp.size()==nums.size())
{
ans.push_back(tmp);
return;
}
for(int i = 0;i<nums.size();i++)
{
if(hash[i]||(i>0&&hash[i-1]&&nums[i]==nums[i-1])) continue;//跳过重复数字
tmp.push_back(nums[i]);//后续与 "全排列" 完全一样
hash[i] = true;
_permuteUnique(nums);
tmp.pop_back();
hash[i] = false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums)
{
sort(nums.begin(),nums.end());//这里需要对数组排序一下，这样重复的数字就一定是挨在一起的
_permuteUnique(nums);
return ans;
}
};
