打家劫舍 III(LeetCode 337)

简介: 打家劫舍 III(LeetCode 337)

打家劫舍 III(LeetCode 337)

Description

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root

除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。

Sample Input 1

img

root = [3,2,3,null,3,null,1]

Sample Output 1

3

Sample Tips 1

小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

Sample Input 2

img

root = [3,4,5,1,3,null,1]

Sample Output 2

9

Sample Tips 2

小偷一晚能够盗取的最高金额 4 + 5 = 9

Tips

  • 树的节点数在 [1, 104] 范围内
  • 0 <= Node.val <= 104

算法思想:

对于树的话,首先就要想到遍历方式,前中后序(深度优先搜索)还是层序遍历(广度优先搜索)。

本题一定是要后序遍历,因为通过递归函数的返回值来做下一步计算

与198.打家劫舍,213.打家劫舍II一样,关键是要讨论当前节点抢还是不抢。

如果抢了当前节点,两个孩子就不能动,如果没抢当前节点,就可以考虑抢左右孩子。

暴力递归

代码如下:

class Solution {
public:
    int rob(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return root->val;
        // 偷父节点
        int val1 = root->val;
        if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left,相当于不考虑左孩子了
        if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right,相当于不考虑右孩子了
        // 不偷父节点
        int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子
        return max(val1, val2);
    }
};
  • 时间复杂度:O(n^2),这个时间复杂度不太标准,也不容易准确化,例如越往下的节点重复计算次数就越多
  • 空间复杂度:O(log n),算上递推系统栈的空间

这个递归的过程中其实是有重复计算了。

我们计算了root的四个孙子(左右孩子的孩子)为头结点的子树的情况,又计算了root的左右孩子为头结点的子树的情况,计算左右孩子的时候其实又把孙子计算了一遍。

因此可以采用记忆化递推:所以可以使用一个map把计算过的结果保存一下,这样如果计算过孙子了,那么计算孩子的时候可以复用孙子节点的结果。

