网站建设的商业计划书,动态和静态网站的区别,个人作品主页wordpress,怎么样的网站合适做城市代理文章目录 1863. 找出所有子集的异或总和再求和解题思路#xff1a;子集问题解法#xff08;回溯 剪枝#xff09;47. 全排列 II解题思路#xff1a;排序 回溯 剪枝 1863. 找出所有子集的异或总和再求和
1863. 找出所有子集的异或总和再求和
一个数组的 异或总和 定义为… 文章目录 1863. 找出所有子集的异或总和再求和解题思路子集问题解法回溯 剪枝47. 全排列 II解题思路排序 回溯 剪枝 1863. 找出所有子集的异或总和再求和
1863. 找出所有子集的异或总和再求和
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果如果数组为 空 则异或总和为 0 。
例如数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 1 。
给你一个数组 nums 请你求出 nums 中每个 子集 的 异或总和 计算并返回这些值相加之 和 。
注意 在本题中元素 相同 的不同子集应 多次 计数。
数组 a 是数组 b 的一个 子集 的前提条件是从 b 删除几个也可能不删除元素能够得到 a 。
示例 1
输入nums [1,3]
输出6
解释[1,3] 共有 4 个子集
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 2 。
0 1 3 2 6示例 2
输入nums [5,1,6]
输出28
解释[5,1,6] 共有 8 个子集
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 4 。
- [5,6] 的异或总和为 5 XOR 6 3 。
- [1,6] 的异或总和为 1 XOR 6 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 2 。
0 5 1 6 4 3 7 2 28示例 3
输入nums [3,4,5,6,7,8]
输出480
解释每个子集的全部异或总和值之和为 480 。提示
1 nums.length 121 nums[i] 20 解题思路子集问题解法回溯 剪枝
这道题其实变相在考察子集问题因为它要求的就是将所有的子集的异或结果累加起来那么我们只需要像求解子集问题时候一样求出每个子集序列然后算出它的异或结果累加到一个全局变量 sum 上去最后返回 sum 即可
只不过我们其实可以不用每次得到一个子集序列后再去遍历子集序列求异或结果这样子时间复杂度是比较高的我们可以用一个变量 path 记录下路径上已经遍历到的元素的异或结果然后让其再异或上当前的元素得到就是当前子集的异或结果最后将其累加到 sum 变量上即可仅仅用一个变量就能得到这个效果只不过我们需要注意的是因为我们要列举出其它的同层路径所以回溯的时候需要将临时变量 path 恢复到原来的样子只需要让其再次异或上当前元素即可做到
剩下的其实细节和子集问题都是一样的具体可以参考子集问题的笔记
class Solution {
private:int path 0; // 存放当前路径的异或结果int sum 0; // 结果集存放所有异或结果的和
public:int subsetXORSum(vectorint nums) {dfs(nums, 0);return sum;}void dfs(vectorint nums, int index){// 递归函数出口其实也可以不写因为下面的循环已经限制了在数组范围内了if(index nums.size())return;for(int i index; i nums.size(); i){// 处理当前结果path ^ nums[i];sum path;// 递归处理其它结果dfs(nums, i 1);// 回溯处理path ^ nums[i];}}
};47. 全排列 II
47. 全排列 II
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。
示例 1
输入nums [1,1,2]
输出
[[1,1,2],[1,2,1],[2,1,1]]示例 2
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示
1 nums.length 8-10 nums[i] 10 解题思路排序 回溯 剪枝
还是一样对于全排列问题我们使用的是回溯也就是深度优先搜索方法遍历整棵决策树最后叶子节点就是我们需要的结果大体的思路是一样的这里就不再细讲具体可以参考 46. 全排列 的解题笔记
但是与 46. 全排列 不同的是这道题给定的数字序列是可包含重复元素的也就是说决策树中可能会出现相同的子树也就是有重复的结果出现如下图所示 所以我们必须做点措施防止重复决策子树出现也可以用哈希表去重但是比较占空间这里不考虑
方法其实很简单我们仔细一想会出现重复的情况其实就是因为有重复的元素那么我们只要让重复的元素只遍历一次决策子树而其它重复的元素不处理即可所以我们考虑 先将原数组进行排序这样子使得重复的元素是相邻的然后我们只需要用已有的 used 数组多加一层判断即可具体判断的细节如下所示
对于 不同层的元素 的剪枝处理 如果上一层走过了该节点那么就不需要再走了也就是如果 used[i] true 则直接跳过即可 对于 同层的元素 的剪枝处理 如果相邻元素重复的话那么当前元素其决策子树是和前面重复的必须得进行剪枝操作也就是此时 i 0 nums[i] nums[i - 1] used[i - 1] false 成立的话则直接跳过即可
上面的判断相比起 46. 全排列 这道题来说只不过多了一个对同层元素的剪枝处理如下图所示 其它细节都是一样的这里不再赘述
class Solution {
private:vectorvectorint ret; // 存放结果集vectorint path; // 存放当前路径中的元素bool used[9]; // 保存元素是否已经走过true表示走过
public:vectorvectorint permuteUnique(vectorint nums) {// 首先对原数组进行排序使得重复的元素是相邻的sort(nums.begin(), nums.end());// 然后交给递归函数去求解结果即可dfs(nums);return ret;}void dfs(vectorint nums){// 递归函数出口if(path.size() nums.size()){ret.push_back(path);return;}for(int i 0; i nums.size(); i){// 如果上一层走过了该节点那么就不需要再走了注意这是对不同层的剪枝处理// 进行剪枝操作如果相邻元素重复的话其排列结果是和前面重复的注意这是对同层的剪枝处理if(used[i] true || (i 0 nums[i] nums[i - 1] used[i - 1] false))continue;// 处理当前元素path.push_back(nums[i]);used[i] true;// 递归处理该节点以下的路径dfs(nums);// 回溯处理used[i] false;path.pop_back();}}
};
