鲜花商城网站模板,高端大气,wordpress 主题 博客,苏州网站开发公司文章目录LeetCode 216.组合总和题目链接#x1f517;思路LeetCode 17.电话号码的字母组合题目链接#x1f517;思路LeetCode 216.组合总和
题目链接#x1f517;
LeetCode 216.组合总和
思路
本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。
相对于7…
文章目录LeetCode 216.组合总和题目链接思路LeetCode 17.电话号码的字母组合题目链接思路LeetCode 216.组合总和
题目链接
LeetCode 216.组合总和
思路
本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。
相对于77. 组合 (opens new window)无非就是多了一个限制本题是要找到和为n的k个数的组合而整个集合已经是固定的了[1,…,9]。
想到这一点了做过77. 组合之后本题是简单一些了。
本题k相当于树的深度9因为整个集合就是9个数就是树的宽度。
例如 k 2n 4的话就是在集合[1,2,3,4,5,6,7,8,9]中求 k个数 2, n和 4的组合。
选取过程如图 回溯三部曲 确定递归函数参数 需要一维数组path来存放符合条件的结果二维数组result来存放结果集。 这里我依然定义path 和 result为全局变量。 ListListInteger result new ArrayList();
LinkedListInteger path new LinkedList();接下来还需要如下参数 targetSumint目标和也就是题目中的n。kint就是题目中要求k个数的集合。sumint为已经收集的元素的总和也就是path里元素的总和。startIndexint为下一层for循环搜索的起始位置。 所以代码如下 ListListInteger result new ArrayList();
LinkedListInteger path new LinkedList();
void backTracking(int targetSum, int k, int startIndex, int sum)还要强调一下回溯法中递归函数参数很难一次性确定下来一般先写逻辑需要啥参数了填什么参数。 确定终止条件 k其实就已经限制树的深度因为就取k个元素树再往下深了没有意义。 所以如果path.size() 和 k相等了就终止。 如果此时path里收集到的元素和sum 和targetSum就是题目描述的n相同了就用result收集当前的结果。 所以 终止代码如下 if (path.size() k) {if (sum targetSum) result.add(new ArrayList(path));return;}单层搜索过程 本题和77. 组合 区别之一就是集合固定的就是9个数[1,…,9]所以for循环固定i9 如图 处理过程就是 path收集每次选取的元素相当于树型结构里的边sum来统计path里元素的总和。 代码如下 for (int i startIndex; i 9; i) {path.add(i);sum i;backTracking(targetSum, k, i 1, sum);//回溯path.removeLast();//回溯sum - i;}别忘了处理过程 和 回溯过程是一一对应的处理有加回溯就要有减
剪枝
这道题目剪枝操作其实是很容易想到了想必大家看上面的树形图的时候已经想到了。
如图 已选元素总和如果已经大于n图中数值为4了那么往后遍历就没有意义了直接剪掉。
和回溯算法组合问题再剪剪枝 (opens new window)一样for循环的范围也可以剪枝i 9 - (k - path.size()) 1就可以了。
最后完整的代码
class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combinationSum3(int k, int n) {backTracking(n, k, 1, 0);return result;}private void backTracking(int targetSum, int k, int startIndex, int sum) {// 减枝if (sum targetSum) {return;}if (path.size() k) {if (sum targetSum) result.add(new ArrayList(path));return;}// 减枝 9 - (k - path.size()) 1for (int i startIndex; i 9 - (k - path.size()) 1; i) {path.add(i);sum i;backTracking(targetSum, k, i 1, sum);//回溯path.removeLast();//回溯sum - i;}}
}LeetCode 17.电话号码的字母组合
题目链接
LeetCode 17.电话号码的字母组合
思路
要解决如下三个问题
数字和字母如何映射两个字母就两个for循环三个字符我就三个for循环以此类推然后发现代码根本写不出来输入1 * #按键等等异常情况
数字和字母如何映射
可以使用map或者定义一个数组来做映射我这里定义一个二维数组代码如下
String[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};回溯法来解决n个for循环的问题
例如输入“23”抽象为树形结构如图所示 图中可以看出遍历的深度就是输入23的长度而叶子节点就是我们要收集的结果输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。
回溯三部曲 确定回溯函数参数 首先需要一个字符串s来收集叶子节点的结果然后用一个字符串数组result保存起来这个变量我依然定义为全局。 再来看参数参数指定是有题目中给的string digits然后还要有一个参数就是int型的num。 这个num是记录遍历第几个数字了就是用来遍历digits的题目中给出数字字符串同时num也表示树的深度。 代码如下 ListString list new ArrayList();
void backTracking(String digits, String[] numString, int num)确定终止条件 每次迭代获取一个字符串所以会设计大量的字符串拼接所以这里选择更为高效的 StringBuild StringBuilder temp new StringBuilder();例如输入用例23两个数字那么根节点往下递归两层就可以了叶子节点就是要收集的结果集。 那么终止条件就是如果num 等于 输入的数字个数digits.length了本来num就是用来遍历digits的。 然后收集结果结束本层递归。 代码如下 if (num digits.length()) {list.add(temp.toString());return;}确定单层遍历逻辑 首先要取num指向的数字并找到对应的字符集手机键盘的字符集。 然后for循环来处理这个字符集代码如下 String str numString[digits.charAt(num) - 0];for (int i 0; i str.length(); i) {temp.append(str.charAt(i));//cbackTracking(digits, numString, num 1);//剔除末尾的继续尝试temp.deleteCharAt(temp.length() - 1);}注意这里for循环可不像是在回溯算法求组合问题 (opens new window)和回溯算法求组合总和 (opens new window)中从startIndex开始遍历的。 因为本题每一个数字代表的是不同集合也就是求不同集合之间的组合而77. 组合 (opens new window)和216.组合总和III (opens new window)都是求同一个集合中的组合
完整代码
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();//比如digits如果为23,num 为0则str表示2对应的 abcpublic void backTracking(String digits, String[] numString, int num) {//遍历全部一次记录一次得到的字符串if (num digits.length()) {list.add(temp.toString());return;}//str 表示当前num对应的字符串String str numString[digits.charAt(num) - 0];for (int i 0; i str.length(); i) {temp.append(str.charAt(i));//cbackTracking(digits, numString, num 1);//剔除末尾的继续尝试temp.deleteCharAt(temp.length() - 1);}}
}
