leetcode337. House Robber III

AlphaWallet 發布于2019-08-16 11:14 / 2631人閱讀

摘要：題目要求即如何從樹中選擇幾個節點，在確保這幾個節點不直接相連的情況下使其值的和最大。當前節點的情況有兩種選中或是沒選中，如果選中的話，那么兩個直接子節點將不可以被選中，如果沒選中，那么兩個直接子節點的狀態可以是選中或是沒選中。

題目要求

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:
     3
    / 
   2   3
        
     3   1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
     3
    / 
   4   5
  /     
 1   3   1
Maximum amount of money the thief can rob = 4 + 5 = 9.

即如何從樹中選擇幾個節點，在確保這幾個節點不直接相連的情況下使其值的和最大。

思路和代碼

最開始的思路我是采用自頂向下遞歸遍歷樹的形式來計算可能獲得的最大收益。當前節點的情況有兩種：選中或是沒選中，如果選中的話，那么兩個直接子節點將不可以被選中，如果沒選中，那么兩個直接子節點的狀態可以是選中或是沒選中。代碼如下：

    public int rob(TreeNode root) {
        if(root == null) return 0;
        int result1 = root.val + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right)) + (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
        int result2 = rob(root.left) + rob(root.right);
        return Math.max(result1, result2);
    }

這段代碼的缺陷在于，我需要遍歷這棵樹兩次，分別為了獲取選中當前節點和不選中當前節點的情況。而事實上我們可以在一次遍歷中就得到這兩個情況對于當前節點的影響，并通過遞歸將值傳遞回上一層。很像是一種逆向思維。

    public int rob2(TreeNode root) {
        if (root == null) return 0;
        int[] value = robSum(root);
        return Math.max(value[0], value[1]);
    }
    
    private int[] robSum(TreeNode root) {
        int[] res = new int[2];
        if (root == null) return res;
        
        int[] left = robSum(root.left);
        int[] right = robSum(root.right);
        
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        
        return res;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

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

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

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