企业网络营销案例,seo按天计费系统,铁道部建设监理协会网站查询,做网站发广告17.电话号码的字母组合
在套模板的基础上#xff0c;手动按位置放一个映射表#xff0c;每次独立处理字符#xff0c;还要对空字符串单独处理#xff08;因为默认生成了StringBuilder是空字符串而不是null#xff09;
此处for循环并不像之前从start开始遍历#xff0c;…17.电话号码的字母组合
在套模板的基础上手动按位置放一个映射表每次独立处理字符还要对空字符串单独处理因为默认生成了StringBuilder是空字符串而不是null
此处for循环并不像之前从start开始遍历因为本题每一个数字代表的是不同集合也就是求不同集合之间的组合而求组合问题是求同一个集合中的组合
class Solution {ListString res new ArrayList();StringBuilder path new StringBuilder();String[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};public ListString letterCombinations(String digits) {if (digits.length() 0) return res;backtrack(digits,0);return res;}void backtrack(String digits, int start) {if (start digits.length()) {res.add(path.toString());return;}String str numString[digits.charAt(start) - 0];for (int i 0; i str.length(); i) {path.append(str.charAt(i));backtrack(digits,start1);path.deleteCharAt(path.length()-1);}}
}
39. 组合总和
这种复杂算法可以先把给的数组排序方便剪枝
class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();int sum 0;public ListListInteger combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtrack(candidates, target, 0);return res;}void backtrack(int[] candidates, int target, int start) {if (sum target) {res.add(new ArrayList(path)); return;} for (int i start; i candidates.length; i) {if (sum candidates[i] target) break;path.add(candidates[i]);sum candidates[i];backtrack(candidates, target, i);path.removeLast();sum - candidates[i];}}
}
40.组合总和II
candidates有重复元素但还不能有重复的组合真的离谱加一个数组来标记
class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();boolean[] used;int sum 0;public ListListInteger combinationSum(int[] candidates, int target) {used new boolean[candidates.length];Arrays.fill(used, false);Arrays.sort(candidates);backtrack(candidates, target, 0);return res;}void backtrack(int[] candidates, int target, int start) {if (sum target) res.add(new ArrayList(path)); for (int i start; i candidates.length; i) {if (sum candidates[i] target) break;if (i 0 candidates[i] candidates[i - 1] !used[i - 1]) continue;used[i] true;path.add(candidates[i]);sum candidates[i];backtrack(candidates, target, i1);used[i] false;path.removeLast();sum - candidates[i];}}
}
