LeetCode[337] House Robber III

Dr_Noooo 發布于2019-08-14 15:00 / 926人閱讀

摘要：復雜度思路對于每一個位置來說，考慮兩種情況分別對和再進行計算。用對已經計算過的進行保留，避免重復計算。

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, 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.

recursion + Memorization

復雜度
O(N), O(lgN)

思路
對于每一個位置來說，考慮兩種情況, Max(child, subchild + root.val).
分別對child和subchild再進行recursion計算。

用map對已經計算過的node進行保留，避免重復計算。

代碼

public int rob(TreeNode root) {
    // Base case;
    if(root == null) return 0;
    if(root.left == null && root.right == null) return root.val;
    if(map.containsKey(root)) return map.get(root);
    int child = 0, subchild = 0;
    if(root.left != null) {
        child += rob(root.left);
        subchild += rob(root.left.left) + rob(root.left.right);
    }
    if(root.right != null) {
        child += rob(root.right);
        subchild += rob(root.right.left) + rob(root.right.right);
    }
    int val = Math.max(child, subchild + root.val);
    map.put(root, val);
    return val;
}

GPU云服務器云服務器 Robber House ee337新域名 III

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65225.html

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] House Robber III

摘要：解法真的非常巧妙，不過這道題里仍要注意兩個細節。中，為時，返回長度為的空數組建立結果數組時，是包括根節點的情況，是不包含根節點的情況。而非按左右子樹來進行劃分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...

macg0406 2019-08-14 15:34 評論0 收藏0
leetcode198,213 house robber

摘要：你不能連著偷兩家因為這樣會觸發警報系統。現在有一個數組存放著每一家中的可偷金額，問可以偷的最大金額為多少這里考驗了動態編程的思想。動態編程要求我們將問題一般化，然后再找到初始情況開始這個由一般到特殊的計算過程。 House Robber I You are a professional robber planning to rob houses along a street. Each...

whidy 2019-08-16 11:01 評論0 收藏0
[LeetCode] House Robber I II

摘要：注意對邊界條件的判斷，是否非空，是否長度為 House Robber I Problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping y...

qpal 2019-08-14 15:17 評論0 收藏0