天台城乡规划建设局网站,行业网站设计,给网站app做后台的公司,网站建设项目推文一、电话号码的字母组合题目链接思路#xff1a;回溯三部曲。确定回溯函数参数#xff1a;题目中给的 digits#xff0c;还要有一个参数就是int型的index#xff08;记录遍历第几个数字#xff0c;就是用来遍历digits的#xff0c;同时也代表了递归的深度#xff09;回溯三部曲。确定回溯函数参数题目中给的 digits还要有一个参数就是int型的index记录遍历第几个数字就是用来遍历digits的同时也代表了递归的深度第三个参数numString(数字和字母映射)。确定终止条件如果index 等于 输入的数字个数digits.size了就return。确定单层遍历逻辑首先要取index指向的数字并找到对应的字符集然后for循环来处理这个字符集注意1解决三个问题数字和字母如何映射 使用map或者定义一个二维数组两个字母就两个for循环三个字符我就三个for循环以此类推然后发现代码根本写不出来输入1 * #按键等等异常情况2区别于普通的组合问题本题是多个集合求组合因为本题每一个数字代表的是不同集合也就是求不同集合之间的组合。3全局变量一个字符串sb来收集叶子节点的结果一个字符串数组result保存sb。解法class Solution {// 最终结果字符数组和单次符合条件结果ListString res new ArrayList();StringBuffer sb new StringBuffer();public ListString letterCombinations(String digits) {if (digits.length() 0 || digits null)return res;String[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};backTracking(digits, numString, 0);return res;}public void backTracking(String digits, String[] numString ,int num) {if (num digits.length()){res.add(sb.toString());return;}// digits.charAt(num)能够获取到当前的号码数字2-9String t numString[digits.charAt(num) - 0];for (int i 0; i t.length(); i) {sb.append(t.charAt(i));backTracking(digits, numString, num 1);sb.deleteCharAt(sb.length() - 1); //回溯}}
}二、组合总和题目链接思路基本与组合总和III类似。区别有组合没有数量要求元素可无限重复选取注意如果是一个集合来求组合的话就需要startIndex否则会出现重复情况如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex。解法未剪枝ListListInteger res new ArrayList();
LinkedListInteger path new LinkedList();
public ListListInteger combinationSum(int[] candidates, int target) {// sum, startIndex是开始位置也是candidates的索引back(candidates, target, 0,0);return res;
}private void back(int[] candidates, int target, int sum, int startIndex) {if (sum target){res.add(new ArrayList(path));return;}if (sum target)return;for (int i startIndex; i candidates.length; i){path.add(candidates[i]);sum candidates[i];back(candidates, target, sum, i);sum - candidates[i];path.removeLast();}
}剪枝优化1.对总集合排序之后如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历。解法class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combinationSum(int[] candidates, int target) {Arrays.sort(candidates); // 先进行排序back(candidates, target, 0, 0);return res;}private void back(int[] candidates, int target, int sum, int startIndex) {if (sum target){res.add(new ArrayList(path));return;}if (sum target)return;// 多一步判断for (int i startIndex; i candidates.length sum candidates[i] target; i){path.add(candidates[i]);sum candidates[i];back(candidates, target, sum, i);sum - candidates[i];path.removeLast();}}
}三、组合总和II题目链接思路与组合总和类似但区别于本题candidates 中的每个数字在每个组合中只能使用一次。本题数组candidates的元素是有重复的而39.组合总和 (opens new window)是无重复元素的数组candidates。也就是说组合里的元素可能有重复且只使用一次但组合之间不能重复。本题的难点在于区别2中集合数组candidates有重复元素但还不能有重复的组合。去重也去的是同一个树层上重复的值。代码里就是判断i startIndex candidates[i] candidates[i - 1]直接continue解法class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates); // 先进行排序back(candidates, target, 0, 0);return res;}private void back(int[] candidates, int target, int sum, int startIndex) {if (sum target){res.add(new ArrayList(path));return;}if (sum target)return;for (int i startIndex; i candidates.length sum candidates[i] target; i){// 碰到同一树层重复元素 直接continueif ( i startIndex candidates[i] candidates[i - 1] ) {continue;}path.add(candidates[i]);sum candidates[i];back(candidates, target, sum, i 1);sum - candidates[i];path.removeLast();}}
}
