网站建设公司发展规划,网站开发设计文档,汽车网站建设分析报告,成都必去的地方排行榜学习目标#xff1a; 216.组合总和III 17.电话号码的字母组合 学习内容#xff1a;
216.组合总和III
题目链接 文章讲解 找出所有相加之和为 n 的 k 个数的组合#xff0c;且满足下列条件#xff1a;
只使用数字1到9每个数字 最多使用一次 返回所有可能的有效…学习目标 216.组合总和III 17.电话号码的字母组合 学习内容
216.组合总和III
题目链接 文章讲解 找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次 返回所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
class Solution {ListListInteger result new ArrayList();ListInteger path new ArrayList();public ListListInteger combinationSum3(int k, int n) {backtracking(n,k,0, 1);return result;}//1.递归函数参数以及返回值public void backtracking(int targetSum, int k, int sum, int startIndex){//2.剪枝操作sum targetSum 确定终止条件:path.size kif(sum targetSum) return;if(path.size() k){if(targetSum sum){result.add(new ArrayList(path));return;}}//3.单层处理逻辑//剪枝操作i 9 - (k - path.size()) 1for(int i startIndex; i 9 - (k - path.size()) 1; i){sum i;path.add(i);backtracking(targetSum, k, sum, i 1);sum - i;path.removeLast();}}
}17.电话号码的字母组合
题目链接文章讲解 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 class Solution {//存储最终结果ListString list new ArrayList();//存储每次迭代字符串StringBuilder str new StringBuilder();public ListString letterCombinations(String digits) {if (digits null || digits.length() 0) {return list;}//数字-字母映射String[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};backTracking(digits, numString, 0);return list;}//树形结构深度digits.length() 树形结构宽度letter.lengthpublic void backTracking(String digits, String[] numString, int index){if(index digits.length()){list.add(str.toString());return;}String letter numString[digits.charAt(index) - 0];for(int i 0; i letter.length(); i){str.append(letter.charAt(i));backTracking(digits, numString, index 1);str.deleteCharAt(str.length() - 1);}}
}
