• 代码随想录算法训练营第25天|216.组合总和III● 17.电话号码的字母组合天|


    一、216.组合总和III

    力扣

    结束条件:一个是集合的大小达到k,另一个是和等于targetSum

    循环:sum加了i,回溯的时候要减掉i。

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

    二、17.电话号码的字母组合

    理解本题后,要解决如下三个问题:

    1. 数字和字母如何映射
    2. 两个字母就两个for循环,三个字符我就三个for循环,以此类推,然后发现代码根本写不出来
    3. 输入1 * #按键等等异常情况

    回溯三部曲:

    • 确定回溯函数参数

    首先需要一个字符串temp来收集叶子节点的结果,然后用一个集合result保存起来。

    再来看参数,参数指定是有题目中给的string digits,然后还要有一个参数就是int型的index和numString映射表。(这个index是记录遍历第几个数字了,就是用来遍历digits的(题目中给出数字字符串),同时index也表示树的深度。)

    • 确定终止条件

    例如输入用例"23",两个数字,那么根节点往下递归两层就可以了,叶子节点就是要收集的结果集。

    那么终止条件就是如果index 等于 输入的数字个数(digits.size)了(本来index就是用来遍历digits的)。

    然后收集结果,结束本层递归。

    • 确定单层遍历逻辑

    首先要取index指向的数字,并找到对应的字符集(手机键盘的字符集)。

    因为本题每一个数字代表的是不同集合,也就是求不同集合之间的组合,而77. 组合 (opens new window)216.组合总和III (opens new window)都是是求同一个集合中的组合!

    然后for循环来处理这个字符集,代码如下:

    1. class Solution {
    2. List<String> result = new ArrayList<>();
    3. public List<String> letterCombinations(String digits) {
    4. if (digits == null || digits.length() == 0) {
    5. return result;
    6. }
    7. String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"};
    8. //迭代处理
    9. backTracking(digits, numString, 0);
    10. return result;
    11. }
    12. StringBuilder temp = new StringBuilder();
    13. public void backTracking(String digits, String[] numString, int index) {
    14. if (index == digits.length()) {
    15. result.add(temp.toString());
    16. return;
    17. }
    18. //str 表示当前index对应的字符串
    19. String str = numString[digits.charAt(index) - '0'];
    20. for (int i = 0; i < str.length(); i++) {
    21. temp.append(str.charAt(i));
    22. backTracking(digits, numString, index + 1);
    23. temp.deleteCharAt(temp.length() - 1);
    24. }
    25. }
    26. }

  • 相关阅读:
    简单了解JDBC相关操作
    【java】【项目实战】[外卖十二]【完结】项目优化(前后端分离开发)
    RocketMQ源码(16)—消费者负载均衡服务RebalanceService入口源码
    Java Field.set()方法具有什么功能呢?
    PD虚拟机(Parallels Desktop)2024mac苹果电脑19免费版下载
    android12 super.image 解压缩及其挂载到ubuntu
    [答疑]是不是直接写“发红包”而不是“请求微信发红包”
    Python进程池Pool详解
    Fluent Operator 2.5.0 发布:新增多个插件
    【华为OD机试真题 JS】字符串比较
  • 原文地址:https://blog.csdn.net/weixin_44565532/article/details/127538975