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’];

(仅代表个人观点)

相关内容

热门资讯

第五个了解!微扑克系统外挂透明... 第五个了解!微扑克系统外挂透明挂辅助神器,微扑克辅助哪里有卖(有挂助手)-哔哩哔哩;科技安装教程;相...
1瞬间秒懂!(打宝麻将)外挂透... 1瞬间秒懂!(打宝麻将)外挂透明挂辅助脚本!(透视)详细教程(2020已更新)(哔哩哔哩)是一款可以...
4分钟了解!智星德州菠萝软件透... 自定义新版智星德州菠萝系统规律,只需要输入自己想要的开挂功能,一键便可以生成出智星德州菠萝专用辅助器...
8刹那秒懂!(浙江闲乐)外挂辅... 8刹那秒懂!(浙江闲乐)外挂辅助器开挂!(透视)详细教程(2021已更新)(哔哩哔哩);一、浙江闲乐...
第5实锤!wpk软件透明挂辅助... 第5实锤!wpk软件透明挂辅助开挂,wpk外挂存在的(有挂助手)-哔哩哔哩;科技安装教程;相信小伙伴...
四刹那秒懂!(徒有麻将)外挂透... 四刹那秒懂!(徒有麻将)外挂透视辅助开挂!(透视)详细教程(2024已更新)(哔哩哔哩)是一款可以让...
第三个了解!德州扑克ai外挂透... 第三个了解!德州扑克ai外挂透明挂辅助插件,wpk德州辅助器是真是假(有挂头条)-哔哩哔哩;德州扑克...
第十了解!AAPoKer外挂辅... 第十了解!AAPoKer外挂辅助器作弊,wpk微扑克有辅助(有挂教程)-哔哩哔哩是一款可以让一直输的...
文心智能体平台:想象即现实(快... 🎬 鸽芷咕:个人主页 🔥 个人专栏: 《C+&...
第8个了解!微扑克规律外挂辅助... 第8个了解!微扑克规律外挂辅助脚本,wepoke透明挂识别(有挂细节)-哔哩哔哩是一款可以让一直输的...