做个人网站的步骤,wordpress+模板检测,永州网站网站建设,微信 html5 网站方法论
1.构建决策树 2.设计代码#xff1a;全局变量、dfs函数 3.剪枝#xff0c;回溯
全排列
给定一个不含重复数字的整数数组 nums #xff0c;返回其 所有可能的全排列 。可以 按任意顺序 返回答案。 示例 1#xff1a; 输入#xff1a;nums [1,2,3] 输出#xff…方法论
1.构建决策树 2.设计代码全局变量、dfs函数 3.剪枝回溯
全排列
给定一个不含重复数字的整数数组 nums 返回其 所有可能的全排列 。可以 按任意顺序 返回答案。 示例 1 输入nums [1,2,3] 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2 输入nums [0,1] 输出[[0,1],[1,0]]
思路 首先构建决策树这道题无非就是遍历所有数字然后组合我们选择采用dfs深度优先的遍历方法同时用一个bool数组check判断该数是否被遍历过每一遍的答案放在path数组里当path数组的长度等于nums长度时则加入到ret结果数组中同时回溯即把path数组pop_back(),并把check数组的该位置设为false。 class Solution {vectorvectorint ret;vectorint path;bool check[7];
public: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(check[i]false){path.push_back(nums[i]);check[i]true;dfs(nums);//回溯恢复现场path.pop_back();check[i]false;}}}
};子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的 子集 幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1
输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2
输入nums [0] 输出[[],[0]]
思路1
从0到n遍历nums决策树判断每个元素选不选
class Solution {vectorvectorint ret;vectorint path;
public:vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}void dfs(vectorint nums,int pos){if(posnums.size()){ret.push_back(path);return;}//选path.push_back(nums[pos]);dfs(nums,pos1);path.pop_back();//恢复现场//不选dfs(nums,pos1);}
};思路2
构建决策树以节点数量来判断第一层为空第二层一个节点第三层两个节点以此类推。
class Solution {vectorint path;vectorvectorint ret;
public:vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}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();}}
};
