devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

代码随想录算法训练营第二十七天| 39. 组合总和，40.组合总和II，131.分割回文串

作者：很楠不爱3 | 2024-05-17 05:08:16

赞

踩

代码随想录算法训练营第二十七天| 39. 组合总和，40.组合总和II，131.分割回文串

 题目与题解

39. 组合总和

题目链接：39. 组合总和

代码随想录题解：39. 组合总和

视频讲解：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！_哔哩哔哩_bilibili

解题思路：

        组合总和这一类题的基本思路是一样的，这道题是在组合总和III这题的基础上，增加了一个元素可重复选取的需求，实际上正如提示所说，只要修改startIndex的入参即可。

        同样还是用回溯法做，三部曲如下：

        参数有返回的结果result，中间记录结果的变量list，用于计算当前数字之和的变量sum，递归函数的入参是输入的数组candidates，目标和target，以及每一次递归的起始值startIndex；

        终止条件仍然为sum等于target，将list插入result，并返回；

        单层遍历条件也是类似的，不同的地方在于startIndex不是i+1，而是i（因为当前元素可以重复选取）。

        考虑到输入数组的元素都是正数，所以当sum>target时，可以剪枝返回。

  1. class Solution {
  2. 	List<List<Integer>> result = new ArrayList<>();
  3. 	LinkedList<Integer> list = new LinkedList<>();
  4. 	int sum;
  5.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  6.  		combinationSum(candidates, target, 0);
  7. 		 return result;
  8.     }
  9.  
  10. 	public void combinationSum(int[] candidates, int target, int startIndex) {
  11. 		if (sum > target) return;
  12. 		if (sum == target) {
  13. 			result.add(new ArrayList<>(list));
  14. 			return;
  15. 		}
  16. 		for (int i = startIndex; i < candidates.length; i++) {
  17. 			sum += candidates[i];
  18. 			list.add(candidates[i]);
  19. 			combinationSum(candidates, target, i);
  20. 			list.pollLast();
  21. 			sum -= candidates[i];
  22. 		}
  23. 	}
  24. }

看完代码随想录之后的想法 

        有些可以优化的细节：

        sum参数可以不需要，递归时每次入参用target-candidates代替target即可，如果某次递归时target直接为0，说明当前list已经符合要求，可以直接返回。

        剪枝可以再优化：如果先对数组进行排序，取值就会从小到大取得，这样一旦前面某个序列已经大于target了，同一层后面的序列就不用再计算了。

  1. // 剪枝优化
  2. class Solution {
  3.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  4.         List<List<Integer>> res = new ArrayList<>();
  5.         Arrays.sort(candidates); // 先进行排序
  6.         backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
  7.         return res;
  8.     }
  9.  
  10.     public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
  11.         // 找到了数字和为 target 的组合
  12.         if (sum == target) {
  13.             res.add(new ArrayList<>(path));
  14.             return;
  15.         }
  16.  
  17.         for (int i = idx; i < candidates.length; i++) {
  18.             // 如果 sum + candidates[i] > target 就终止遍历
  19.             if (sum + candidates[i] > target) break;
  20.             path.add(candidates[i]);
  21.             backtracking(res, path, candidates, target, sum + candidates[i], i);
  22.             path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
  23.         }
  24.     }
  25. }

遇到的困难

        无

40.组合总和II

题目链接：​​​​​​​40.组合总和II

代码随想录题解：​​​​​​​40.组合总和II

视频讲解：回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II_哔哩哔哩_bilibili

解题思路：

        总体套路仍旧和之前做过的组合总和题目类似，不同的地方在于，candidates中的元素会有重复，但每个元素不可以重复选取，所以做的时候需要去重。

        入参，终止条件和剪枝条件不作赘述，关键在于单层遍历的逻辑。因为考虑到有重复元素，首先在candidates入参之前要进行排序，这样方便后序遇到重复元素的时候跳过处理。跳过的条件为：如果当前元素不是startIndex，且它和它的前一个元素相同，就直接跳过本次循环。

  1. class Solution {
  2. 	List<List<Integer>> result = new ArrayList<>();
  3. 	LinkedList<Integer> list = new LinkedList<>();
  4. 	int sum = 0;
  5.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  6. 		Arrays.sort(candidates);
  7. 		combinationSum2(candidates, target, 0);
  8.     	return result;
  9. 	}
  10.  
  11. 	public void combinationSum2(int[] candidates, int target, int startIndex) {
  12. 		if (sum > target) return;
  13. 		if (sum == target) {
  14. 			result.add(new ArrayList<>(list));
  15. 		}
  16. 		for (int i = startIndex; i < candidates.length; i++) {
  17. 			if (i > startIndex && candidates[i] == candidates[i-1]) continue;
  18. 			sum += candidates[i];
  19. 			list.add(candidates[i]);
  20. 			combinationSum2(candidates, target, i + 1);
  21. 			list.pollLast();
  22. 			sum -= candidates[i];
  23. 		}
  24. 	}
  25. }

