html公司网站模板源码,企业信息填报系统,移动 开发 网站建设,新媒体运营师考试报名官网算法题
Leetcode 216.组合总和III
题目链接:216.组合总和III
大佬视频讲解#xff1a;组合总和III视频讲解 个人思路 在昨日做过的组合问题后#xff0c;这道题的限制 多了两个#xff1a;1.要找到和为n的k个数的组合#xff0c;2.整个集合已经是固定的了[1,...,9]… 算法题
Leetcode 216.组合总和III
题目链接:216.组合总和III
大佬视频讲解组合总和III视频讲解 个人思路 在昨日做过的组合问题后这道题的限制 多了两个1.要找到和为n的k个数的组合2.整个集合已经是固定的了[1,...,9]依然用回溯法解决只是找寻结果的条件不同。 解法
回溯法
把改题抽象为如下树形结构 再跟上
回溯法三部曲
1.确定递归函数参数 定义一个一维数组path来存放符合条件的结果一个二维数组result来存放结果集。再定义path(结果路径) 和 result为全局变量。 回溯法中需要如下参数 targetSumint目标和也就是题目中的n。kint就是题目中要求k个数的集合。sumint为已经收集的元素的总和也就是path里元素的总和。startIndexint为下一层for循环搜索的起始位置。 强调回溯法中递归函数参数很难一次性确定下来一般先写逻辑需要啥参数了填什么参数。
2.确定终止条件 首先k其实就已经限制树的深度因为就取k个元素树再往下深了没有意义。所以如果path.size() 和 k相等了就终止。如果此时path里收集到的元素和sum 和targetSum就是题目描述的n相同了就用result收集当前的结果。 3.单层搜索过程 集合固定的就是9个数[1,...,9]所以for循环固定i9 处理过程path收集每次选取的元素相当于树型结构里的边sum来统计path里元素的总和。 最后要注意处理过程 和 回溯过程是一一对应的处理有加回溯就要有减 搞定完回溯法再做一下剪枝优化
按题意已选元素总和如果已经大于n图中数值为4了那么往后遍历就没有意义了直接剪掉。
class Solution {LinkedListInteger path new LinkedList();ListListInteger ans new ArrayList();public ListListInteger combinationSum3(int k, int n) {build(k, n, 1, 0);return ans;}private void build(int k, int n, int startIndex, int sum) {if (sum n) return;//剪枝 剪去和大于目标值的结果if (path.size() k) return;//剪枝 剪去超过结果集个数的遍历//相当于for循环中的这个剪枝i 9 - (k - path.size()) 1; if (sum n path.size() k) {//符合条件就收集结果ans.add(new ArrayList(path));return;}for(int i startIndex; i 9; i) {path.add(i);sum i;build(k, n, i 1, sum);//递归sum - i;//回溯path.removeLast();//回溯}}
} 时间复杂度:O(n * 2^n))循环n个元素2^n表示所有可能的子集数量 空间复杂度:O(n);递归栈的深度最多为 n Leetcode 17.电话号码的字母组合
题目链接:17.电话号码的字母组合
大佬视频讲解电话号码的字母组合视频讲解 个人思路
虽然题目也类似于组合但最多可以有4重循环思路打结... 解法
回溯法
把组合问题抽象为如下树形结构 如上图可以看出遍历的深度就是输入23的长度而叶子节点就是要收集的结果。 回溯法三部曲
1.确定回溯函数参数 首先需要一个字符串s来收集叶子节点的结果然后用一个字符串数组result保存起来, 参数指定是有题目中给的string digits然后还要有一个参数就是int型的index。 这个index是记录遍历第几个数字就是用来遍历digits的题目中给出数字字符串同时index也表示树的深度。 2.确定终止条件 终止条件就是index 等于 输入的数字个数digits.size,然后收集结果结束本层递归。 3.确定单层遍历逻辑 首先要取index指向的数字并找到对应的字符集手机键盘的字符集。 然后for循环来处理这个字符集,注意本题每一个数字代表的是不同集合也就是求不同集合之间的组合还有需要注意输入1 * #按键等等异常情况 关于剪枝这道题没有其他条件是在求取不同集合之间的组合所以没有可以剪枝的地方。
class Solution {ListString list new ArrayList();//结果列表public ListString letterCombinations(String digits) {if (digits null || digits.length() 0) {return list;}//初始对应所有的数字为了直接对应2-9新增了两个无效的字符串String[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};backTracking(digits, numString, 0);return list;}//每次递归获取一个字符串所以会涉及大量的字符串拼接因此选择更为高效的 StringBuildStringBuilder temp new StringBuilder();public void backTracking(String digits, String[] numString, int num) {//遍历全部,记录一次得到的字符串if (num digits.length()) {//终止条件list.add(temp.toString());return;}//str 表示当前num对应的字符串//比如digits如果为23,num 为0则str表示2对应的 abcString str numString[digits.charAt(num) - 0];for (int i 0; i str.length(); i) {temp.append(str.charAt(i));backTracking(digits, numString, num 1);temp.deleteCharAt(temp.length() - 1);//回溯剔除末尾的元素继续尝试}}
} 时间复杂度:O(3^m * 4^n)粗略估算其中 m 是对应四个字母的数字个数n 是对应三个字母的数字个数 空间复杂度:O(3^m * 4^n);(需要暂存结果大小) 以上是个人的思考反思与总结若只想根据系列题刷参考卡哥的网址代码随想录算法官网
