LeetCode 337. House Robber III

ymyang 發(fā)布于2019-07-31 10:16 / 1298人閱讀

摘要：一番偵察之后，聰明的小偷意識到這個地方的所有房屋的排列類似于一棵二叉樹。如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

Description

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:

Input: [3,2,3,null,3,null,1]

     3
    / 
   2   3
        
     3   1

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

Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / 
   4   5
  /     
 1   3   1

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

描述

在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現了一個新的可行竊的地區(qū)。這個地區(qū)只有一個入口，我們稱之為“根”。除了“根”之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。

計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

示例 1:

輸入: [3,2,3,null,3,null,1]

     3
    / 
   2   3
        
     3   1

輸出: 7 
解釋: 小偷一晚能夠盜取的最高金額 = 3 + 3 + 1 = 7.

示例 2:

輸入: [3,4,5,1,3,null,1]

     3
    / 
   4   5
  /     
 1   3   1

輸出: 9
解釋: 小偷一晚能夠盜取的最高金額 = 4 + 5 = 9.

思路

用一個包含兩個元素的數組 result ，result[0] 表示偷當前節(jié)點的房子，result[1] 表示不偷當前節(jié)點的房子。

如果偷當前的房子，那么 result[0] = 當前節(jié)點的值 + max(左右子樹中，不偷根節(jié)點房子可以獲得的最大值)。

如果不偷當前的房子，那么 result[1] = max(左子樹中偷或不偷根節(jié)點房子可以獲得的最大值) + max(右子樹中偷或不偷根節(jié)點房子可以獲得的最大值)

最后可以獲得的最大值值為 max(result)

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-04-07 10:43:47
# @Last Modified by:   何睿
# @Last Modified time: 2019-04-07 11:00:22


class Solution:
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return max(self.recursion(root))

    def recursion(self, root):
        # result[0] 表示偷當前的房子，result[1] 表示不偷當前的房子
        if not root: return [0, 0]
        result = [0, 0]
        left = self.recursion(root.left)
        right = self.recursion(root.right)
        # 偷當前的房子：result[0] ：當前節(jié)點的值+ 左右子樹中不偷根節(jié)點房子的最大值
        result[0] = root.val + left[1] + right[1]
        # 不偷當前的房子：result[1] 那么左右子樹的根節(jié)點偷不偷都可以，選最大值
        result[1] = max(left[0], left[1]) + max(right[0], right[1])
        return result

源代碼文件在這里。
?本文首發(fā)于何睿的博客，歡迎轉載，轉載需保留文章來源，作者信息和本聲明.

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43542.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

摘要：題目要求即如何從樹中選擇幾個節(jié)點，在確保這幾個節(jié)點不直接相連的情況下使其值的和最大。當前節(jié)點的情況有兩種選中或是沒選中，如果選中的話，那么兩個直接子節(jié)點將不可以被選中，如果沒選中，那么兩個直接子節(jié)點的狀態(tài)可以是選中或是沒選中。題目要求 The thief has found himself a new place for his thievery again. There is on...

AlphaWallet 2019-08-16 11:14 評論0 收藏0
[LintCode/LeetCode] House Robber III

摘要：解法真的非常巧妙，不過這道題里仍要注意兩個細節(jié)。中，為時，返回長度為的空數組建立結果數組時，是包括根節(jié)點的情況，是不包含根節(jié)點的情況。而非按左右子樹來進行劃分的。 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

摘要：你不能連著偷兩家因為這樣會觸發(fā)警報系統(tǒng)。現在有一個數組存放著每一家中的可偷金額，問可以偷的最大金額為多少這里考驗了動態(tài)編程的思想。動態(tài)編程要求我們將問題一般化，然后再找到初始情況開始這個由一般到特殊的計算過程。 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