[LintCode/LeetCode] House Robber III

macg0406 发布于2019-08-14 15:34 / 1145人阅读

摘要：解法真的非常巧妙，不过这道题里仍要注意两个细节。中，为时，返回长度为的空数组建立结果数组时，是包括根节点的情况，是不包含根节点的情况。而非按左右子树来进行划分的。

Problem

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

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

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

Note

DFS解法真的非常巧妙，不过这道题里仍要注意两个细节。
DFS中，root为null时，返回长度为2的空数组；
建立结果数组A时，A[0]是包括根节点的情况，A[1]是不包含根节点的情况。而非按左右子树来进行划分的。

Solution

public class Solution {
    public int houseRobber3(TreeNode root) {
        int[] A = dfs(root);
        return Math.max(A[0], A[1]);
    }
    public int[] dfs(TreeNode root) {
        if (root == null) return new int[2];
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int[] A = new int[2];
        A[0] = left[1] + root.val + right[1];
        A[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return A;
    }
}

云服务器 GPU云服务器 Robber House III ucos-iii 消息队列

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

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

[LintCode/LeetCode] House Robber II

摘要：因为取了队首就不能取队尾，所以对数组循环两次，一个从取到，一个从取到，比较两次循环后队尾元素，取较大者。注意，要先讨论当原数组位数小于时的情况。 Problem After robbing those houses on that street, the thief has found himself a new place for his thievery so that he wi...

OnlyLing 2019-08-14 15:34 评论0 收藏0
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
[LintCode/LeetCode] Paint House I & Paint Hous

摘要：在原数组上动规，每一行对应一个房子，每一个元素代表从第一行的房子到这一行的房子选择这一种颜色所花的最小开销。所以每个元素该元素的值上一行两个与该元素不同列元素的值的较小者。不过这次要记录三个变量本行最小值，本行第二小值，本行最小值下标。 Paint House Problem There are a row of n houses, each house can be painted ...

ChristmasBoy 2019-08-14 16:22 评论0 收藏0