力扣337——打家劫舍 III
这一篇也是基于”打家劫舍”的扩展,需要针对特殊情况特殊考虑,当然其本质还是动态规划,优化时需要考虑数据结构。
原题
在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
示例 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 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
,确实快了很多。
总结
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要还是利用动态规划,只是需要大家进行思路转化,优化时需要考虑的更多是对数据结构的理解。
有兴趣的话可以访问我的博客或者关注我的公众号,说不定会有意外的惊喜。
https://death00.github.io/
公众号:健程之道
点击此处留言