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

216.组合总和III

直接在77的基础上修改,参数多了个sum,终止条件改成两个if嵌套,先判断大小=k,再判断sum=n,否则直接return!(不能合在一起判断,否则会栈溢出,无法return!

  • java代码
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public void backtracking(int k, int target, int startIndex,int sum) {
        if (path.size() == k) {
            if (sum == target) {
                result.add(new ArrayList<>(path));
            }
            return; // 如果path.size() == k 但sum != n 直接返回
        }
        for(int i = startIndex; i <= 9 - (k-path.size()) + 1; i++) {
            sum+=i;
            path.add(i);
            
            backtracking(k,target,i+1,sum);
            sum-=i;
            path.removeLast();
            
        }
    } 

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k,n,1,0);
        return result;
    }
}

17.电话号码的字母组合

![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img-home.csdnimg.cn/images/20230724024159.png?

  • 关键:
  1. 数字和字母如何映射 – 用一个String数组映射,作为回溯函数参数
//初始对应所有的数字,为了直接对应0-9,新增了两个无效的字符串"",对应0和1
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  1. for循环里的i的个数 = 这一位上所有可能的情况个数(numString[k].length())!
  2. 每次递归用num表示当前位数。
  3. 用一个List<String> result存储,用stringbuilder拼接,存进去之前先toString()转换一下。
  4. 怎么用给的数字得到对应字符串?numString[digits.charAt(num) - '0']

回溯三部曲:

  1. 确定回溯函数:传入映射数组,digits和num(表示当前要讨论的位数)
void backtracking(String digits, String[] numsString, int num)
  1. 终止条件:num==digits长度了(num从0开始)
if(digits.length() == num) {  //收获结果
	result.add(sb.toString());
    return;
}
  1. 单层逻辑

恢复现场用deleCharAt()方法,获得当前位数字对应的字符串用str = numsString[digits.charAt(num) - '0'];

 String str = numsString[digits.charAt(num) - '0'];
        for(int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            backtracking(digits,numsString,num+1);
            sb.deleteCharAt(sb.length()-1);  //恢复现场
        }
  • java代码
class Solution {
    List<String> result = new ArrayList<>() ;
    StringBuilder sb = new StringBuilder(); 
    public void backtracking(String digits, String[] numsString, int num) {   
        if(digits.length() == num) {  //收获结果
            result.add(sb.toString());
            return;
        }
        String str = numsString[digits.charAt(num) - '0'];
        for(int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            backtracking(digits,numsString,num+1);
            sb.deleteCharAt(sb.length()-1);  //恢复现场
        }
    }   

    public List<String> letterCombinations(String digits) {
        String[] numsString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        if(digits.equals("")) return result;  //注意特殊情况 digits为空特殊判断
        backtracking(digits, numsString, 0);
        return result;
    }
}

Day25总结

  1. 数字的list恢复现场用removeLast(),path数组是LinkedList

  2. 字符串恢复现场用sb.deleteCharAt()

  3. 电话号码题用String数组保存映射关系。

  4. 取出String每一位上的可以直接str = numsString[digits.charAt(num) - '0']

  5. 单层递归逻辑里for循环的次数就是 这一位上能填的值的情况总数!

最近更新

  1. leetcode705-Design HashSet

    2024-04-04 00:48:02       8 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-04 00:48:02       8 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-04 00:48:02       9 阅读
  4. 高级IO——React服务器简单实现

    2024-04-04 00:48:02       8 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-04 00:48:02       7 阅读
  6. go第三方库go.uber.org介绍

    2024-04-04 00:48:02       8 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-04 00:48:02       10 阅读

热门阅读

  1. 蓝桥杯刷题--python-36

    2024-04-04 00:48:02       2 阅读
  2. how to Optimize mysql select clause

    2024-04-04 00:48:02       4 阅读
  3. flutter一个bloc可以对应多个state

    2024-04-04 00:48:02       4 阅读
  4. 讨论 OpenSIPS 预加载路由的问题

    2024-04-04 00:48:02       5 阅读
  5. 【电路笔记】-逻辑与门

    2024-04-04 00:48:02       3 阅读