class Solution {
public:
    unordered_map<TreeNode* , int> umap; // 记录计算过的结果
    int rob(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return root->val;
        if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回
        // 偷父节点
        int val1 = root->val;
        if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left
        if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right
        // 不偷父节点
        int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子
        umap[root] = max(val1, val2); // umap记录一下结果
        return max(val1, val2);
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(log n),算上递推系统栈的空间

在上面两种方法,其实对一个节点 偷与不偷得到的最大金钱都没有做记录,而是需要实时计算。

而动态规划其实就是使用状态转移容器来记录状态的变化,可以使用一个长度为2的数组,记录当前节点偷与不偷所得到的的最大金钱。

动规五部曲分析如下:

  1. 确定递归函数的参数和返回值

    这里我们要求一个节点 偷与不偷的两个状态所得到的金钱,那么返回值就是一个长度为2的数组。

    参数为当前节点,代码如下:

    vector<int> robTree(TreeNode* cur) {

    其实这里的返回数组就是dp数组。

    所以dp数组(dp table)以及下标的含义:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱。

    所以本题dp数组就是一个长度为2的数组!

    在递归的过程中,系统栈会保存每一层递归的参数

  2. 确定终止条件

    在遍历的过程中,如果遇到空节点的话,很明显,无论偷还是不偷都是0,所以就返回

    if (cur == NULL) return vector<int>{0, 0};

    这也相当于dp数组的初始化

  3. 确定遍历顺序

    首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。

    通过递归左节点,得到左节点偷与不偷的金钱。

    通过递归右节点,得到右节点偷与不偷的金钱。

    代码如下:

    // 下标0:不偷,下标1:偷
    vector<int> left = robTree(cur->left); // 左
    vector<int> right = robTree(cur->right); // 右
    // 中
  4. 确定单层递归的逻辑

    如果是偷当前节点,那么左右孩子就不能偷,val1 = cur->val + left[0] + right[0]; (如果对下标含义不理解就再回顾一下dp数组的含义

    如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的,所以:val2 = max(left[0], left[1]) + max(right[0], right[1]);

    最后当前节点的状态就是{val2, val1}; 即:{不偷当前节点得到的最大金钱,偷当前节点得到的最大金钱}

    vector<int> left = robTree(cur->left); // 左
    vector<int> right = robTree(cur->right); // 右
    
    // 偷cur
    int val1 = cur->val + left[0] + right[0];
    // 不偷cur
    int val2 = max(left[0], left[1]) + max(right[0], right[1]);
    return {val2, val1};

综上分析完毕,代码如下:

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // 长度为2的数组,0:不偷,1:偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷cur,那么就不能偷左右节点。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur,那么可以偷也可以不偷左右节点,则取较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};

Java代码代码如下:

class Solution {
    // 1.递归去偷,超时
    public int rob(TreeNode root) {
        if (root == null)
            return 0;
        int money = root.val;
        if (root.left != null) {
            money += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            money += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(money, rob(root.left) + rob(root.right));
    }

    // 2.递归去偷,记录状态
    // 执行用时:3 ms , 在所有 Java 提交中击败了 56.24% 的用户
    public int rob1(TreeNode root) {
        Map<TreeNode, Integer> memo = new HashMap<>();
        return robAction(root, memo);
    }

    int robAction(TreeNode root, Map<TreeNode, Integer> memo) {
        if (root == null)
            return 0;
        if (memo.containsKey(root))
            return memo.get(root);
        int money = root.val;
        if (root.left != null) {
            money += robAction(root.left.left, memo) + robAction(root.left.right, memo);
        }
        if (root.right != null) {
            money += robAction(root.right.left, memo) + robAction(root.right.right, memo);
        }
        int res = Math.max(money, robAction(root.left, memo) + robAction(root.right, memo));
        memo.put(root, res);
        return res;
    }

    // 3.状态标记递归
    // 执行用时:0 ms , 在所有 Java 提交中击败了 100% 的用户
    // 不偷:Max(左孩子不偷,左孩子偷) + Max(又孩子不偷,右孩子偷)
    // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
    // Math.max(rob(root.right)[0], rob(root.right)[1])
    // 偷:左孩子不偷+ 右孩子不偷 + 当前节点偷
    // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
    public int rob3(TreeNode root) {
        int[] res = robAction1(root);
        return Math.max(res[0], res[1]);
    }

    int[] robAction1(TreeNode root) {
        int res[] = new int[2];
        if (root == null)
            return res;

        int[] left = robAction1(root.left);
        int[] right = robAction1(root.right);

        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        return res;
    }
}
目录
相关文章
|
缓存 Dubbo druid
SOFABoot 4.0 正式发布,多项新特性等你来体验!
SOFABoot 4.0 依赖 Java 17 作为最小支持的 JDK 版本。如果你的应用目前使用 Java 8 或 11,你需要先将自己的 JDK 版本升级到 17 才能基于 SOFABoot 4.0 进行开发。
|
存储 关系型数据库 MySQL
MySQL 处理大数据表的 3 种方案,写的太好了,建议收藏!!
MySQL 处理大数据表的 3 种方案,写的太好了,建议收藏!!
962 0
|
测试技术 微服务 负载均衡
微服务部署:蓝绿部署、滚动部署、灰度发布、金丝雀发布
在项目迭代的过程中,不可避免需要”上线“。上线对应着部署,或者重新部署;部署对应着修改;修改则意味着风险。 目前有很多用于部署的技术,有的简单,有的复杂;有的得停机,有的不需要停机即可完成部署。
3022 0
|
8月前
|
机器学习/深度学习 测试技术 计算机视觉
YOLOv11改进策略【Conv和Transformer】| ICCV-2023 iRMB 倒置残差移动块 轻量化的注意力模块
YOLOv11改进策略【Conv和Transformer】| ICCV-2023 iRMB 倒置残差移动块 轻量化的注意力模块
205 7
YOLOv11改进策略【Conv和Transformer】| ICCV-2023 iRMB 倒置残差移动块 轻量化的注意力模块
|
7月前
|
SQL 安全 数据库
win10 安装 sql server2012
安装 SQL Server 2012 是许多开发者使用数据库的第一步。主要步骤包括:下载并运行安装程序,接受许可条款,选择功能(如数据库引擎服务),配置实例和服务器设置,设置身份验证模式,完成安装并进行测试。建议安装 SQL Server Management Studio (SSMS) 进行管理和维护,确保数据安全。
276 3
|
12月前
|
前端开发 JavaScript 中间件
七、Flask蓝图使用之七
七、Flask蓝图使用之七
263 0
|
10月前
|
SQL 分布式计算 DataWorks
DataWorks产品测评|基于DataWorks和MaxCompute产品组合实现用户画像分析
本文介绍了如何使用DataWorks和MaxCompute产品组合实现用户画像分析。首先,通过阿里云官网开通DataWorks服务并创建资源组,接着创建MaxCompute项目和数据源。随后,利用DataWorks的数据集成和数据开发模块,将业务数据同步至MaxCompute,并通过ODPS SQL完成用户画像的数据加工,最终将结果写入`ads_user_info_1d`表。文章详细记录了每一步的操作过程,包括任务开发、运行、运维操作和资源释放,帮助读者顺利完成用户画像分析。此外,还指出了文档中的一些不一致之处,并提供了相应的解决方法。
|
运维 测试技术
拆分软件测试流程,一张图秒杀所有面试
本文主要介绍了软件测试流程的核心内容,包括需求分析、测试用例编写、测试执行、缺陷提交及回归测试等关键步骤。以迭代测试为例,详细说明了每个环节的具体操作和注意事项,并提供了一张测试流程图以便理解。测试流程确保了软件质量,是面试中常见的考察点。
745 7
拆分软件测试流程,一张图秒杀所有面试
|
12月前
|
分布式计算 Java 大数据
大数据-147 Apache Kudu 常用 Java API 增删改查
大数据-147 Apache Kudu 常用 Java API 增删改查
120 1
|
Java
Java并行流问题之parallelStream的使用方式
Java并行流问题之parallelStream的使用方式
275 1