代码随想录第22天|回溯算法

77.组合

            

题目链接/文章解说：代码随想录

   

视频解说：带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili

   

剪枝操纵：带你学透回溯算法-组合问题的剪枝操纵（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili

        代码随想录

回溯基本思路:

 剪枝思路：
以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们须要的元素个数了，那么就没有须要搜刮了。

1. for (int i = startIndex; i <= n; i++) {

复制代码

接下来看一下优化过程如下：

• 已经选择的元素个数：path.size();
  
• 还须要的元素个数为: k - path.size();
  
• 在聚集n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
  

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的聚集。
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜刮都是公道的，可以是组合[2, 3, 4]。
这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。
所以优化之后的for循环是：

1. for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

复制代码

 代码：

 

1. class Solution {
2.     List<List<Integer>> results = new ArrayList<>();
3.     List<Integer> path = new ArrayList<>();
4.     public List<List<Integer>> combine(int n, int k) {
5.         getPath(n,k,1);
6.         return results;
7.     }
8.     public void getPath(int n,int k, int startIndex){
9.         if(path.size()==k){
10.             results.add(new ArrayList<>(path));
11.             return;
12.         }
13.         for(int i = startIndex;i<=n-(k-path.size())+1;i++){
14.             path.add(i);
15.             getPath(n,k,i+1);
16.             path.remove(path.size()-1);
17.         }
18.     }
19. }

复制代码

216.组合问题III

      题目链接/文章解说：   代码随想录           

视频解说：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III_哔哩哔哩_bilibili

       代码随想录：

已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。
那么剪枝的地方可以放在递归函数开始的地方，剪枝代码如下：

1. if (sum > targetSum) { // 剪枝操作
2.     return;
3. }

复制代码

代码：

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

复制代码

17.电话号码的字母组合

            

题目链接/文章解说：代码随想录

   

视频解说：还得用回溯算法！| LeetCode：17.电话号码的字母组合_哔哩哔哩_bilibili

       代码随想录：

 关于字符串为空时：
我的做法是在主函数直接判断字符串为空，那么就返回空结果，不消再进入回溯函数。和示例代码相似：

1. if (digits == null || digits.length() == 0) {
2.      return list;
3. }

复制代码

 存储字母编号的数据布局：

1. //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
2. String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

复制代码

我选用的是map是比力恐惊和字符串打交道，但是选用数组与index下标对应更为简洁。 
代码

1. class Solution {
2.     List<String> results = new ArrayList<>();
3.     StringBuilder path = new StringBuilder();
4.     Map map = new HashMap();
5.     public List<String> letterCombinations(String digits) {
6.         map.put('2', new char[]{'a', 'b', 'c'});
7.         map.put('3', new char[]{'d', 'e', 'f'});
8.         map.put('4', new char[]{'g', 'h', 'i'});
9.         map.put('5', new char[]{'j', 'k', 'l'});
10.         map.put('6', new char[]{'m', 'n', 'o'});
11.         map.put('7', new char[]{'p', 'q', 'r','s'});
12.         map.put('8', new char[]{'t', 'u', 'v'});
13.         map.put('9', new char[]{'w', 'x', 'y','z'});
14.         char[] charArray = digits.toCharArray();
15.         if(charArray.length==0){
16.             return results;
17.         }
18.         getPhoneCombination(charArray,0);
19.         return results;
20.     }
21.     public void getPhoneCombination(char[] digits,int index){
22.         if(path.length()==digits.length) {
23.             results.add(path.toString());
24.             return;
25.         }
26.         char digit = digits[index];
27.         char[] item = (char[]) map.get(digit);
28.         for(int i = 0;i<item.length;i++){
29.             path.append(item[i]);
30.             getPhoneCombination(digits,index+1);
31.             path.deleteCharAt(path.length()-1);
32.         }
33.     }
34. }

复制代码

 


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