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

2024-01-09 20:38:45

回溯问题的模板

    public static void backtracking(参数列表){
        if(终止条件){
        	存放结果
            return;
        }

        for(选择:本层集合中元素(树中节点孩子的数量就是集合的大小)){
        	处理节点;
        	backtracking(路径,选择列表); // 递归
       		回溯,撤销处理结果
        }
    }

LeetCode 77 组合

在这里插入图片描述
本题思路:组合问题,利用回溯来解决。回溯就是用来解决纯暴力解决不了的问题。此题,如果通过 for 循环, 也可以解决,但是如果 k 越来越来越大,那么就要写越来越多的 for,不切实际。
此时就可以利用回溯来解决。

  • 第一步就是分析终止条件,终止条件,就是组合大小等于 k,就可以进行结束,进行保存
  • 而 for 循环处理的就是这每一个元素
    • 保存节点
    • 然后进行递归处理
    • 然后回退到上一个节点
class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> path = new ArrayList();
        backtracking(path,res,n,k,1);
        return res;
    }

    public void backtracking(List<Integer> path,List<List<Integer>> res,int n, int k, int startIndex){
        // 先找出口终止条件
        if(path.size() == k){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = startIndex; i <= n-(k-path.size())+1 ; i++){
            path.add(i);
            backtracking(path,res,n,k,i+1);
            path.removeLast();
        }
    }
}

LeetCode 216 组合总和||

在这里插入图片描述
本题思路:和上题一样,终止条件也是元素个数满足为 k的时候,不过保存结果的时候,要加个判断,和是否等于 n,只有等于才会保存起来。

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> path = new ArrayList();
        backtracking(res,path,k,n,1);
        return res;
    }


    public void backtracking(List<List<Integer>> res, List<Integer> path, int k , int n , int startIndex){
        // 终止条件
        if(path.size() == k){
            int sum = 0;
            for(int i = 0; i < path.size(); i++){
                sum += path.get(i);
            }
            if(sum == n){
                res.add(new ArrayList(path));
            }
        }
        for(int i = startIndex; i <= 9; i++){
            path.add(i);
            backtracking(res,path,k,n,i+1);
            path.removeLast();
        }
    }
}

LeetCode 17 电话号码的字母组合

在这里插入图片描述
本题思路:本题和上述两题不同,不在同一个集合里面,是不同的集合,所以参数就用 index 了,不用 startIndex 进行去重。

  • 首先要将数字和对应的字符做一个映射
  • 这里终止条件就是遍历完当前数字所对应的字符串了
class Solution {

    String[] sMap = new String[]{" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList();
        List<Character> path = new ArrayList();
        if(digits.equals("")){
            return res;
        }
        backtracking(digits,0,res,path);
        return res;
    }

    public void backtracking(String digits, int index, List<String> res, List<Character> path){
        // 终止条件
        if(index == digits.length()){
            StringBuilder s =  new StringBuilder();
            for(int i = 0; i < path.size(); i++){
                s.append(path.get(i));
            }
            res.add(s.toString());
            return;
        }
        Character ch = digits.charAt(index);
        String str = sMap[ch - '0'];
        for(int i = 0; i < str.length(); i++){
            path.add(str.charAt(i));
            backtracking(digits,index+1,res,path);
            path.removeLast();
        }
    }
}

文章来源:https://blog.csdn.net/hero_jy/article/details/135486288
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。