时间轴网页网站模板,濮阳是哪里,化妆品网站栏目设计,静态网站做毕业设计找出所有子集的异或总和再求和 题目解析 算法原理 解法 决策树 这种决策使得每一次递归都是有效的递归#xff0c;每一个节点都是最终的结果#xff0c;所以这棵决策树是不用剪枝的#xff0c;也没有递归出口的#xff1b; 注意 决策树执行添加元素… 找出所有子集的异或总和再求和 题目解析 算法原理 解法 决策树 这种决策使得每一次递归都是有效的递归每一个节点都是最终的结果所以这棵决策树是不用剪枝的也没有递归出口的 注意 决策树执行添加元素的操作前要先从子集末尾元素在 nums 的位置后面是否还有元素如果有元素则可以添加反之则不可以添加 全局变量 开始时子集是空集所以异或的结果为 0 path 初始值刚好是0所以不用处理子集为空的情况 函数结构 在递归到决策树的某一层时要知道从 nums 的哪个元素开始向后枚举因此设计 dfs(nums,pos) 编写代码 虽然没有写 return 来回溯但是在每次向下递归新一层的 dfs 时这层 dfs 执行完就会自动返回上一层的 dfs 全排列Ⅱ 题目解析 算法原理 这道题其实就是全排列Ⅰ的plus 版本只是多了重复的数大体框架和全排列Ⅰ相同只是剪枝操作需要更细致一点全排列Ⅰ的解法可以先看下面这篇博客的第一题 【递归搜索与回溯算法】穷举 vs 暴搜 vs 深搜 vs 回溯 vs 剪枝算法入门专题详解 两道题唯一的出入的就是剪枝操作所以我们下面只讲全排列Ⅱ该如何剪枝 1. 两种剪枝 1. 在同一个节点如图中的黑色节点的所有分支中相同的元素只能选择一次 2. 同一个数只能使用一次可以设置一个 check[] 数组来标记一下用过的数为 true 1.1 根据两种剪枝完善决策树 2. 两种思考方式 本质相同都是针对是否需要剪枝的情况作出相应的处理 3. 只关心不合法的分支被剪枝的分支 红色剪枝条件 check[ i ] true表示同一个数只能使用一次 粉色剪枝条件 nums[ i ] nums [ i -1 ]表示同一个节点的所有分支中相同数只能使用一次 3.1 问题一如果 nums 中重复元素不是连在一起的那么这个判断条件无法使用 3.1.1 问题解析 如果我们要全排列的数组是 [ 1 , 2 , 1 , 3 , 1 ]那么无法判断同一个节点其中一条分支要递归的数是否在前面分支中已经出现过了 3.1.2 解决办法 我们可以在正式递归之前先对 nums 数组先进行排序方便后续的剪枝操作在大多数情况下排序数组的时间复杂度O(N*logN)对于递归O(2^N)来说可以忽略不记 3.2 问题二无法筛查掉红色剪枝的分支和合法分支相邻的情况 3.2.1 问题解析 nums[ i ] nums [ i -1 ] 这个对不合法分支的判断条件范围还是太广了无法筛查掉红色剪枝的分支和合法分支不应该被剪枝的分支相邻的情况
因为这些分支所代表的数是相同的所以 nums[ i ] 所在的分支会被识别为不合法分支而被执行粉色剪枝
但是实际上被红色剪枝的 nums[ i -1 ] 所在分支本身就是不合法分支
只有当 nums[i-1]和 nums[i] 两条分支都是合法的时候才需要判断 nums[ i ] 是否等于 nums[ i - 1 ] 3.2.2 解决办法 我们要把下面这两种情况区分开 那么怎么区分开呢其实非常简单就是判断两个数是否在决策树的同一层 (1) 对于不同层 两个数不是同一层哪怕 nums[ i ] nums [ i - 1 ]nums[ i -1 ] 所在分支肯定也会被执行红色剪枝 因此 nums[i] 所在分支就是合法分支 (2) 对于同一层 如果递归时发现check[i-1]false则说明 nums[i-1] 和 nums[i] 所在位置为决策树同一层如果是同一层并且这两个数还相等此时递归 nums[i] 的分支就是不合法的分支 (3) 改进条件 我们在准备对 nums [ i ] 进行递归时先判断 check[i] false如果 check[ i -1 ] false 那么就可以判断 nums[i-1] 和 nums[i] 在同一层
对同一层进行进一步判断如果 nums[i-1] nums[i]说明 nums[i] 所在分支不合法 3.3 问题三i 0时访问 nums[ i -1 ] 会越界 只关心不合法分支的最终判断条件 i ! 0 check[ i ] false num[i]nums[i-1] 3.4 总结不合法分支 4. 只关心合法的分支不被剪枝的分支 4.1 先判断该节点是否已经被使用是否会被执行红色剪枝 如果我们的思考链路是只关心分支合法那么第一步就是检查该分支是否被红色剪枝
所以第一步就是判断 check [ i ] false
合法分支是一条 不被执行红色剪枝 不被执行粉色剪枝 的分支所以在判断该分支不被执行红色剪枝后我们就需判断该分支是否被执行粉色剪枝 4.2 节点未被使用的情况下是否被执行粉色剪枝 4.2.1 节点在决策树的深度相同但是代表的数不同 我们先来分析下面这条分支在检查完 check[ i ] false 而不被执行红色剪枝之后之后我们来判断是否被粉色剪枝 显然nums[ i ] ! nums[ i -1 ]因此肯定不会执行粉色剪枝nums 已经提取排好序了
此时的判断条件为 check[ i ] false ( nums [ i ] ! nums [ i-1] .......) 4.2.2 节点代表的数相同但是该节点前一条分支已经被使用 如果 nums[ i ] nums [ i - 1 ]但是 nums[ i - 1 ] 已经被使用过了此时 check [ i - 1 ] true那么此时的分支也是合法的所以此时的判断条件 4.2.3 当 i 0 的情况
如果只是考虑当前分支是否合法那么 i 是可以等于 0 的 i 0 表示的是数组第一个元素只要确保 check[ 0 ] false就一定是可以大胆枚举的因为这是对 nums 的第一个元素进行枚举的分支这条分支必定是合法分支一定是从考虑合法分支的角度出发 此时的判断条件 5. 两种思考方式判断条件的区别
如果考虑当前分支不合法就需要根据前一条分支的具体情况来对当前分支的合法与否作出判断如果当前分支的 i0则会出现数组越界 6. 处理细节问题 7. 编写代码 7.1 只关心不合法分支 7.2 只关心合法分支 电话号码的字母组合 题目解析 算法原理 解法一 : 暴力枚举 定义两层 for 循环对字符映射的数字的所有组合进行暴力枚举 但是如果一个字符映射的数字过多使用暴力枚举是不好操作的 解法二 深度优先遍历 决策树 对决策树进行一次深度优先遍历在叶子节点收集结果即可 解决数字和字符串的映射关系 我们可以使用字符串数组让字符串数组前两个位置空着让下标为2的数组元素存 abc 这个字符串往后依此类推 我们在遍历原始字符串的时候拿到字符2之后减去字符 0 对应的 Ascii 码值就可以对应字符串数组的下标元素 全局变量 设计函数 编写代码 括号生成 题目解析 算法原理 给一个括号子串必须从头到尾遍历子串的每一个括号字符如果在遍历的过程中出现左括号的数量大于右括号的数量那么这个子串就一定不是有效括号子串 解法暴搜 决策树 蓝色剪枝表示添加 ( 数量大于 n 剪枝紫色剪枝表示添加 ) 数量大于 ( 的数量 全局变量 这些变量可以设置成全局变量也可以作为参数传给 dfs区别在于恢复现场时采取的措施不同 设置函数 编写代码 组合 题目解析 算法原理 解法 : 暴搜 决策树 根据题目示例可以知道 得到的 path 元素没有顺序可言path 的区别只在元素的种类所以可以画出决策树 1. 两层节点代表的数相同执行紫色剪枝2. 前面的分支已经枚举过这种可能执行蓝色剪枝 path 只看元素种类不看元素顺序 发现规律 所以我们不需要定义全局变量来剪枝只需要在向下递归时从当前节点元素的下一个元素开始递归即可 设置函数 编写代码 目标和 题目解析 算法原理 解法 决策树 这棵决策树是要深度优先遍历的每一个节点每次递归只能遍历一条分支而不是在一个节点递归时同时记录所有分支通过递归回溯相结合的方式遍历整棵决策树 编写代码 path 是全局变量时候的代码手动回溯 path 作为参数的代码 自动回溯 报错原因 如果我们提前让 path nums[i] 是真正修改了 path 的状态并且记录 那么编译器在帮我们恢现场的时候只会恢复 pos 的值而因为 path 的值无法恢复到上次递归前的值 组合总和 题目解析 算法原理 解法一暴搜 决策树 红色剪枝剪去超过 target 的分支 紫色剪枝剪去重复出现的组合 最终结果 发现规律 从最终的有效递归图我们可以发现有效递归都是是从当前节点开始向后枚举的
所以我们在进行下一轮递归时从当前节点开始枚举即可 编写代码 报错原因没有考虑以 pos 越界的情况作为递归出口并且忽略了本题是可以选择重复元素的 恢复现场的操作是去掉最后一个元素并且remove() 的 API 也用不对 解法二 决策树 这棵决策树是的每一层是在节点和 target 时枚举重复元素相加的个数直到枚举的节点和大于 target 处理细节问题 (1) 恢复现场的时机 这个解法有一个特别容易被忽略的地方就是回溯现场的时机如左下角的两次递归回溯 第一次回溯是不能恢复现场的因为第二次递归是在第一次递归了0个5的基础上再多递归1个5也就是说对于同一层回溯只有递归完一个元素能枚举的所有使用次数才能恢复现场 并且恢复现场时sum 会自动恢复但是 path 需要我们手动恢复 (2) 在解法一的基础上修改代码 对于解法二只是枚举的策略不同其他的递归剪枝操作和解法一是相同的因此我们只需要删除红色框的代码在此基础上重新编写即可 (3) 用于枚举的循环的终止条件 这个循环的小细节是枚举 nums[pos] 的个数是从0个开始的当 k* nums[ pos ] aim枚举完这个数的所有可能的使用个数 (4) 在哪里恢复现场 不要在上面 for 循环恢复现场出了 for 循环表示 nums[pos] 的使用个数枚举完毕此时再恢复现场 (5) 恢复现场的循环起点 注意恢复现场的循环从 k1 开始 因为我们在递归枚举时 会枚举 nums[pos] 使用0次的情况上层 for 循环从 k0 开始循环 但是 path 真正添加 nums[pos] 时nums[pos] 的使用次数是不为0的所以我们恢复现场要从 k1 开始 所以我们手动恢复现场本质上恢复的的是执行 path.remove(size()-1) 操作 k-1 次sum 则是因为通过参数传递编译器会自动帮助我们恢复 sum 编写代码 小优化 字母大小写全排列 题目解析 算法原理 解法暴搜 决策树 我们可以在原字符串 s 上操作当 s 递归到叶子节点时把叶子节点的 s 添加到 ret 中也可以定义一个全局变量 path 遍历到 s 字符串的字母字符时就把变或不变的字符每次只能选一个添加到 path 上如果遍历到的是数字直接添加到 path 后即可 全局变量 函数设计 编写代码
