337. House RobberIII

妤锋シ发布于2019-08-14 14:15 / 3052人阅读

摘要：题目解答最原始的想法是对每个点分两种情况考虑如果取这个点，那么下一次取的就是它的孙结点如果不取这个点，那么下一次取的就是它的子结点代码这里用来记下当前结点的和，避免一些重复记算。算法记录下取和不取两种情况的最大值

题目：
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:

Maximum amount of money the thief can rob = 4 + 5 = 9.

解答：
1.最原始的想法是对每个点分两种情况考虑：如果取这个点，那么下一次取的就是它的孙结点；如果不取这个点，那么下一次取的就是它的子结点：
代码：

private Map map = new HashMap<>();
public int rob(TreeNode root) {
    if (root == null) return 0;
    if (map.containsKey(root)) return map.get(root);
    
    int result = 0;
    if (root.left != null) {
        result += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right != null) {
        result += rob(root.right.left) + rob(root.right.right);
    }
    
    result = Math.max(root.val + result, rob(root.left) + rob(root.right));
    map.put(root, result);
    
    return result;
}

这里用map来记下当前结点的和，避免一些重复记算。

2.Greedy算法

public int[] Helper(TreeNode root) {
    if (root == null) return new int[2];
    //记录下取和不取两种情况的最大值
    int[] left = Helper(root.left);
    int[] right = Helper(root.right);
    int[] res = new int[2];
    res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    res[1] = root.val + left[0] + right[0];
    
    return res;
}

public int rob(TreeNode root) {
    int[] res = Helper(root);
    return Math.max(res[0], res[1]);
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64904.html

LeetCode[337] House Robber III

摘要：复杂度思路对于每一个位置来说，考虑两种情况分别对和再进行计算。用对已经计算过的进行保留，避免重复计算。 LeetCode[337] House Robber III The thief has found himself a new place for his thievery again. There is only one entrance to this area, calle...

Dr_Noooo 2019-08-14 15:00 评论0 收藏0
leetcode337. House Robber III

摘要：题目要求即如何从树中选择几个节点，在确保这几个节点不直接相连的情况下使其值的和最大。当前节点的情况有两种选中或是没选中，如果选中的话，那么两个直接子节点将不可以被选中，如果没选中，那么两个直接子节点的状态可以是选中或是没选中。题目要求 The thief has found himself a new place for his thievery again. There is on...

AlphaWallet 2019-08-16 11:14 评论0 收藏0
LeetCode 337. House Robber III

摘要：一番侦察之后，聪明的小偷意识到这个地方的所有房屋的排列类似于一棵二叉树。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。 Description The thief has found himself a new place for his thievery again. There is only one entranc...

ymyang 2019-07-31 10:16 评论0 收藏0
RxJava系列四（过滤操作符）

摘要：过滤类操作符主要包含等等。获取房源列表中的最后一套房源小区房源描述程序输出小区中粮海景壹号房源描述南北通透，豪华五房只发射观测序列中符合条件的最后一个数据项。转载请注明出处：https://zhuanlan.zhihu.com/p/21966621 RxJava系列1(简介) RxJava系列2(基本概念及使用介绍) RxJava系列3(转换操作符) RxJava系列4(过滤操作符...

Ryan_Li 2019-08-14 17:14 评论0 收藏0