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


    JAVA代码编写

    216. 组合总和III

    • 找出所有相加之和为 nk 个数的组合,且满足下列条件:

      • 只使用数字1到9
      • 每个数字 最多使用一次

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

      示例 1:

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

      示例 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
      没有其他符合的组合了。
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7

      示例 3:

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

      提示:

      • 2 <= k <= 9
      • 1 <= n <= 60

    教程:https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

    方法一:回溯

    思路

    class Solution {
    	List<List<Integer>> result = new ArrayList<>();
    	LinkedList<Integer> path = new LinkedList<>();
    
    	public List<List<Integer>> combinationSum3(int k, int n) {
    		backTracking(n, k, 1, 0);
    		return result;
    	}
    
    	private void backTracking(int targetSum, int k, int startIndex, int sum) {
    		// 减枝
    		if (sum > targetSum) {
    			return;
    		}
    
    		if (path.size() == k) {
    			if (sum == targetSum) result.add(new ArrayList<>(path));
    			return;
    		}
    
    		// 减枝 9 - (k - path.size()) + 1
    		for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
    			path.add(i);
    			sum += i;
    			backTracking(targetSum, k, i + 1, sum);
    			//回溯
    			path.removeLast();
    			//回溯
    			sum -= i;
    		}
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    17.电话号码的字母组合

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

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

        img

        示例 1:

        输入:digits = "23"
        输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
        
        • 1
        • 2

        示例 2:

        输入:digits = ""
        输出:[]
        
        • 1
        • 2

        示例 3:

        输入:digits = "2"
        输出:["a","b","c"]
        
        • 1
        • 2

        提示:

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

    教程:https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html

    方法一:回溯

    思路

    class Solution {
    
        //设置全局列表存储最后的结果
        List<String> list = new ArrayList<>();
    
        public List<String> letterCombinations(String digits) {
            if (digits == null || digits.length() == 0) {
                return list;
            }
            //初始对应所有的数字,为了直接对应2-9,新增了两个无效的字符串""
            String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            //迭代处理
            backTracking(digits, numString, 0);
            return list;
    
        }
    
        //每次迭代获取一个字符串,所以会设计大量的字符串拼接,所以这里选择更为高效的 StringBuild
        StringBuilder temp = new StringBuilder();
    
        //比如digits如果为"23",num 为0,则str表示2对应的 abc
        public void backTracking(String digits, String[] numString, int num) {
            //遍历全部一次记录一次得到的字符串
            if (num == digits.length()) {
                list.add(temp.toString());
                return;
            }
            //str 表示当前num对应的字符串
            String str = numString[digits.charAt(num) - '0'];
            for (int i = 0; i < str.length(); i++) {
                temp.append(str.charAt(i));
                //c
                backTracking(digits, numString, num + 1);
                //剔除末尾的继续尝试
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
  • 相关阅读:
    oracle数据库的导入与导出
    Dubbo面试题(二十八道)
    OpenCL编程指南-10.1C++包装器API
    巧用 CSS 实现炫彩三角边框动画
    iOS之APP上架
    【Verilog基础】PPA优化问题总结(含面积优化、速度优化)
    前端懒加载
    Java 异常处理
    java计算机毕业设计基于springboot+vue+elementUI的家具销售电商平台(前后端分离)
    Docker的奇幻漂流
  • 原文地址:https://blog.csdn.net/Catherinemin/article/details/134477200