网站建设备案条件,seo快速排名培训,wordpress新用户添加管理员权限,wordpress琪亚娜216. 组合总和 III
题目链接
题目描述#xff1a; 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数#xff0c;并且每种组合中不存在重复的数字。
说明#xff1a;
所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k 3, n 7 输…216. 组合总和 III
题目链接
题目描述 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数并且每种组合中不存在重复的数字。
说明
所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k 3, n 7 输出: [[1,2,4]]
示例 2: 输入: k 3, n 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
难点
思路
递归进入下一层时传入剩余需要的总和数总和数为0减去已被添加元素值和元素个数为k均满足添加至结果集剪枝当前所需总和小于零 或 结果集元素个数大于k 直接返回
class Solution {ListListInteger result new ArrayList();ListInteger path new ArrayList();int curSum;public ListListInteger combinationSum3(int k, int n) {backtracking(n, k, 1);return result;}public void backtracking(int n, int k, int startIdx) {if (n 0 || path.size() k) return; // 当前所需总和小于零 或 结果集元素个数大于kif (path.size() k n 0) { // 总和数和元素个数均满足result.add(new ArrayList(path));return;}for (int i startIdx; i 9; i) {path.add(i);curSum i;backtracking(n-i, k, i1); // 传入剩余需要的总和数path.remove(path.size()-1);curSum - i;}}
}时长 15min
收获 17. 电话号码的字母组合
题目链接
题目描述 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
示例:
输入“23”输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]. 说明尽管上面的答案是按字典序排列的但是你可以任意选择答案输出的顺序。
难点 多层for循环不可取。。。。 这题有难度的。。。
思路
class Solution {ListString result new ArrayList();//每次迭代获取一个字符串所以会设计大量的字符串拼接所以这里选择更为高效的 StringBuilderStringBuilder path new StringBuilder();public ListString letterCombinations(String digits) {if (digits null || digits.length() 0) return result;//因为数据规模不大采用数组结构存储映射关系。//初始对应所有的数字为了直接对应2-9新增了两个无效的字符串String[] numStrs {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};backtracking(digits, numStrs, 0);return result;}public void backtracking(String digits, String[] numStrs, int num) {//num代表递归层数也代表拼接的字符数量if (num digits.length()) {result.add(path.toString());return;}//str 表示当前num对应的字符串String str numStrs[digits.charAt(num)-0];for (int i 0; i str.length(); i) {path.append(str.charAt(i));backtracking(digits, numStrs, num1);path.deleteCharAt(path.length()-1);}}
}时长 30min
收获 递归参数传递不要用num这种啊啊啊啊num是自增的不对不对
