力扣337——打家劫舍 III

2024-01-05 20:43:34

这一篇也是基于"打家劫舍"的扩展，需要针对特殊情况特殊考虑，当然其本质还是动态规划，优化时需要考虑数据结构。

原题

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3   3   1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4   5 = 9.

原题url：https://leetcode-cn.com/problems/house-robber-iii/

解题

先给出树节点的结构：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

简单思路

这道题简单来说，就是如果存在父节点、子节点、孙子节点三层的话，要么偷父节点孙子节点，要么只偷子节点。

顺着这个思路，我们只要找出每个节点所能偷到的最大值，自然也就能找出从 root 节点开始偷的最大值了。

接下来我们看看代码：

class Solution {

    Map<TreeNode, Integer> cache = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 是否已经计算过
        if (cache.containsKey(root)) {
            return cache.get(root);
        }

        // 策略1：抢当前节点和孙子节点
        int sum1 = root.val   
            // 左子节点的子节点们
            (root.left == null ? 0 : (rob(root.left.left)   rob(root.left.right)))  
            // 右子节点的子节点们
            (root.right == null ? 0 : (rob(root.right.left)   rob(root.right.right)));
        // 策略2：只抢子节点
        int sum2 = rob(root.left)   rob(root.right);
        // 找出更大的值
        int sum = Math.max(sum1, sum2);
        // 并记录
        cache.put(root, sum);
        return sum;
    }
}

提交OK，执行用时：5 ms，只战胜了52.00%的 java 提交记录，因此还是有值得优化的地方。

优化

上面的解法，如果说有什么值得优化的地方，就是在于我们在动态规划时，不仅考虑了子节点，甚至也考虑到了孙子节点，因此当子节点变成父节点之后，孙子节点也变成了子节点。

也就是说，一开始的孙子节点被计算了两遍。虽然我们借用了一个 map 来记录了中间结果，但我们需要注意，这种情况依旧会被计算，只是代价被转移到了针对 map 的操作，这也是需要消耗时间的。

那么现在的优化，就转变成针对中间状态的记录上了。

其实我们针对每个节点的状态，只需要记录两种情况：抢或者不抢。而且这个状态只会被父节点用到，并不需要永久保留。因此我们考虑用一个长度为 2 的数组进行记录，这样就会快捷很多。

接下来我们看看代码：

class Solution {
    public int rob(TreeNode root) {
        // index为0，代表不抢当前节点的最大值
        // index为1，代表抢当前节点，不抢子节点的最大值
        int[] res = dp(root);
        return Math.max(res[0], res[1]);

    }

    public int[] dp(TreeNode cur) {
        if(cur == null) {
            return new int[]{0,0};
        }
        
        int[] left = dp(cur.left);
        int[] right = dp(cur.right);
        // 抢当前节点，子节点都不抢
        int rob = cur.val   left[0]  right[0];
        // 不抢当前节点，获取左右子节点各自的最大值
        int notRob = Math.max(left[0], left[1])   Math.max(right[0], right[1]);
        // 返回结果 
        return new int[]{notRob, rob};

    }
}

提交OK，时间消耗只有1 ms，确实快了很多。