資訊專欄INFORMATION COLUMN
摘要：復(fù)雜度思路對于每一個位置來說，考慮兩種情況分別對和再進行計算。用對已經(jīng)計算過的進行保留，避免重復(fù)計算。
LeetCode[337] House Robber III
recursion + MemorizationThe 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:
3 / 2 3 3 1Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3 / 4 5 / 1 3 1Maximum amount of money the thief can rob = 4 + 5 = 9.
復(fù)雜度
O(N), O(lgN)
思路
對于每一個位置來說，考慮兩種情況, Max(child, subchild + root.val).
分別對child和subchild再進行recursion計算。
用map對已經(jīng)計算過的node進行保留，避免重復(fù)計算。
代碼
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;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65225.html
摘要：題目要求即如何從樹中選擇幾個節(jié)點，在確保這幾個節(jié)點不直接相連的情況下使其值的和最大。當前節(jié)點的情況有兩種選中或是沒選中，如果選中的話，那么兩個直接子節(jié)點將不可以被選中，如果沒選中，那么兩個直接子節(jié)點的狀態(tài)可以是選中或是沒選中。 題目要求 The thief has found himself a new place for his thievery again. There is on...
摘要：一番偵察之后，聰明的小偷意識到這個地方的所有房屋的排列類似于一棵二叉樹。如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。 Description The thief has found himself a new place for his thievery again. There is only one entranc...
摘要：解法真的非常巧妙，不過這道題里仍要注意兩個細節(jié)。中，為時，返回長度為的空數(shù)組建立結(jié)果數(shù)組時，是包括根節(jié)點的情況，是不包含根節(jié)點的情況。而非按左右子樹來進行劃分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...
摘要：你不能連著偷兩家因為這樣會觸發(fā)警報系統(tǒng)?，F(xiàn)在有一個數(shù)組存放著每一家中的可偷金額，問可以偷的最大金額為多少這里考驗了動態(tài)編程的思想。動態(tài)編程要求我們將問題一般化，然后再找到初始情況開始這個由一般到特殊的計算過程。 House Robber I You are a professional robber planning to rob houses along a street. Each...
摘要：注意對邊界條件的判斷，是否非空，是否長度為 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...
閱讀 1013·2021-11-22 09:34
閱讀 2201·2021-11-11 16:54
閱讀 2226·2021-09-27 14:00
閱讀 965·2019-08-30 15:55
閱讀 1555·2019-08-29 12:46
閱讀 630·2019-08-26 18:42
閱讀 657·2019-08-26 13:31
閱讀 3209·2019-08-26 11:52
