wordpress建站中英文,冠县网站制作,seo是什么意思 为什么要做seo,金沙网站怎么做代理文章目录 全排列子集找出所有子集的异或总和再求和全排列 II电话号码的字母组合 全排列 题目#xff1a;全排列 思路 通过深度优先搜索的方式#xff0c;不断枚举每个数在当前位置的可能性#xff0c;然后回溯到上一个状态#xff0c;直到枚举完所有可能性得到正确的结果 r… 文章目录 全排列子集找出所有子集的异或总和再求和全排列 II电话号码的字母组合 全排列 题目全排列 思路 通过深度优先搜索的方式不断枚举每个数在当前位置的可能性然后回溯到上一个状态直到枚举完所有可能性得到正确的结果 res一个二维向量vectorvectorint用于存储所有生成的排列。path一个一维向量vectorint用于存储当前正在构建的排列。check一个布尔数组bool check[7]用于标记数组nums中的每个元素是否已经被用于当前排列中。这里假设nums数组的大小不会超过6因为数组索引从0开始最大索引为6时数组大小为7。递归的终止条件是path的大小等于nums的大小。在递归过程中使用check数组来确保不会重复使用同一个元素。使用path.push_back(nums[i])和path.pop_back()来实现回溯即在尝试下一个元素之前需要将当前元素从path中移除以便尝试其他可能的元素组合。通过check[i] true和check[i] false来标记元素是否已被使用。
C代码
class Solution
{vectorvectorint res;vectorint path;bool check[7];public:void dfs(vectorint nums){if(nums.size() path.size()){res.push_back(path);return ;}for(int i 0; i nums.size(); i ){if(!check[i]){path.push_back(nums[i]);check[i] true;dfs(nums);// 回溯 - 恢复现场path.pop_back();check[i] false;}}}vectorvectorint permute(vectorint nums) {dfs(nums);return res;}
};
子集 题目子集 思路1 我们先将所有结果个数为1的选出来再再其基础上选出结果个数为2的依次类推 从 pos 开始遍历 nums 数组。对于每个位置 i 执行以下操作 将 nums[i] 添加到 path 中。递归调用 dfs 函数以 i 1 作为新的起始位置继续搜索。在递归调用返回后进行回溯操作将刚刚添加到 path 中的 nums[i] 移除以便尝试其他可能的元素组合或停止进一步搜索。
C代码
class Solution
{vectorvectorint ret;vectorint path;
public:vectorvectorint subsets(vectorint nums) {dfs(nums, 0);return ret;}void dfs(vectorint nums, int pos){ret.push_back(path);for(int i pos; i nums.size(); i){path.push_back(nums[i]);dfs(nums, i 1);path.pop_back();}}
};思路2 依次枚举1选不选选的话在1基础上2选不选选的话在2基础上选不选枚举出所有结果当当前位置等于数组大小时将结果加入答案中 首先检查pos是否等于nums的大小。如果是说明已经遍历到数组的末尾此时path代表了一个完整的子集可能是空集也可能是包含数组所有元素的集合这取决于dfs的调用过程。然后将这个子集添加到ret中并返回将nums[pos]添加到path中然后递归调用dfs函数以pos 1作为新的起始位置继续搜索。在递归调用返回后执行回溯操作从path中移除nums[pos]以便尝试其他可能的元素组合或停止进一步搜索。
class Solution
{vectorvectorint ret;vectorint path;
public:vectorvectorint subsets(vectorint nums) {dfs(nums, 0);return ret;}void dfs(vectorint nums, int pos) {if (pos nums.size()) {ret.push_back(path);return;}path.push_back(nums[pos]);dfs(nums, pos 1);path.pop_back();dfs(nums, pos 1);}
};
找出所有子集的异或总和再求和 题目找出所有子集的异或总和再求和 思路 本题和上题思路一样我们使用上题的第一种思路依次枚举1选不选选的话在1基础上2选不选选的话在2基础上选不选 不同的是将每个子集的值异或并将其相加 从数组的第一个元素开始递归地构建所有可能的子集在每个递归步骤中可以选择包含当前元素通过异或操作更新path或不包含当前元素直接递归到下一个位置int path选择1将其异或在path上再选2异或在path上当到达数组的末尾时将当前的 path即当前子集的异或和加到 res 上
C代码
class Solution
{int path;int res;
public:void dfs(vectorint nums, int pos){res path;for(int i pos; i nums.size(); i ){path ^ nums[i];dfs(nums, i 1);path ^ nums[i];}}int subsetXORSum(vectorint nums) {dfs(nums, 0);return res;}
};全排列 II 题目全排列 II 思路 同一个节点的分支中相同的元素只能选择一次 同一个数只能使用一次 只关心不合法分支
if(cheak[i] true) || (i ! 0 nums[i] nums[i-1] cheak[i-1] false))
C代码
class Solution
{vectorint path;vectorvectorint ret; bool check[9];
public:vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ret;}void dfs(vectorint nums, int pos){if(pos nums.size()){ret.push_back(path);return;}for(int i 0; i nums.size(); i){if(check[i] true|| (i ! 0 nums[i] nums[i - 1] check[i - 1] false)) continue;path.push_back(nums[i]);check[i] true;dfs(nums, pos 1);path.pop_back();check[i] false;}}
};只关心合法分支
if(cheak[i] false) (i 0 || nums[i] ! nums[i-1] ||cheak[i-1] ! false))
C代码
class Solution
{vectorint path;vectorvectorint ret; bool check[9];
public:vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ret;}void dfs(vectorint nums, int pos){if(pos nums.size()){ret.push_back(path);return;}for(int i 0; i nums.size(); i){if(check[i] false (i 0 || nums[i] ! nums[i - 1] || check[i - 1] ! false)) {path.push_back(nums[i]);check[i] true;dfs(nums, pos 1);path.pop_back();check[i] false;}}}
};电话号码的字母组合 题目电话号码的字母组合 思路 利用一个全局的字符串数组来帮我映射数组和字母之间的关系 如果pos等于digits的长度说明已经处理完所有数字将当前的path即一个完整的字母组合添加到结果数组ret中并返回否则对于当前数字digits[pos]遍历其对应的所有字母通过str[digits[pos] - 0]访问。对于每个字母执行以下操作 将当前字母添加到path的末尾。 递归调用dfs函数处理下一个数字pos 1。 在递归返回后将刚刚添加的字母从path中移除以便尝试当前数字对应的下一个字母。
C代码
class Solution
{vectorstring ret;string path;string str[10]{,, abc, def,ghi, jkl, mno,pqrs, tuv, wxyz};
public:vectorstring letterCombinations(string digits) {if(digits.size() 0) return ret;dfs(digits, 0);return ret;}void dfs(string digits, int pos){if(pos digits.size()){ret.push_back(path);return;}for(auto ch : str[digits[pos] - 0]){path.push_back(ch);dfs(digits, pos 1);path.pop_back();}}
};
