数据结构与算法-暴力递归与回溯
目录
博主介绍
1、暴力递归和回溯
1.1、暴力递归概念说明
1.2、回溯算法概念说明
1.3、逆序一个栈
1.4、获取一个字符串的全部子序列
1.5、转换结果
1.6、全排列
1.7、子集
💫点击直接资料领取💫
目录
博主介绍
💂 个人主页:苏州程序大白
💂 个人社区:CSDN全国各地程序猿
🤟作者介绍：中国DBA联盟(ACDU)成员，CSDN全国各地程序猿（媛）聚集地管理员。目前从事工业自动化软件开发工作。擅长C#、Java、机器视觉、底层算法等语言。2019年成立柒月软件工作室，2021年注册苏州凯捷智能科技有限公司
💬如果文章对你有帮助，欢迎关注、点赞、收藏（一键三连）和C#、Halcon、python+opencv、VUE、各大公司面试等一些订阅专栏哦
💅 有任何问题欢迎私信，看到会及时回复
👤 微信号：stbsl6，微信公众号：苏州程序大白
🎯 想加入技术交流群的可以加我好友，群里会分享学习资料
1、暴力递归和回溯
1.1、暴力递归概念说明
暴力递归就是尝试：
将问题转换为规模缩小了的同类问题的子问题。
有明确的不需要继续进行递归的条件，这个条件是递归的退出条件。
有当得到了子问题的结果**之后的决策过程。
不记录每一个子问题的解。
1.2、回溯算法概念说明
回溯算法实际上就是 N 叉树的遍历 ，这个 N 等于当前可做的选择（choices）的总数，同时，在前序遍历的位置作出当前选择（choose 过程），然后开始递归，最后在后序遍历的位置取消当前选择（unchoose 过程）。
回溯算法伪代码模板如下：
result = [] def backtrack(路径, 选择列表) : if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择
回溯算法相当于一个决策过程，递归地遍历一棵决策树，穷举所有的决策，同时把符合条件的决策挑出来。
在过程中，我们需要思考三个问题：
路径：也就是已经做出的选择。
选择列表：当前可以做的选择。
结束条件：也就是到达决策树底层，此时无法继续做选择的条件。
1.3、逆序一个栈
1、题目描述
给定一个栈，在不申请额外数据结构的前提下，使用递归函数逆序这个栈。
2、解题思路
编写一个函数，这个函数的作用是将栈底的元素取出。
比如说，有一个栈，元素从顶而下分别是 [1,2,3] ，那么这个函数可以将栈底的 3 取出，同时将栈变为 [1,2]
//这个方法的作用是，将栈底的元素取出并返回。 public static int getLastElementFromStack(Stack<Integer> stack) { // 使用一个临时变量来接收当前传入栈栈顶的元素 int result = stack.pop(); if (stack.isEmpty()) { // 如果取出元素后栈为空，那么证明 result 保存的就是栈底元素 // 此时直接返回即可 return result; } else { // 否则进行递归，获取栈的最后一个元素 int last = getLastElementFromStack(stack); // 将临时变量压入栈中 stack.push(result); return last; } }
假设现在有一个栈，栈元素自顶而下依次是 [1,2,3] ，那么我们使用上面那个函数获取栈底元素 3 的过程如下：
在第二次进行递归调用时，之前的栈顶元素会在第一次方法调用中被 result 变量保存，不会丢失。
在第三次调用 getLastElementFromStack 函数后，此时已经获取到了栈底元素，于是进行退栈
编写一个方法，用于将栈逆序。
假设我们此时要逆序的栈还是 [1,2,3] ，那么第一次进入 reverseStack 时，他会将栈底元素 3 保存在 temp 中，然后将 [1,2] 作为参数继续进行递归，此时第二次调用 reverseStack ，将 2 保存到 temp 中，同时将 [1] 作为参数继续进行递归，此时第三次调用 reverseStack ，将 1 保存到 temp 中，然后将 [] 作为参数继续进行递归，此时第四次调用 reverseStack ，由于传入的栈为空，那么进行返回，此时回到第三次调用时的栈帧中，将第三次调用时保存的 1 压入到栈中，此时栈为 [1] ，然后此次调用结束，然后分别回到第二次、第一次调用时产生的栈帧中，将该栈帧中 temp 保存的 2 和 3 依次压入栈中，此时逆序完成。
public static void reverseStack(Stack<Integer> stack) { if (stack.isEmpty()) { return; } // 获取当前栈的最后一个元素 int temp = getLastElementFromStack(stack); reverseStack(stack); stack.push(temp); }
1.4、获取一个字符串的全部子序列
1、解题思路
对于这道题，我们可以遍历字符串，然后对这个字符串的每个字符都进行一次选择，即是否选择将当前遍历到的字符加入到结果中，对全部的字符都选择一遍后，就可以得到全部的字符串子序列。
**我们尝试获取字符串 ** abc 的全部子序列。
2、解题代码
public static void getSubsequenceList(int index, String str, List<String> result, String path) { // 如果当前 index 与字符串长度相同，那么证明已经对字符串的最后一个字符做出了选择 // 此时直接将 path 加入到结果列表中并返回即可 if (index == str.length()) { result.add(path); return; } // 进行选择，这个函数表示不将当前字符选择进子序列中 getSubsequenceList(index + 1, str, result, path); // 这个函数表示将当前字符选择进子序列中 getSubsequenceList(index + 1, str, result, path + str.charAt(index)); }
1.5、转换结果
1、题目描述
规定 1 对应 A 、2 对应 B 、3 对应 C ，那么一个数字字符串比如 111 可以转换为 AAA 、KA 和 AK
给定一个只有数字组成的字符串 str ，返回有多少种转换结果。
2、解题思路
以 11111 为例，它的转换过程可以如下：
将第一个 1 转为 A ，然后把剩下四个 1 看为另外一个部分，对剩下的部分进行转换。
将前面两个 1 转为 K ，然后将剩下的三个 1 看为另一个部分，对剩下的部分进行转换。
由于 111 无法转换为对应的数，所以 11111 没有其他的分支。
3、解题代码
/** * 对于 str[0, index - 1] 位置上的字符已经转换完毕 * 这个函数表示 str[index, ...] 有多少种转换结果 * @param str * @param index * @return */ public static int process(String str, int index) { // base case ，如果此时转换的是 str 的最后一个字符，那么只有一种转换结果 if (index == str.length()) { return 1; } // 如果当前字符为 0 ，那么没有任何转换结果 if (str.charAt(index) == '0') { return 0; } // 如果当前字符不是 '0' if (str.charAt(index) == '1') { // 将自己作为单独的一部分，后续有多少种方法 int result = process(str, index + 1); if (index + 1 < str.length()) { // 将 str[index , index + 1] 看为单独的一部分 result += process(str, index + 2); } return result; } if (str.charAt(index) == '2') { int result = process(str, index + 1); if (index + 1 < str.length() && str.charAt(index + 1) >= '0' && str.charAt(index + 1) <= '6') { result += process(str, index + 2); } return result; } // 对于 '3' - '9' ，这种情况直接将自己看为单独一部分 return process(str, index + 1); }
1.6、全排列
1、题目描述
给定一个不含重复数字的数组 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]]
2、解题思路
使用回溯算法解决这道题，我们需要明确这道题的三个条件
路径：当前已经进行排列的数字集合，我们将他们放在一个列表中。
选择列表：nums 数组中不存在于 路径 中的那些元素。
结束条件：当 nums.length 等于路径列表的长度时，此时 nums 中的所有元素都在路径列表中出现。
3、解题代码
public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); if (nums == null || nums.length == 0) return result; // 使用一个双端列表来模拟 path ，便于我们撤销选择，进行回溯 LinkedList<Integer> path = new LinkedList<>(); dfs(nums, path, result); return result; } private void dfs(int[] nums, LinkedList<Integer> path, List<List<Integer>> result) { // 如果此时达到终止条件，即 path 的长度等于 nums 的长度，此时所有数字都被选择完 // 这里不能添加 path ，因为 path 只是一个引用，我们需要将当前 path 中的数据取出来放入到结果中，这样才不会让 path 发生变化时，影响 result 里面的结果 if (nums.length == path.size()) { // 将当前 path 添加到总结果中 result.add(new LinkedList(path)); // 直接返回 return; } for (int i = 0;i < nums.length;i++) { // 排除不合法的选择，如果此时路径已经包含了这个数，那么不将这个数加入到 path 中，直接跳过 if (path.contains(nums[i])) { continue; } // 做选择，将当前遍历到的数组元素加入到 path 中 path.addLast(nums[i]); // 进入下一层树 dfs(nums, path, result); // 撤销选择，进行回溯 path.removeLast(); } }
1.7、子集
1、题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例
输入：nums = [1,2,3]
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
2、解题思路
使用回溯算法解决这道题，这道题与 1.4 获取字符串的全部子序列一题的解题思路一致，都是在每一步分别对当前元素进行选择，然后收集选择对应的结果。
3、解题代码
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); if (nums == null || nums.length == 0) return result; LinkedList<Integer> path = new LinkedList<>(); dfs(0, nums, result, path); return result; } private void dfs(int index, int[] nums, List<List<Integer>> result, LinkedList<Integer> path) { // 判断此时是否到达终止条件，当 index == nums.length 时，证明已经对最后一个元素进行了选择，此时收集结果 if (index == nums.length) { result.add(new LinkedList(path)); return; } // 进行选择，我们既要收集将当前数组元素加入 path 的结果，也要考虑不讲当前元素加入 path 的结果 path.addLast(nums[index]); // 选择 1 ，将 nums[index] 加入 path dfs(index + 1, nums, result, path); // 选择 2 ，不将 nums[index] 加入 path path.removeLast(); dfs(index + 1, nums, result, path); }
