• 欢迎光临~

代码随想录训练营|Day 25|216,17

开发技术 开发技术 2022-10-14 次浏览

216. Combination Sum III

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

  • Only numbers 1 through 9 are used.
  • Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints:

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

在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。
k相当于了树的深度,9(因为整个集合就是9个数)就是树的宽度。
需要一维数组path来存放符合条件的结果,二维数组result来存放结果集。
还需要如下参数:

  • targetSum(int)目标和,也就是题目中的n。
  • k(int)就是题目中要求k个数的集合。
  • sum(int)为已经收集的元素的总和,也就是path里元素的总和。
  • startIndex(int)为下一层for循环搜索的起始位置。

k其实就已经限制树的深度,因为就取k个元素,树再往下深了没有意义。

如果path.size() 和 k相等了,就终止

如果此时path里收集到的元素和(sum) 和targetSum(就是题目描述的n)相同了,就用result收集当前的结果。

处理过程 和 回溯过程是一一对应的,处理有加,回溯就要有减!

已选元素总和如果已经大于n(图中数值为4)了,那么往后遍历就没有意义了,直接剪掉。

class Solution {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        build(k, n, 1, 0);
        return ans;
    }

    private void build(int k, int n, int startIndex, int sum) {
        
        if (sum > n) return;

        if (path.size() > k) return;

        if (sum == n && path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }
        
        for(int i = startIndex; i <= 9; i++) {
            path.add(i);
            sum += i;
            build(k, n, i + 1, sum);
            sum -= i;
            path.removeLast();
        }
    }
}

For Future References

题目链接:https://leetcode.com/problems/combination-sum-iii/

文章讲解:https://programmercarl.com/0216.组合总和III.html


17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

代码随想录训练营|Day 25|216,17

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

代码随想录训练营|Day 25|216,17

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

index是记录遍历第几个数字了,就是用来遍历digits的(题目中给出数字字符串),同时index也表示树的深度。

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

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

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

然后for循环来处理这个字符集

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);
        }
    }
}

For Future References

题目链接:https://leetcode.com/problems/letter-combinations-of-a-phone-number/

文章讲解:https://programmercarl.com/0017.电话号码的字母组合.html

程序员灯塔
转载请注明原文链接:代码随想录训练营|Day 25|216,17
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com