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

代码随想录day25｜216.组合总和III｜17.电话号码的字母组合｜Golang_go 组合总和iii

作者：Monodyee | 2024-04-11 10:36:35

赞

踩

go 组合总和iii

代码随想录day25

好

目录

216.组合总和III

17.电话号码的字母组合

216.组合总和III

        找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9

每个数字 最多使用一次

输入: k = 3, n = 7

输出: [[1,2,4]]

解释: 1 + 2 + 4 = 7 没有其他符合的组合了。

        本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。本题宽相当于1、2、3、4、5、6、7、8、9。 深度相当于k

        找出在宽度内深度为k且之和等于n的组合。

例如 k = 2，n = 4的话，就是在集合[1,2,3,4,5,6,7,8,9] 中求 个数(k) = 2,   和(n)= 4的组合。

图中，可以看出，只有最后取到集合（1，3）和为4 符合条件。

回溯三部曲来咯

1、确定递归参数：

  1. /*  
  2. 1、确定递归函数参数
  3. targetSum也就是题目要求的n
  4. k也就是题目要求的k个数的集合
  5. path_sum 也就是path上存放的元素的和
  6. startindex为下一层for循环搜索的起始位置
  7. */
  8. var path []int
  9. var result [][]int
  10. func backtrack(target, k, path_sum, startindex int){
  11. }
  12. //还要强调一下，回溯法中递归函数参数很难一次性确定下来，一般先写逻辑，需要啥参数了，填什么参数。

2、确定终止条件：

  1. /*
  2. 2、确定终止条件
  3. 终止条件就是len(path) == k，因为再往下没意义的。
  4. 如果此时path里面收集到的元素和path_sum == targetSum了（题目要求的n），那么就把path放进result里面。
  5. */
  6. if len(path) == k {
  7.   if path_sum == targetSum {
  8.     tmp := make([]int,k)
  9.     copy(tmp, path)
  10.     result = append(result, tmp)
  11.     return
  12.   }
  13. }

3、单层搜索过程：

  1. /*
  2. 3、单层搜索过程
  3. 本题和77组合的区别之一就是集合固定为9个数字[1,2,3,4,5,6,7,8,9]，所以for循环<=9。
  4. 处理过程就是path收集选取的元素，相当于树形结构的边，path_sum用来统计path里面的元素之和。
  5. */
  6. for i:=startindex;i<=9;i++{
  7.   path = append(path,i)
  8.   path_sum += i 
  9.   backtrack(targetSum, k, path_sum, i+1)
  10.   path_sum -=i  //记得回溯撤销
  11.   path = path[:len(path)-1] //记得回溯撤销
  12. }
  13. ​
  14. //别忘了处理过程 和 回溯过程是一一对应的，处理有加，回溯就要有减！

不难写出如下Go代码：

  1. //总的代码，未剪枝前
  2. var path []int
  3. var result [][]int
  4. func combinationSum3(k int, n int) [][]int {
  5.     result = [][]int{}
  6.     backtrack(n,k,0, 1)
  7.     return result
  8. }
  9. func backtrack(target_sum, k, path_sum, startIndex int) {
  10.     if len(path) == k {
  11.         if path_sum == target_sum {
  12.             temp := make([]int, k)
  13.             copy(temp, path)
  14.             result = append(result, temp)
  15.             return 
  16.         }
  17.     }
  18.     for i:=startIndex;i<=9;i++{
  19.         path = append(path, i)
  20.         path_sum += i 
  21.         backtrack(target_sum, k, path_sum,i+1)
  22.         path_sum -= i
  23.         path = path[:len(path)-1]
  24.     }
  25. }
  26.     // targetSum：目标和，也就是题目中的n。
  27.     // k：题目中要求k个数的集合。
  28.     // sum：已经收集的元素的总和，也就是path里元素的总和。
  29.     // startIndex：下一层for循环搜索的起始位置。

剪枝

        这道题目，剪枝操作其实是很容易想到了，想必大家看上面的树形图的时候已经想到了。

如图：

         已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。

那么剪枝的地方一定是在递归终止的地方剪，剪枝代码如下：

  1. if path_sum > targetSum { 
  2.     return 
  3. }

和回溯算法：组合问题再剪剪枝

一样，for循环的范围也可以剪枝，i <= 9 - (k - path.size()) + 1就可以了。

最后Go代码如下：

 

 

  

  1. //总的代码
  2. //总的代码
  3. var path []int
  4. var result [][]int
  5. func combinationSum3(k int, n int) [][]int {
  6.     result = [][]int{}
  7.     backtrack(n,k,0, 1)
  8.     return result
  9. }
  10. func backtrack(target_sum, k, path_sum, startIndex int) {
  11.     if path_sum > target_sum {
  12.         return 
  13.     }
  14.     if len(path) == k {
  15.         if path_sum == target_sum {
  16.             temp := make([]int, k)
  17.             copy(temp, path)
  18.             result = append(result, temp)
  19.             return 
  20.         }
  21.     }
  22.     for i:=startIndex;i<=9-(k-len(path))+1;i++{
  23.         path = append(path, i)
  24.         path_sum += i 
  25.         backtrack(target_sum, k, path_sum,i+1)
  26.         path_sum -= i
  27.         path = path[:len(path)-1]
  28.     }
  29. }
  30.     // targetSum：目标和，也就是题目中的n。
  31.     // k：题目中要求k个数的集合。
  32.     // sum：已经收集的元素的总和，也就是path里元素的总和。
  33.     // startIndex：下一层for循环搜索的起始位置。

        开篇就介绍了本题与77.组合的区别，相对来说加了元素总和的限制，如果做完77.组合

