代码随想录算法训练营Day22|77、组合216、组合综合17、电话号码的字母组合 ...

77、组合

        回溯三部曲：1、确定函数头 2、确定停止条件 3、确定单层逻辑（for循环横向遍历，遍历的时候把递归看成一个黑盒）
        for循环控制的是当前层的逐个元素遍历，递归层的i+1控制的是下一层从这个元素的下一个开始取，如果可以取重复元素的话，下一层依旧从i开始就可以。但是一定不能再取到i-1或更前面的元素了，由于在取i-1的时候就已经把含有i-1的所有环境（包括可以重复和不可以重复的环境）都取过了。

1. class Solution {
2.     List<List<Integer>> res = new ArrayList<>();
3.     List<Integer> path = new LinkedList<>();
4.     public List<List<Integer>> combine(int n, int k) {
5.         backingTrace(n,k,1);
6.         return res;
7.     }
9.     public void backingTrace(int n, int k, int startIndex){
10.         if(path.size() == k){
11.             res.add(new ArrayList<>(path));
12.             return;
13.         }
15.         for(int i = startIndex; i <=n; i++){
16.             path.add(i);
17.             backingTrace(n, k, i + 1);
18.             path.removeLast();
19.         }
20.         
21.     }
22. }

复制代码

216、组合总和

        思绪和上一题差不多，注意sum如果已经大于目标值，没须要再组合下去了，我们组合出来的和都是递增的。

1. class Solution {
2.     List<List<Integer>> res = new ArrayList<>();
3.     List<Integer> path = new LinkedList<>();
4.     public List<List<Integer>> combinationSum3(int k, int n) {
5.         backingTrace(k,n,1, 0);
6.         return res;
7.     }
9.     private void backingTrace(int k, int n, int startIndex,int sum){
10.         if(sum > n){
11.             return;
12.         }
13.         if(path.size() == k){
14.             if(sum == n){
15.                 res.add(new ArrayList<>(path));
16.             }
17.             return;
18.         }
20.         for(int i = startIndex; i <=9 ; i++){
21.             path.add(i);
22.             backingTrace(k,n,i + 1,sum +i);
23.             path.removeLast();
24.         }
25.     }
26. }

复制代码

 17、电话号码的字母组合

         积累下StringBuilder的几个方法，添加元素append，删除元素deleteCharAt（index）

1. class Solution {
3. String[] numbers = {
4.     "",
5.     "",
6.     "abc",
7.     "def",
8.     "ghi",
9.     "jkl",
10.     "mno",
11.     "pqrs",
12.     "tuv",
13.     "wxyz"
14. };
15.     List<String> res = new ArrayList<>();
16.     StringBuilder sb = new StringBuilder();
18.     public List<String> letterCombinations(String digits) {
19.         if(digits == null || digits.length() == 0) return res;
20.         int[] digitsArr = new int[digits.length()];
21.         for(int i = 0; i < digitsArr.length; i++){
22.             int temp = digits.charAt(i) - '0';
23.             digitsArr[i] = temp;
24.             System.out.println(temp);
25.         }
27.         backingTrace(digitsArr,0);
28.         return res;
29.     }
31.     private void backingTrace(int[] digits,int index){
32.         if(index == digits.length){
33.             res.add(sb.toString());
34.             return;
35.         }
36.         //电话号码的第index位
37.         int inNum = digits[index];
38.         for(int i = 0; i < numbers[inNum].length(); i++)
39.         {
40.             char  cur = numbers[inNum].charAt(i);
41.             sb.append(cur);
42.             backingTrace(digits,index + 1);
43.             sb.deleteCharAt(sb.length() - 1);
45.         }
46.     }
47. }
49. //二刷
51. class Solution {
53.         String[] numbers = {
54.                         "",
55.                         "",
56.                         "abc",
57.                         "def",
58.                         "ghi",
59.                         "jkl",
60.                         "mno",
61.                         "pqrs",
62.                         "tuv",
63.                         "wxyz"
64.         };
65.         List<String> res = new ArrayList<>();
66.         StringBuilder sb = new StringBuilder();
68.         public List<String> letterCombinations(String digits) {
69.                 int n = digits.length();
70.         if(n == 0) return res;
71.                 int[] nums = new int[digits.length()];
72.                 for(int i = 0; i < digits.length();i++){
73.                         nums[i] = (int)(digits.charAt(i) -'0');
74.                         System.out.println(nums[i]);
75.                 }
76.                 backingTrace(n,nums);
78.                 return res;
79.         }
81.         private void backingTrace(int n, int[] nums){
82.                 if(sb.length() == n){
83.                         res.add(new String(sb));
84.                         return;
85.                 }
86.         //当前遍历到电话号码的位置索引
87.                 int location = sb.length();
88.         //当前遍历到的电话号码数字
89.                 int locationNum = nums[location];
90.         //遍历数字按键对应的3-4个字母
91.                 for(int i = 0; i < numbers[locationNum].length(); i++){
92.                         //添加字母
93.             sb.append(numbers[locationNum].charAt(i));
94.                         backingTrace(n,nums);
95.                         sb.deleteCharAt(sb.length() - 1);
96.                 }
98.         }
100. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。