做空eth网站,网站改版建设公司,高端品牌网站建设,四川建设人才网官网登录目录
1、决策树
2、算法实战应用【leetcode】
2.1 题一#xff1a;全排列
2.2.1 算法原理
2.2.2 算法代码
2.2 题二#xff1a;子集
2.2.1 算法原理【策略一】
2.2.2 算法代码【策略一】
2.2.3 算法原理【策略二#xff0c;推荐】
2.2.4 算法代码【策略二#x…目录
1、决策树
2、算法实战应用【leetcode】
2.1 题一全排列
2.2.1 算法原理
2.2.2 算法代码
2.2 题二子集
2.2.1 算法原理【策略一】
2.2.2 算法代码【策略一】
2.2.3 算法原理【策略二推荐】
2.2.4 算法代码【策略二推荐】
2.3 题三找出所有子集的异或总和再求和
2.3.1 算法原理
2.3.2 算法代码【解法一】(不推荐) 2.3.3 算法代码【解法二】(推荐) 2.4 题四全排列 II
2.4.1 算法原理
2.4.2 算法代码 1、决策树
决策树是一种树形结构的监督学习算法广泛应用于分类任务和回归任务中。它通过递归地将数据集分割成更小的子集最终形成一个树形模型用于预测新数据的输出。
决策树是一种树形结构其中每个内部节点表示一个属性上的测试每个分支代表一个测试输出每个叶节点代表一种类别。
决策树是一种十分常用的分类方法。它是一种监督学习所谓监督学习就是给定一堆样本每个样本都有一组属性和一个类别这些类别是事先确定的那么通过学习得到一个分类器这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。
面对上难度的DFS算法题我们首先要做的就是画出决策树。
注意画出的决策树越详细越好 2、算法实战应用【leetcode】
2.1 题一全排列 . - 力扣LeetCode 2.2.1 算法原理
画出决策树记住决策树越详细越好设置全局变量(全局变量的设置因题而异)本题设置二维数组ret为返回值记录全部的全排列数组path记录路径布尔类型的check数组实现剪枝操作对于递归函数我们仍然要站在宏观角度聚焦于某一层要做的事来设计DFS算法不可避免的就是回溯、剪枝与函数出口等细节问题的考虑对于本题回溯的设计在dfs完下一层回到当前层后再进行恢复现场的操作(删除下一层在path中的数据)注意本题需要对path和check均进行回溯操作对于本题剪枝的设计通过布尔数组的判断判断数组中数据可否放进路径path中对于本题递归函数的出口将path中存放数据的数量和nums数组长度相比较若相等则添加到ret中。 2.2.2 算法代码
class Solution {ListListInteger ret;ListInteger path;boolean[] check;public ListListInteger permute(int[] nums) {ret new ArrayList();path new ArrayList();check new boolean[nums.length];dfs(nums);return ret;}public void dfs(int[] nums) {//函数出口if(path.size() nums.length) {ret.add(new ArrayList(path));return;}for(int i 0; i nums.length; i) {if(!check[i]) {path.add(nums[i]);check[i] true;dfs(nums);//将下一层中的相关数据删除 - 回溯 - 恢复现场 - 1.path 2.check//add新数据时递归仍然在本层中add的是本层i位置处的新数据//dfs完后i仍然为本层add时的数据的下标//此时回溯要将path和check恢复现场path.remove(path.size() - 1);check[i] false;}}}
} 2.2 题二子集 . - 力扣LeetCode 2.2.1 算法原理【策略一】
画决策树设置全局变量 : ①ListListInteger ret;//返回值 ②ListInteger path;//记录路径设计函数头void dfs(nums, pos);//pos为下一次进入path中元素的下标设计函数体①:选:path nums[pos]; dfs(nums,pos1)②:不选:dfs(nums,pos1);考虑函数出口pos nums.length将path添加进ret中return处理细节问题①:回溯 - 恢复现场path.remove(pathsize()-1); ②:剪枝无 2.2.2 算法代码【策略一】
class Solution {ListListInteger ret;ListInteger path;public ListListInteger subsets(int[] nums) {ret new ArrayList();path new ArrayList();dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos) {//函数出口if(pos nums.length) {ret.add(new ArrayList(path));return;}//选path.add(nums[pos]);dfs(nums, pos 1);//回溯 - 恢复现场path.remove(path.size() - 1);//不选(不做任何操作即可)dfs(nums, pos 1);}
}
2.2.3 算法原理【策略二推荐】
思想
分三个支线每个节点就是一个子集所以每刚进入递归函数时就把path添加进ret中pos依然为下一个要添加进path中的元素的下标。叶子节点即为函数出口。 步骤
画决策树设计代码 ①全局变量 ret/path ②函数头 void dfs(nums, pos); ③函数体 1.ret.add(path);2.依次枚举该节点后的元素 ④函数出口 无细节问题 ①回溯 - 恢复现场:path.remove(path,size()-1) ②剪枝 - 无 2.2.4 算法代码【策略二推荐】
class Solution {ListListInteger ret;ListInteger path;public ListListInteger subsets(int[] nums) {ret new ArrayList();path new ArrayList();dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos) {ret.add(new ArrayList(path));//从pos位置开始向后枚举for(int i pos; i nums.length; i) {//依次枚举下标为ipath.add(nums[i]);//从当前元素后面的元素中选dfs(nums, i 1);//回溯 - 恢复现场path.remove(path.size() - 1);}}
} 2.3 题三找出所有子集的异或总和再求和 . - 力扣LeetCode 2.3.1 算法原理
本题与上一题解题思想如出一辙
解法一直接cv上一题的代码再将每组子集相异或再求和。不推荐
解法二将path设置为每个子集的异或值(策越二每个节点都是一个子集)再创建一个全局变量sum求和即可回溯时直接利用异或消消乐的特性恢复现场即可。
解法二的时间效率更加优秀建议大家使用解法二解题。
2.3.2 算法代码【解法一】(不推荐)
class Solution {ListListInteger total;ListInteger path;public int subsetXORSum(int[] nums) {total new ArrayList();path new ArrayList();ListInteger sum new ArrayList();dfs(nums, 0);for(int i 0; i total.size(); i) {int ret 0;for(int j 0; j total.get(i).size(); j) {ret ^ (total.get(i).isEmpty() ? 0 : total.get(i).get(j));}sum.add(ret);}int val 0;for(int x : sum) val x;return val;}public void dfs(int[] nums, int pos) {total.add(new ArrayList(path));for(int i pos; i nums.length; i) {path.add(nums[i]);dfs(nums, i 1);path.remove(path.size() - 1);}}
} 2.3.3 算法代码【解法二】(推荐)
class Solution {int path;//每个子集所有元素的异或值int sum;public int subsetXORSum(int[] nums) {path 0;sum 0;dfs(nums, 0);return sum;}public void dfs(int[] nums, int pos) {sum path;for(int i pos; i nums.length; i) {path ^ nums[i];dfs(nums, i 1);//回溯 - 恢复现场 - 异或消消乐path ^ nums[i];}}
} 2.4 题四全排列 II . - 力扣LeetCode 2.4.1 算法原理
本题整体框架与上文题一全排列相同回溯函数出口函数体等设计这里不再赘述。
由于出现重复的元素故本题算法需要添加更多的剪枝操作。
在数组有序的情况下(有序时相同的元素才会相邻)我们可以这样来设计剪枝
剪枝
①同一个元素只能出现一次 -- boolean[] check ②在一个节点的分支中相同数值的元素只能选择一次
筛选节点
符合条件的节点 check[i]flase (i0 || nums[i-1] ! nums[i] || check[i-1]true) 2.4.2 算法代码
class Solution {ListListInteger ret;ListInteger path;boolean[] check;//同一个数据只能出现一次public ListListInteger permuteUnique(int[] nums) {ret new ArrayList();path new ArrayList();check new boolean[nums.length];//数据有序的情况下保证重复的元素是相邻的Arrays.sort(nums);dfs(nums);return ret;}public void dfs(int[] nums) {if(path.size() nums.length) {ret.add(new ArrayList(path));return;}for(int i 0; i nums.length; i) {//剪枝 - 筛选出符合条件的分支//同一个数据只能出现一次 一个节点上相同数值的元素只能选择一次if(!check[i] (i 0 || nums[i - 1] ! nums[i] || check[i - 1])) {path.add(nums[i]);check[i] true;dfs(nums);//回溯 - 恢复现场path.remove(path.size() - 1);check[i] false;}}}
} END