再做本题在合适不过。

        分析完区别，依然把问题抽象为树形结构，按照回溯三部曲进行讲解，最后给出剪枝的优化。相信做完本题，大家对组合问题应该有初步了解了。

17.电话号码的字母组合

        给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

        给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

 示例 1：

输入：digits = "23"

输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。 ​

示例 2：

输入：digits = ""

输出：[] ​

示例 3：

输入：digits = "2"

输出：["a","b","c"]

        从示例上来说，输入"23"，最直接的想法就是两层for循环遍历了吧，正好把组合的情况都输出了。

        如果输入"233"呢，那么就三层for循环，如果"2333"呢，就四层for循环.......

        应该感觉出和[77.组合遇到的一样的问题，就是这for循环的层数如何写出来，此时又是回溯法登场的时候了。

理解本题后，要解决如下三个问题：

  1. 数字和字母如何映射
  2. 两个字母就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来
  3. 输入1 * #按键等等异常情况
  1. //1.数字和字母如何映射
  2. 可以使用map或者定义一个数组来映射。这里用数组。
  3. yingshe := []string{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}

        利用回溯法来解决n个for循环的问题。例如输入：“23”，抽象为树形结构，如图所示：

先按2（abc），再按3（def）。 长度为2哦

        图中可以看出遍历的深度，就是输入"23"的长度，而叶子节点就是我们要收集的结果，输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

回溯三部曲！

1、确定回溯函数参数：

  1. //回溯三部曲
  2. 1、确定回溯函数参数
  3. 首先需要一个path来收集叶子节点的结果，然后用result把所有path保存起来。
  4. 再来看看参数，参数指定是有题目中给的string digits，也就是给定的数字，只不过他是给的string类型的数字，反正给的数字有对应的字符串。然后需要用deep_index，用来记录遍历第几个数了，也就是遍历深度，也就是遍历题目要求的digits(字符串的数字)。
  5. var path []int
  6. var result [][]int
  7. func backtracking(digits string, deep_index int, yingshe []string, path []byte ) {
  8. }

2、递归终止条件：

  1. 2、确定终止条件
  2. 例如输入用例“23”，共两个数，那么根节点往下递归两层就可以了。叶子节点path就是要收集的结果集。那么终止条件就是如果deep_index == len(digits)输入的数字个数。就可以了。然后收集结果，结束本层递归。
  3. if deep_index == len(digits) {
  4.   tmp := make([]int,len(digits))
  5.   copy(tmp, path)
  6.   result = append(result, tmp)
  7.   return
  8. }

3、确定单层递归逻辑：

  1. 3、确定单层遍历逻辑
  2. 首先要取index指向的数字，并找到对应的字符集（数字对应的字母集），然后用for循环来处理这个数据集。
  3. digit = digits[index] - '0'
  4. letters := yingshe[digit]   //单个数字对应的字母集
  5. for i:=0;<len(letters);i++{
  6.   path = append(path,letters[i])  //把数字对应的字母集加入
  7.   backtrack（digits, deep_index+1） //递归，注意这里的deep_index是用来遍历深度的。
  8.   path = pat[:len(path)-1]  //回溯撤销
  9. }
  10.  
  11.  
  12.  
  13.   注意这里for循环，可不像是在回溯算法：求组合问题！和回溯算法：求组合和！中从startIndex开始遍历的。
  14. 因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而77. 组合和216.组合总和III都是是求同一个集合中的组合！
  15.   注意：输入1 * #按键等等异常情况
  16.   代码中最好考虑这些异常情况，但题目的测试数据中应该没有异常情况的数据，所以我就没有加了。但是要知道会有这些异常，如果是现场面试中，一定要考虑到！

所以总的代码如下：

  1. var result []string
  2. var path []byte
  3. func letterCombinations(digits string) []string {
  4.     result = []string{}
  5.     if len(digits) == 0 {
  6.         return result
  7.     }
  8.     yingshe := []string{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}
  9.  
  10.     backtracking(digits, 0, yingshe, path )
  11.     return result
  12. }
  13.  
  14. func backtracking(digits string, deep_index int, yingshe []string, path []byte ) {
  15.     if deep_index == len(digits) {
  16.         result = append(result, string(path))
  17.         return
  18.     }
  19.  
  20.     digit := digits[deep_index] - '0'   // 例如字符'2'的ascii码是50，字符'0'的ascii码是48。不减会越界的导致panic的。
  21.     letters := yingshe[digit]
  22.     for i := 0; i < len(letters); i++ {
  23.         path = append(path, letters[i])
  24.         backtracking(digits, deep_index+1, yingshe, path)
  25.         path = path[:len(path) - 1]
  26.     }
  27. }

以上

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

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

  

闽ICP备14008679号