資訊專欄INFORMATION COLUMN
摘要：解法真的非常巧妙，不過(guò)這道題里仍要注意兩個(gè)細(xì)節(jié)。中，為時(shí)，返回長(zhǎng)度為的空數(shù)組建立結(jié)果數(shù)組時(shí)，是包括根節(jié)點(diǎn)的情況，是不包含根節(jié)點(diǎn)的情況。而非按左右子樹(shù)來(lái)進(jìn)行劃分的。
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 3
/
2 3
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
3 / 4 5 / 1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
NoteDFS解法真的非常巧妙，不過(guò)這道題里仍要注意兩個(gè)細(xì)節(jié)。
DFS中，root為null時(shí)，返回長(zhǎng)度為2的空數(shù)組；
建立結(jié)果數(shù)組A時(shí)，A[0]是包括根節(jié)點(diǎn)的情況，A[1]是不包含根節(jié)點(diǎn)的情況。而非按左右子樹(shù)來(lái)進(jìn)行劃分的。
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/65853.html
摘要：因?yàn)槿×岁?duì)首就不能取隊(duì)尾，所以對(duì)數(shù)組循環(huán)兩次，一個(gè)從取到，一個(gè)從取到，比較兩次循環(huán)后隊(duì)尾元素，取較大者。注意，要先討論當(dāng)原數(shù)組位數(shù)小于時(shí)的情況。 Problem After robbing those houses on that street, the thief has found himself a new place for his thievery so that he wi...
摘要：復(fù)雜度思路對(duì)于每一個(gè)位置來(lái)說(shuō)，考慮兩種情況分別對(duì)和再進(jìn)行計(jì)算。用對(duì)已經(jīng)計(jì)算過(guò)的進(jìn)行保留，避免重復(fù)計(jì)算。 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...
摘要：題目要求即如何從樹(shù)中選擇幾個(gè)節(jié)點(diǎn)，在確保這幾個(gè)節(jié)點(diǎn)不直接相連的情況下使其值的和最大。當(dāng)前節(jié)點(diǎn)的情況有兩種選中或是沒(méi)選中，如果選中的話，那么兩個(gè)直接子節(jié)點(diǎn)將不可以被選中，如果沒(méi)選中，那么兩個(gè)直接子節(jié)點(diǎn)的狀態(tài)可以是選中或是沒(méi)選中。 題目要求 The thief has found himself a new place for his thievery again. There is on...
摘要：一番偵察之后，聰明的小偷意識(shí)到這個(gè)地方的所有房屋的排列類似于一棵二叉樹(shù)。如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。 Description The thief has found himself a new place for his thievery again. There is only one entranc...
摘要：在原數(shù)組上動(dòng)規(guī)，每一行對(duì)應(yīng)一個(gè)房子，每一個(gè)元素代表從第一行的房子到這一行的房子選擇這一種顏色所花的最小開(kāi)銷。所以每個(gè)元素該元素的值上一行兩個(gè)與該元素不同列元素的值的較小者。不過(guò)這次要記錄三個(gè)變量本行最小值，本行第二小值，本行最小值下標(biāo)。 Paint House Problem There are a row of n houses, each house can be painted ...
閱讀 1410·2021-11-25 09:43
閱讀 2268·2021-09-27 13:36
閱讀 1121·2021-09-04 16:40
閱讀 1962·2019-08-30 11:12
閱讀 3314·2019-08-29 14:14
閱讀 570·2019-08-28 17:56
閱讀 1328·2019-08-26 13:50
閱讀 1251·2019-08-26 13:29
