day22 | 77. 组合 216.组合总和III 17.电话号码的字母组合
创始人
2024-12-01 00:33:06
0

代码随想录算法训练营第22天| 77. 组合216.组合总和III17.电话号码的字母组合

Leetcode 77. 组合
题目链接:https://leetcode.cn/problems/combinations/description/
题目描述:

给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:

输入:n = 4, k = 2 输出: [   [2,4],   [3,4],   [2,3],   [1,2],   [1,3],   [1,4], ] 

示例 2:

输入:n = 1, k = 1 输出:[[1]] 

提示:

  • 1 <= n <= 20
  • 1 <= k <= n
思路:

1、回溯

2、剪枝

图示:

在这里插入图片描述

代码1:回溯
class Solution {     // 声明用来存放结果的数组     List> res = new ArrayList<>();     LinkedList path = new LinkedList<>();     public List> combine(int n, int k) {         backTracking(n , k , 1);         return res;     }     // 回溯     public void backTracking(int n ,int k , int startIndex){         // 终止条件         if(path.size() == k){             // 存放结果             res.add(new ArrayList<>(path));             return;         }         // 单层递归逻辑         for(int i = startIndex ; i <=  n ; i++){             path.add(i);             backTracking( n , k , i + 1);             path.removeLast();         }         // removeLast()方法用于返回最后一个元素,但要从此双端队列移除该元素。     } } 
代码2:剪枝
class Solution {     // 声明单条路径     LinkedList path = new LinkedList<>();     // 声明结果     List> res = new ArrayList<>();     public List> combine(int n, int k) {         // 剪枝优化         backTracking(n , k , 1);         return res;     }     public void backTracking(int n ,int k , int startIndex){         // 终止条件         if(path.size() == k){             // 收集好了,添加至res             res.add(new ArrayList<>(path));             return;         }         // 单层的回溯逻辑         for(int i = startIndex ; i <= (n - (k - path.size()) + 1) ; i++){             // n - (k - path.size()) + 1 为至多要从该位置遍历             path.add(i);             backTracking(n ,k , i + 1);             path.removeLast();         }     } } 
总结:
Leetcode 216.组合总和III
题目链接:https://leetcode.cn/problems/combination-sum-iii/
题目描述:找出所有相加之和为 nk 个数的组合,且满足下列条件:
  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。 

示例 2:

输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。 

示例 3:

输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字,我们可以得到的最小和是1+2+3+4 = 10,因为10 > 1,没有有效的组合。 

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60
思路:

1、回溯

2、剪枝

图示:

在这里插入图片描述

代码1:回溯
class Solution {     // 单个路径     LinkedList path = new LinkedList<>();     // 结果     List> res = new ArrayList<>();     public List> combinationSum3(int k, int n) {                 backTracking(  k , n , 0 , 1);         return res;     }     // 回溯算法     public void backTracking(int k , int targetSum , int sum , int startIndex){                  // 终止条件         if(path.size() == k){             if(targetSum == sum){                 res.add(new LinkedList<>(path));                 return;             }         }                  // 单层递归逻辑         for(int i = startIndex ; i <= 9 ; i++){             path.add(i);             sum += i;             backTracking( k , targetSum , sum , i + 1);             // startIndex防止组合中出现重复结果             sum = sum - i;             path.removeLast();         }     } } 
代码2:剪枝
class Solution {     List> res = new ArrayList<>();     LinkedList path = new LinkedList<>();     public List> combinationSum3(int k, int n) {         // 剪枝         backTracking( k , n , 0 , 1);         return res;     }     public void backTracking(int k , int targetSum , int sum , int startIndex){         // 终止条件         if(targetSum < sum){             return;         }         if(path.size() == k){             if(targetSum == sum){                 res.add(new LinkedList<>(path));                 return;             }         }         // 单层         for(int i = startIndex ; i <= (9 - (k - path.size())) + 1 ; i++){             path.add(i);             sum += i;             backTracking( k , targetSum ,sum , i + 1);             path.removeLast();             sum -= i;         }     } } 
总结:

注意:此题每个数字 最多使用一次 ,该列表不能包含相同的组合两次

所以startIndex后续加1

Leetcode 17.电话号码的字母组合
题目链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
题目描述:
输入:digits = "2" 输出:["a","b","c"] 

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。
思路:

1、回溯

图示:

在这里插入图片描述

代码1:回溯
class Solution {     // 声明结果     List res = new ArrayList<>();     public List letterCombinations(String digits) {         // 排空         if(digits == null || digits.length() == 0){             return res;         }         // 定义数字对应的字符串         //初始对应所有的数字,为了直接对应2-9,新增了两个无效的字符串""         String[] strNum = {"",     //0                         "",     //1                         "abc",  //2                         "def",  //3                         "ghi",  //4                         "jkl",  //5                         "mno",  //6                         "pqrs",                         "tuv",                         "wxyz"};         backTracking(digits , strNum , 0);         return res;     }     //每次迭代获取一个字符串,     // 所以会涉及大量的字符串拼接,     // 所以这里选择更为高效的 StringBuilder     StringBuilder stringB = new StringBuilder();     // num 用来记录当前遍历第几个数字     public void backTracking(String digits , String[] strNum , int num){         // 终止条件         if(num == digits.length()){             res.add(stringB.toString());             return;         }          //str 代表 num 对应的字符串         String str =  strNum[digits.charAt(num) - '0'];         // charAt()是一种从指定索引返回字符的方法,字符串中的字符从左到右索引。         // 单层递归逻辑         for( int i = 0 ; i < str.length(); i++){             stringB.append(str.charAt(i));             backTracking(digits , strNum , num + 1);              //剔除末尾的继续尝试             stringB.deleteCharAt(stringB.length() - 1);         }     } } 
总结:
本题难点在于
//str 代表 num 对应的字符串

String str = strNum[digits.charAt(num) - ‘0’];

(仅代表个人观点)

相关内容

热门资讯

科普2下!(美金局AA扑克)原... 科普2下!(美金局AA扑克)原来始终是有挂!(软件透明挂)外挂透明挂辅助器神器!(2021有挂版);...
新2021版教程"鱼... 新2021版教程"鱼乐达人外挂透视辅助器脚本!原来一直皆有挂"2020已更新(哔哩哔哩);AI智能教...
科普8下"AAPoK... 科普8下"AAPoKer其实有挂猫腻(作弊)原来有挂猫腻"1/5已拥有(2024有挂版)德扑锦标赛是...
新2023版教程"中... 新2023版教程"中至都昌讨赏原来一直都是有挂!1/9已拥有"确实一贯总有挂(2024已更新);超受...
科普四下"最新版德州... 德州ai,咨询(小薇485275054)了解;德州ai是一款WPK题材类的回合制手游,同时小编本次带...
新2022版教程"中... 新2022版教程"中至上饶同城原来一直都是有挂!太坑了"原来一贯是真有挂(2020已更新)中至上饶同...
科普9下!(大厅WePoKer... 科普9下!(大厅WePoKer)原来一贯真的有挂!(软件透明挂)外挂透明挂辅助插件!(2022有挂版...
新2021版教程!(小吆干瞪眼... 新2021版教程!(小吆干瞪眼)原来向来有挂!(辅助)外挂透视辅助器软件!(2022已更新);小吆干...
cdn许可证多少钱_内容分发网... CDN许可证的价格因供应商、服务范围和所需带宽等因素而异。内容分发网络(CDN)通过在不同地理位置部...
科普九下"德州版德普... 科普九下"德州版德普之星‘外挂透明挂辅助器插件!1/2已拥有"其实真的是有挂(2024有挂版);超受...