丹阳建设工程管理处网站,铜陵高端网站建设,安装失败未能找到wordpress目录,设计公司起名网欢迎来到Cefler的博客#x1f601; #x1f54c;博客主页#xff1a;那个传说中的man的主页 #x1f3e0;个人专栏#xff1a;题目解析 #x1f30e;推荐文章#xff1a;题目大解析#xff08;3#xff09; 目录 #x1f449;#x1f3fb;找出所有子集的异或总和再求… 欢迎来到Cefler的博客 博客主页那个传说中的man的主页 个人专栏题目解析 推荐文章题目大解析3 目录 找出所有子集的异或总和再求和全排列 II电话号码的字母组合括号生成组合 找出所有子集的异或总和再求和
原题链接找出所有子集的异或总和再求和
mycode:
class Solution {
public:vectorvectorint res;vectorint path;void dfs(vectorint nums,int n){for(int i n ;inums.size();i){path.push_back(nums[i]);dfs(nums,i1);path.pop_back();}res.push_back(path);}int subsetXORSum(vectorint nums) {dfs(nums,0);int Sum 0;for(int i 0;ires.size();i){int sum 0;for(auto e:res[i]){sum^e;}Sumsum;}return Sum;}
};优化代码纯递归
class Solution {
public:int Sum 0,sum 0;void dfs(vectorint nums,int n){for(int i n ;inums.size();i){sum^nums[i];dfs(nums,i1);sum^nums[i];//再异或一遍可以消掉}Sumsum;}int subsetXORSum(vectorint nums) {dfs(nums,0);return Sum;}
};全排列 II
原题链接全排列 II
mycode:
class Solution {
public:vectorvectorint ret;vectorint path;bool check[8];//检查该位置是否被用过了true说明被用过了 void dfs(vectorint nums){if(nums.size()path.size())//说明此时已经组成一个序列了{ret.push_back(path);return;}for(int i 0;inums.size();i){if(check[i]false (i0||nums[i]!nums[i-1]||check[i-1]true))//此时还没被用过第一层||前后值不重复相等||不在同一层{path.push_back(nums[i]);check[i] true;dfs(nums);//回溯清空现场将dfs下层插入的元素pop掉path.pop_back();check[i] false;}}}vectorvectorint permuteUnique(vectorint nums) {//前提先排序sort(nums.begin(),nums.end());dfs(nums);return ret;}
};电话号码的字母组合
原题链接电话号码的字母组合
mycode:
class Solution {
public:const char* numsArr[10] {,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};void Combine(const string digits,string combinestr,int i ,vectorstring ret){if(i digits.size())//当数字中的字母全部都进行完组合后{ret.push_back(combinestr);return;}int num digits[i] - 0;string str numsArr[num];for(auto ch:str){Combine(digits,combinestrch,i1,ret);}}vectorstring letterCombinations(const string digits) {vectorstring v;//存储全部组合的字符串if(digits)return v;string str;//这个是专门用来组合的字符串int i 0;Combine(digits,str,i,v);return v;}
};加入恢复现场代码优化
class Solution {
public:const char* numsArr[10] {,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstring ret;string combinestr;void Combine(const string digits,int i ){if(i digits.size())//当数字中的字母全部都进行完组合后{ret.push_back(combinestr);return;}int num digits[i] - 0;string str numsArr[num];for(auto ch:str){combinestrch;Combine(digits,i1);//恢复现场combinestr.pop_back();}}vectorstring letterCombinations(const string digits) {if(digits)return ret;Combine(digits,0);return ret;}
};括号生成
原题链接括号生成
mycode:
class Solution {
public:vectorstring ret;string path;int left 0,right 0;void dfs(int n){if(leftright2*n) {ret.push_back(path);return;}if(leftn){path.push_back(();left;dfs(n);path.pop_back();left--;}if(rightleft){path.push_back());right;dfs(n);path.pop_back();right--;} }vectorstring generateParenthesis(int n) {dfs(n);return ret;}
};组合
原题链接组合
mycode:
class Solution {
public:vectorvectorint ret;vectorint path;int _k;void dfs(int n,int pos){if(path.size()_k){ret.push_back(path);return;}for(int i pos;in;i){path.push_back(i);dfs(n,i1);//i1是换层n1是在同一层里换元素//恢复现场path.pop_back();}}vectorvectorint combine(int n, int k) {_k k;dfs(n,1);return ret;}
};如这种左大右小的树一般就是i1进行深度优先遍历如果是完全二叉树则是n1这种广度遍历
