好网站制作,福建省武夷山市城乡建设网站,代理公司注册费用多少,网站营销推广公司#x1f495;对相爱的人来说#xff0c;对方的心意#xff0c;才是最好的房子。#x1f495; 作者#xff1a;Lvzi 文章主要内容#xff1a;算法系列–递归,回溯,剪枝的综合应用(2) 大家好,今天为大家带来的是算法系列--递归,回溯,剪枝的综合应用(2) 一.括号… 对相爱的人来说对方的心意才是最好的房子。 作者Lvzi 文章主要内容算法系列–递归,回溯,剪枝的综合应用(2) 大家好,今天为大家带来的是算法系列--递归,回溯,剪枝的综合应用(2) 一.括号⽣成
题目链接
括号生成
题目描述
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。
示例: 输入n 3 输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 输入n 1 输出[“()”]
提示
1 n 8
分析:
代码:
class Solution {ListString ret;// 返回值StringBuffer path;// 记录搜索路径int maxLevel, lcnt, rcnt;// max表示最大层数 lcnt表示左括号的数量 rcnt表示右括号的数量public ListString generateParenthesis(int n) {ret new ArrayList();path new StringBuffer();if (n 0) return ret;maxLevel 2 * n;dfs(1, lcnt, rcnt,n);return ret;}private void dfs(int level, int lcnt, int rcnt,int n) {// 递归出口if(level maxLevel) {ret.add(path.toString());return;}if(lcnt n) {path.append(();dfs(level 1,lcnt1, rcnt,n);path.deleteCharAt(path.length() - 1);// 回溯}if(rcnt n lcnt rcnt) {path.append());dfs(level 1, lcnt, rcnt1,n);path.deleteCharAt(path.length() - 1);// 回溯}}
}二.目标和
题目链接
目标和
题目描述
给你一个非负整数数组 nums 和一个整数 target。
向数组中的每个整数前添加 ‘’ 或 ‘-’ 然后串联起所有整数可以构造一个表达式
例如nums [2, 1] 可以在 2 之前添加 ‘’ 在 1 之前添加 ‘-’ 然后串联起来得到表达式 2-1 。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。
示例: 输入nums [1,1,1,1,1], target 3 输出5 解释一共有 5 种方法让最终目标和为 3 。 -1 1 1 1 1 3 1 - 1 1 1 1 3 1 1 - 1 1 1 3 1 1 1 - 1 1 3 1 1 1 1 - 1 3 输入nums [1], target 1 输出1
提示
1 nums.length 200 nums[i] 10000 sum(nums[i]) 1000-1000 target 1000
分析:
思路同子集相同,子集中我们的决策策略是选不选当前的数,本题采用当前数/-当前数 代码:
class Solution {int path, ret, target;public int findTargetSumWays(int[] nums, int _target) {target _target;dfs(nums,0);return ret;}private void dfs(int[] nums, int pos) {if(pos nums.length) {if(path target) ret 1;return;}// path nums[pos];dfs(nums,pos 1);path - nums[pos];//回溯// -path - nums[pos];dfs(nums,pos 1);path nums[pos];// 回溯}
}本题的最优解法其实是动态规划,具体可见我的这篇文章 算法系列–动态规划–背包问题(2)–01背包拓展题目
(有限制条件下的组合问题,且一个数只能选择一次–01背包问题) 3.组合总和
题目链接
组合总和
题目描述
给你一个无重复元素的整数数组 candidates 和一个目标整数 target找出 candidates 中可以使数字和为目标数 target 的所有不同组合并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
示例: 输入candidates [2,3,6,7], target 7 输出[[2,2,3],[7]] 解释 2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。 7 也是一个候选 7 7 。 仅有这两种组合。 输入: candidates [2,3,5], target 8 输出: [[2,2,2,2],[2,3,3],[3,5]] 输入: candidates [2], target 1 输出: []
提示
1 candidates.length 302 candidates[i] 40candidates 的所有元素互不相同1 target 40
分析:
(如果本题是要求组合总和的最多组合数就是一个完全背包问题)
代码:
class Solution {ListListInteger ret;ListInteger path;// 保存搜索路径int sum, target;// sum记录搜索路径上的和public ListListInteger combinationSum(int[] nums, int _target) {ret new ArrayList();path new ArrayList();target _target;dfs(nums,0);return ret;}private void dfs(int[] nums, int pos) {if(sum target) {// 递归出口if(sum target) {ret.add(new ArrayList(path));}return;}for(int i pos; i nums.length; i) {path.add(nums[i]); sum nums[i];dfs(nums,i);// 递归path.remove(path.size() - 1); sum - nums[i];// 回溯}}
}4.字⺟⼤⼩写全排列
题目链接
字⺟⼤⼩写全排列
题目描述
784. 字母大小写全排列
给定一个字符串 s通过将字符串 s 中的每个字母转变大小写我们可以获得一个新的字符串。
返回所有可能得到的字符串集合。以任意顺序返回输出。
示例: 输入s “a1b2” 输出[“a1b2”, “a1B2”, “A1b2”, “A1B2”] 输入: s “3z4” 输出: [“3z4”,“3Z4”]
提示:
1 s.length 12s 由小写英文字母、大写英文字母和数字组成
解题思路
这道题可以使用回溯算法来解决。我们可以逐个遍历字符串中的每个字符然后对于每个字符有两种选择保持原大小写或者转换大小写。通过递归实现所有可能的组合。
代码实现Java
class Solution {ListString ret;StringBuffer path;public ListString letterCasePermutation(String s) {ret new ArrayList();path new StringBuffer();dfs(s,0);return ret;}private void dfs(String s, int pos) {if(pos s.length()) {ret.add(path.toString());return;}// 不改变char ch s.charAt(pos);path.append(ch);dfs(s, pos 1);path.deleteCharAt(path.length() - 1);// 改变(非数字字符)if(ch 0 || ch 9) {char tmp change(ch);path.append(tmp);dfs(s, pos 1);path.deleteCharAt(path.length() - 1);}}private char change(char ch) {if(ch a ch z) return ch - 32;else return ch 32;}
}5.优美的排列
题目链接
优美的排列
题目描述
526. 优美的排列
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm下标从 1 开始只要满足下述条件之一该数组就是一个优美的排列
perm[i] 能够被 i 整除i 能够被 perm[i] 整除
给你一个整数 n 返回可以构造的优美排列的数量。
示例:
输入n 2
输出2
解释
第 1 个优美的排列是 [1,2] perm[1] 1 能被 i 1 整除perm[2] 2 能被 i 2 整除 第 2 个优美的排列是 [2,1]: perm[1] 2 能被 i 1 整除i 2 能被 perm[2] 1 整除
解题思路
这道题可以使用回溯算法来解决。我们可以尝试将数字填充到数组的每个位置上同时检查当前位置是否满足条件。如果满足条件继续递归处理下一个位置否则回溯到上一个位置重新尝试其他数字。
check[i]:用于标记数字是否被使用过ret:返回值
代码实现Java
class Solution {int ret;// 返回值boolean[] check;// 用于标记已经使用过的数字public int countArrangement(int n) {check new boolean[n 1];dfs(1,n);return ret;}private void dfs(int pos, int n) {// pos是下标if(pos n 1) {// 递归出口ret 1;return;}for(int i 1; i n; i) {if(check[i] false (pos % i 0 || i % pos 0)) {check[i] true;// 将使用过的数字标记dfs(pos 1, n);// 递归下一个位置check[i] false;// 回溯}}}
}在这段代码中
pos 表示当前递归到的位置也就是在填充数组时当前正在考虑的位置。i 则表示尝试填充到当前位置 pos 上的数字。
具体来说
pos 从1开始代表数组中的位置递归函数会尝试将数字填充到这些位置上。i 从1到n代表可以填充到当前位置的数字即数组中的元素。 6. 组合
题目链接
组合
题目描述
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。
示例 1
输入n 4, k 2 输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]示例 2
输入n 1, k 1 输出[[1]]
提示
1 n 201 k n
分析:
代码:
class Solution {ListListInteger ret;ListInteger path;int k, n;public ListListInteger combine(int nn, int kk) {n nn; k kk;ret new ArrayList();path new ArrayList();dfs(1);return ret;}private void dfs(int start) {if(path.size() k) {ret.add(new ArrayList(path));return;}for(int i start; i n; i) {path.add(i);// 添加当前数字dfs(i 1);// 递归下一个数字path.remove(path.size() - 1);// 回溯}}
}总结:
对于递归回溯这样的问题,一定要把决策树画的详细,要明确每一步的目的是什么,是根据什么进行递归的
对于这种递归回溯剪枝综合应用的题目来说,其分析思路是比较固定的:
画出详细的决策树(越详细越好,把所有的情况都写出来)分析每一个子问题都是在干啥设计全局变量和dfs(其实dfs是这种问题最难的一步,dfs的设计本质上是一个递归的问题),dfs的设计包括三个方面:函数头,函数体,递归出口考虑回溯和剪枝