看完代码随想录之后的想法 

        都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？

        回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

        随想录这里讲的非常清楚，用一个标记去重数组或者startIndex去重都可以，剪枝也是跟前一题相同。这里学习一下用标记去重数组。

  1. class Solution {
  2.   LinkedList<Integer> path = new LinkedList<>();
  3.   List<List<Integer>> ans = new ArrayList<>();
  4.   boolean[] used;
  5.   int sum = 0;
  6.  
  7.   public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  8.     used = new boolean[candidates.length];
  9.     // 加标志数组，用来辅助判断同层节点是否已经遍历
  10.     Arrays.fill(used, false);
  11.     // 为了将重复的数字都放到一起，所以先进行排序
  12.     Arrays.sort(candidates);
  13.     backTracking(candidates, target, 0);
  14.     return ans;
  15.   }
  16.  
  17.   private void backTracking(int[] candidates, int target, int startIndex) {
  18.     if (sum == target) {
  19.       ans.add(new ArrayList(path));
  20.     }
  21.     for (int i = startIndex; i < candidates.length; i++) {
  22.       if (sum + candidates[i] > target) {
  23.         break;
  24.       }
  25.       // 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
  26.       if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
  27.         continue;
  28.       }
  29.       used[i] = true;
  30.       sum += candidates[i];
  31.       path.add(candidates[i]);
  32.       // 每个节点仅能选择一次，所以从下一位开始
  33.       backTracking(candidates, target, i + 1);
  34.       used[i] = false;
  35.       sum -= candidates[i];
  36.       path.removeLast();
  37.     }
  38.   }
  39. }

遇到的困难

        去重方法一开始不好想，本来想用hashset试图去重，但是不确定顺序不同但元素相同的中间list在hashset算不算同一种序列，所以最后还是根据测试用例的结果似乎是排过序的，想到可以排序后比较前后元素去重。

131.分割回文串

题目链接：131.分割回文串

代码随想录题解：​​​​​​​131.分割回文串

视频讲解：带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！_哔哩哔哩_bilibili

解题思路：

       关键点在于分割线如何划分，划分后后续的字符串又可以通过回溯函数递归的再次划分。但是不知道怎么写就直接看答案了。

看完代码随想录之后的想法 

        

        这里同样需要取startindex作为每次递归的起点，以及一个判断是否是回文的函数

递归函数参数：全局变量数组path存放切割后回文的子串，二维数组result存放结果集，以及输入参数s和startIndex。

终止条件：在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。

单层搜索逻辑：不断取startIndex到i之间的字符串，如果取到回文，就用剩下的字符串调用回溯函数，否则continue。

  1. class Solution {
  2.     List<List<String>> lists = new ArrayList<>();
  3.     Deque<String> deque = new LinkedList<>();
  4.  
  5.     public List<List<String>> partition(String s) {
  6.         backTracking(s, 0);
  7.         return lists;
  8.     }
  9.  
  10.     private void backTracking(String s, int startIndex) {
  11.         //如果起始位置大于s的大小，说明找到了一组分割方案
  12.         if (startIndex >= s.length()) {
  13.             lists.add(new ArrayList(deque));
  14.             return;
  15.         }
  16.         for (int i = startIndex; i < s.length(); i++) {
  17.             //如果是回文子串，则记录
  18.             if (isPalindrome(s, startIndex, i)) {
  19.                 String str = s.substring(startIndex, i + 1);
  20.                 deque.addLast(str);
  21.             } else {
  22.                 continue;
  23.             }
  24.             //起始位置后移，保证不重复
  25.             backTracking(s, i + 1);
  26.             deque.removeLast();
  27.         }
  28.     }
  29.     //判断是否是回文串
  30.     private boolean isPalindrome(String s, int startIndex, int end) {
  31.         for (int i = startIndex, j = end; i < j; i++, j--) {
  32.             if (s.charAt(i) != s.charAt(j)) {
  33.                 return false;
  34.             }
  35.         }
  36.         return true;
  37.     }
  38. }

还有判断回文有剪枝方法，后面再补 

遇到的困难

        思路不是很清晰，无从下手

今日收获

        基本回溯套路掌握，但稍微变化一点就不太会做，还是没有掌握回溯的真正技巧，需要练习。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/582081
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号