几道入门的回溯题 | LeetCode

一杯JAVA浓 做棵大树 3周前 (04-17) 46次浏览 0个评论
文章目录[隐藏]

入门级回溯问题记录

回学校后发现大家都在不停的卷,而自己本周只写了没几道力扣题目...

这周写的几道题整体上都是回溯类型的,也都是些入门级的回溯问题。整体有一套回溯的模板,周末了做个简单的总结记录,也是为了“交作业”哈。

关于回溯自己之前转载了一篇大神的文章:有兴趣的可以看看。

LC22. 括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]

当时的想法:

  1. 定义返回类型 List 这个不管什么时候肯定是需要返回值的

  2. 因为题目中的这个涉及到回退,所以我们单独定义一个函数来进行 回溯 操作的处理

    Java 中因为引用对象都是传递的内存地址,所以我们在定义函数的时候直接放进去即可;另外题目中涉及到有效的括号组合 所以我们应该把判断有效用的参数放进方法里,另外将我们当前的状态也就是目前的字符串要放到参数里,因为它是我们的主角,要进行检查和修改的参数。

    那怎么判断是否有效呢?

    • 左括号和对数比较,少了,则说明不够
    • 左括号个数和右括号个数比较,确定有没有正确的闭合。

    这时候就可以把回溯的函数头定义出来了 process(List<String> res, String str, int left, int right, int n)

  3. 思考该怎么记录状态,什么时候符合返回值的需要

    str的长度达到了对数的两倍(正确的长度)我们就可以把它记录到返回值中了。因为 Stringfinal 修饰的所以我们直接 add() 就行。

  4. 状态什么时候回溯

    然后因为左括号在左,也就是先出现的,所以我们把左括号的逻辑放在右括号的前边。而回溯的代码就是把状态转变为前一个状态,对于字符串而言,就是删除最后一个添加的字符。

主要是这几个步骤吧,我们就可以编写了。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 回溯
        process(res, "", 0, 0, n);

        return res;
    }

    // 记录,字符串,左括号数量,右括号数量,一共几对
    public void process(List<String> res, String str, int left, int right, int n){
        if(str.length() == n * 2){
            // 长度够了
            res.add(str);
            return;
        }
        if(left < n){
            // 左括号不够
            str += "(";
            process(res, str, left + 1, right, n);
            // 回复之前状态
            str = str.substring(0, str.length()-1);
        }
        if(left > right){
            // 没有全部闭合
            str += ")";
            process(res, str, left, right + 1, n);
            // 回复之前状态
            str = str.substring(0, str.length()-1);
        }
    }
}

LC39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target,找出 candidates中所有可以使数字和为 target的组合。

candidates中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。 

示例 1:

输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

输入:candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

当时的想法:

整体和上一题实际上是一样的,具体不一样的点就是:这个问题涉及到的只有一个需要进行记录的点,就是 list 符合不符合,而上一题进行判断,需要对括号的个数写两个判断逻辑。

方法定义的时候,我们也要考虑到:返回值记录值中间值/参考值下一个开始点(主要涉及到同一个值能不能呗重复使用)

然后还要注意,因为 backtrace 一般都会涉及到递归结构,所以出口的定义也很重要,很多时候可以避免重复添加。

class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        findResult(res, list, candidates, target, 0);

        return res;
    }

    public void findResult(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int begin){
        if(begin == candidates.length || target < 0) return;
        if(target == 0){
            // 根据条件的取值范围知,当 target == 0 已找到
            res.add(new ArrayList(list));
            return;
        }
        for(int left = begin; left < candidates.length; left++){
            list.add(candidates[left]);   // 添加进去
            // target - candidate[left] 为更新要查找的值,同“两/三数之和”一样
            findResult(res, list, candidates, target - candidates[left], left);
            list.remove(list.size() - 1);
        }
    }

    // public boolean notAdded(List<Integer> list){
    //     // 去重

    // }
}

LC40.组合总和 II

这道题同上一题相同,唯一区别在于:candidates 中的每个数字在每个组合中只能使用一次。

这个在写的时候因为这个条件提错了三次。。。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Arrays.sort(candidates);

        backtrace(res, list, candidates, target, 0);

        return res;
    }

    public void backtrace(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int index){
        // 因为往后移动了一位,避免重复使用同一数字,所以 index 要用 > 否则最后一个下标的递归没法进行检查
        if(target < 0 || index > candidates.length) return;
        if(target == 0){
            if(!res.contains(new ArrayList(list)))
                // 为了去重
                res.add(new ArrayList(list));
            return;
        }

        for(int i = index; i<candidates.length; i++){
            list.add(candidates[i]);

            backtrace(res, list, candidates, target - candidates[i], i+1);

            list.remove(list.size() - 1);
        }
    }
}

LC797. 所有可能的路径

给一个有 n 个结点的有向无环图,找到所有从 0n-1 的路径并输出(不要求按顺序)

二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点(译者注:有向图是有方向的,即规定了 a→b 你就不能从 b→a )空就是没有下一个结点了。

示例 1:

输入:graph = [[1,2],[3],[3],[]]
输出:[[0,1,3],[0,2,3]]
解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

这是一条图的路径问题,考虑到的应该也是深度遍历的思想,同时题目要求 0 -- n-1 也指定了结束条件,最开始写时候忽略了,我以为是要所有的路径呢。

那么思路也是相同的,我们按照上述的来进行写即可。

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> item = new ArrayList<>();
        item.add(0);        // 添加起始点

        backtrace(res, item, graph, 0);

        return res;
    }

    public void backtrace(List<List<Integer>> res, List<Integer> item, int[][] graph, int currentNode){
        int[] canReach = graph[currentNode];            // 当前点可到达的点
        if(currentNode == graph.length - 1){
            res.add(new ArrayList(item));       //最后一个节点
            return;
        }

        for(int i = 0; i < canReach.length; i++){
            item.add(canReach[i]);
            backtrace(res, item, graph, canReach[i]);       // 根据当前点延伸到可以到达的点
            item.remove(item.size() - 1);
        }
    }
}

End

为什么说这是回溯问题的入门呢,因为我们从题目中可以看到,他们的解题结构都是一样的,大致可以概括为以下的代码结构:

主方法{
    返回值
    填充值

    回溯方法(返回值,填充值,状态记录相关参数...);

    return 返回值;
}

回溯方法{
    // 状态核验,是否符合合法条件
    if(不符合合法条件) return;
    if(符合返回条件) 添加进返回值;

    进入递归状态,一般会涉及到循环
        循环语句
        递归调用回溯方法(返回值,填充值,更新后的状态记录参数)
        消除上次修改的状态,完成回溯
    循环结束

    涉及多个状态的可能要写不只一个回溯的代码段,视情况而定。
}

但是再深一点的回溯问题,可能不会这么容易的让我们找到 该怎么记录状态 以及 什么时候实现状态回退,所以上边的题目应该只能算我们入门回溯的几道入门题目了,这里也就不再班门弄斧了,大家可以去LeetCode的回溯专题下去做一下相关题目。


做棵大树 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明几道入门的回溯题 | LeetCode
喜欢 (0)
[欢迎投币]
分享 (0)
关于作者:
一个整天无所事事的,有时候忽然热血的孩子
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址