【递归综合 3】找出所有⼦集的异或总和再求和(easy)(每日一题)
🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
⭐递归杂集⭐
🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
1. 找出所有⼦集的异或总和再求和(easy)
题目链接:1863. 找出所有子集的异或总和再求和 - 力扣(LeetCode)
算法思路:
算法思路:
算法思路:这一题可以用到我文章里边回溯算法里的子集的例题,思路一样.
参考下边
【回溯算法 2】子集(medium)(每日一题)-CSDN博客
这题我们需要求 出所有⼦集,将它们的异或和相加。
所以我们可以定义⼀个变量,直接记 录当前状态的异或和。使⽤递归保存当前集合的状态(异或和),选择将当前元素添加⾄当前状态与 否,并依次递归数组中下⼀个元素。当递归到空元素时,表⽰所有元素都被考虑到,记录当前状态 (将当前状态的异或和添加⾄答案中)。
代码实现:
class Solution {
private int ret =0;
private int sum=0; //记录当前状态的异或和
public int subsetXORSum(int[] nums) {
dfs(nums,0);
return ret;
}
public void dfs(int[] nums,int pos){
//对每个节点加到结果中
ret+=sum;
for(int i = pos;i<nums.length;i++){
//对当前位置的元素加进sum里异或
if(pos==0){
sum = nums[i];
}else{
sum^=nums[i];
}
dfs(nums,i+1);
//回溯
sum^=nums[i];
}
}
}
总结
挺久没更新了,最近被期末忙了好久,每日一题断了,实在不好意思,必须坚持回来!感谢阅览 !
原文地址:https://blog.csdn.net/Y_1215/article/details/140256519
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!