当前位置:   article > 正文

回溯递归的剪枝模版_灵神 模板

灵神 模板

题目传送门
主要看灵神的二分模版,如何使用递归实现在 O ( m k ) O(mk) O(mk)时间内,实现对于二分中每个条件的判断。
一般套路:

dfs函数返回值为布尔类型

循环中使用一个dfs,如果其返回true,那么直接这个dfs返回true

技巧:
一个引用类型的值作为终止条件的判断,所有的dfs共享这个变量。
灵神代码:

class Solution {
    // 返回是否找到 k 个子数组和
    bool dfs(vector<vector<int>> &mat, int &left_k, int i, int s) {
        if (i < 0) // 能递归到这里,说明数组和不超过二分的 mid
            return --left_k == 0; // 是否找到 k 个
        for (int x: mat[i]) { // 「枚举选哪个」,注意 mat[i] 是有序的
            if (x - mat[i][0] > s) // 选 x 不选 mat[i][0]
                break; // 剪枝:后面的元素更大,无需枚举
            if (dfs(mat, left_k, i - 1, s - (x - mat[i][0]))) // 选 x 不选 mat[i][0]
                return true; // 找到 k 个就一直返回 true,不再递归
        }
        return false;
    }

public:
    int kthSmallest(vector<vector<int>> &mat, int k) {
        int sl = 0, sr = 0;
        for (auto &row: mat) {
            sl += row[0];
            sr += row.back();
        }
        // 二分模板 https://www.bilibili.com/video/BV1AP41137w7/
        int left = sl - 1, right = sr; // 开区间 (sl-1,sr)
        while (left + 1 < right) { // 开区间不为空
            // 循环不变量:
            // f(left) < k
            // f(right) >= k
            int mid = left + (right - left) / 2;
            int left_k = k;
            if (dfs(mat, left_k, mat.size() - 1, mid - sl)) // 先把第一列的所有数都选上
                right = mid; // 二分范围缩小至开区间 (left, mid)
            else // f(mid) < k
                left = mid; // 二分范围缩小至开区间 (mid, right)
        }
        return right;
    }
};

作者:灵茶山艾府
链接:https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/solutions/2286593/san-chong-suan-fa-bao-li-er-fen-da-an-du-k1vd/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  • 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
  • 39
  • 40
  • 41
  • 42
  • 43

时间复杂度思考:
为什么回溯的时间复杂度为 O ( m k ) O(mk) O(mk),dfs递归的过程是一棵树从顶到底,本题中如果能够递归到 i < 0 i<0 i<0,那么就是走完了一条路径,该路径花费时间 O ( m k ) O(mk) O(mk)。如果能够成功走完k条路径,那么就直接所有的dfs开始统一返回true,在此之前所有的dfs返回的都是false。
这样做的好处是,虽然每个dfs中的for循环还没结束,但是由于出现了一个true,提前终止了循环,所有就可以保证递归树中每一层的节点个数最多为k个。着实神奇,而且写法十分优雅!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/434278
推荐阅读
相关标签
  

闽ICP备14008679号