seo网站推广有哪些,wordpress lms插件,做vi的设计公司,东莞网站设计排行榜#LeetCode 216. Combination III #LeetCode 216. 视频讲解#xff1a;和组合问题有啥区别#xff1f;回溯算法如何剪枝#xff1f;| LeetCode#xff1a;216.组合总和III_哔哩哔哩_bilibili 如果做了77 题后#xff0c;这个题目可以用相似的思路。回溯三部曲#xff1a; …#LeetCode 216. Combination III #LeetCode 216. 视频讲解和组合问题有啥区别回溯算法如何剪枝| LeetCode216.组合总和III_哔哩哔哩_bilibili 如果做了77 题后这个题目可以用相似的思路。回溯三部曲
1. 确定递归函数的参数以及返回值一维数组path来存放符合条件的结果二维数组result来存放结果集。
2. 确定终止条件path 的长度等于目标长度k 。
3. 确定单层递归逻辑path 收集每次选取的元素用sum来记录path 里元素的和。
代码
class Solution {LinkedList path new LinkedList();ListListInteger result new ArrayList();public ListListInteger combinationSum3(int k, int n) {backtracking(k, n, 1, 0);return result;}public void backtracking(int k, int n, int startIndex, int sum) {if (sum n) {return;}if (sum n) {if (path.size() k) {result.add(new LinkedList(path));}return;}for (int i startIndex; i 9 - (k - path.size()) 1; i) {path.add(i);sum i;backtracking(k, n, i 1, sum);sum - i;path.removeLast();}}
}
#LeetCode 17. Letter Combinations of a Phone Number #LeetCode 17. 视频讲解还得用回溯算法| LeetCode17.电话号码的字母组合_哔哩哔哩_bilibili 这个遇上一个题目index 的区别是上一个题目的index 是为了记录不同的起始位置来保证生成不同的结果这个题目是在两个字符串中操作所以i 都是在0 开始。
这个题目中的index 是记录遍历到digits 中的第几个数字了。终止条件就是如果index 等于输入的数字个数注意这里是length 不是length - 1 因为最后一个元素也会被操作。StringBuilder 在java 中有很多常用方法例如append(), deleteCharAt(), insert()等。
代码
class Solution {StringBuilder path new StringBuilder();ListString result new ArrayList();public ListString letterCombinations(String digits) {if (digits.length() 0 || digits null) {return result;}String[] letterMap {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};backtracking(digits, letterMap, 0);return result;}public void backtracking(String digits, String[] letterMap, int index) {if (digits.length() index) {result.add(path.toString());return;}int digit digits.charAt(index) - 0;String letter letterMap[digit];for (int i 0; i letter.length(); i) {path.append(letter.charAt(i));backtracking(digits, letterMap, index 1);path.deleteCharAt(path.length() - 1);}}
}
