沈阳网站建设优化企业,外贸网站推广销售,做封面哪个网站好,wordpress 4.0 静态化文章目录 1、全排列2、子集3、找出所有子集的异或总和再求和4、全排列 II5、电话号码的字母组合6、括号生成 1、全排列 给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 class Solution {
public:vectorvectori… 文章目录 1、全排列2、子集3、找出所有子集的异或总和再求和4、全排列 II5、电话号码的字母组合6、括号生成 1、全排列 给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 class Solution {
public:vectorvectorint ret;vectorint path;//vectorbool sign(7);并不能使用它它并不能使用[],底层储存问题bool sign[7];vectorvectorint permute(vectorint nums) {dfs(nums);return ret;}void dfs(vectorint nums){if(nums.size()path.size()){ret.push_back(path);return;}for(int i0;inums.size();i){if(sign[i]false){path.push_back(nums[i]);sign[i]true;dfs(nums);path.pop_back();sign[i]false;}}}
};2、子集 给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的 子集幂集。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 class Solution {
public:vectorvectorint ret;vectorint path;vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}//解法一// void dfs1(vectorint nums,int i)// {// if(inums.size())// {// ret.push_back(path);// return;// }// //选// path.push_back(nums[i]);// dfs(nums,i1);// path.pop_back();// //不选// dfs(nums,i1);// }//解法二void dfs(vectorint nums,int pos){ret.push_back(path);for(int ipos;inums.size();i){path.push_back(nums[i]);dfs(nums,i1);path.pop_back();}}
};3、找出所有子集的异或总和再求和 一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果如果数组为 空 则异或总和为 0 。 例如数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 1 。 给你一个数组 nums 请你求出 nums 中每个 子集 的 异或总和 计算并返回这些值相加之 和 。 注意在本题中元素 相同 的不同子集应 多次 计数。 数组 a 是数组 b 的一个 子集 的前提条件是从 b 删除几个也可能不删除元素能够得到 a 。 class Solution {
public:// vectorint ret;// vectorint path;// int subsetXORSum(vectorint nums) {// dfs(nums,0);// int sum0;// for(int i0;iret.size();i)// {// sumret[i];// }// return sum;// }// void dfs(vectorint nums,int pos)// {// int sum0;// for(int i0;ipath.size();i)// {// sum^path[i];// }// ret.push_back(sum);// for(int ipos;inums.size();i)// {// path.push_back(nums[i]);// dfs(nums,i1);// path.pop_back();// }// }int sum0;int path0;int subsetXORSum(vectorint nums){dfs(nums,0);return sum;}void dfs(vectorint nums,int pos){sumpath;//每次开始的节点都是我们需要的for(int ipos;inums.size();i){path^nums[i];dfs(nums,i1);path^nums[i];//恢复现场}}
};4、全排列 II 给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。 class Solution {
public:vectorvectorint ret;vectorint path;bool check[8];vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(),nums.end());//方便后面处理分支dfs(nums,0);return ret;}void dfs(vectorint nums,int pos){if(posnums.size())ret.push_back(path);for(int i0;inums.size();i){//剪枝方法一只关心合法分支// if(check[i]false(i0||nums[i]!nums[i-1]||(check[i-1]truenums[i]nums[i-1])))// {// check[i]true;// path.push_back(nums[i]);// dfs(nums,pos1);// check[i]false;// path.pop_back();// }//剪枝方法二,只关心不合法分支if(check[i]true||(i!0nums[i]nums[i-1]check[i-1]false))continue;check[i]true;path.push_back(nums[i]);dfs(nums,pos1);check[i]false;path.pop_back();}}
};5、电话号码的字母组合 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 class Solution {
public:string hash[10]{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstring ret;string path;vectorstring letterCombinations(string digits) {if(digits.empty())return ret;dfs(digits,0);return ret;}void dfs(string digits,int pos){if(posdigits.size()){ret.push_back(path);return;}for(auto a : hash[digits[pos]-0]){path.push_back(a);dfs(digits,pos1);path.pop_back();}}
};6、括号生成 数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。 class Solution {
public:int left,right,n;vectorstring ret;string path;vectorstring generateParenthesis(int _n) {n_n;dfs();return ret;}void dfs(){if(rightn){ret.push_back(path);return;}if(leftn){path.push_back(();left;dfs();path.pop_back();left--;}if(rightleft){path.push_back());right;dfs();path.pop_back();right--;}}
};
