国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

337. House RobberIII

妤鋒シ / 3125人閱讀

摘要：題目解答最原始的想法是對每個點分兩種情況考慮如果取這個點，那么下一次取的就是它的孫結點如果不取這個點，那么下一次取的就是它的子結點代碼這里用來記下當前結點的和，避免一些重復記算。算法記錄下取和不取兩種情況的最大值

題目：
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.

解答：
1.最原始的想法是對每個點分兩種情況考慮：如果取這個點，那么下一次取的就是它的孫結點；如果不取這個點，那么下一次取的就是它的子結點：
代碼：

private Map map = new HashMap<>();
public int rob(TreeNode root) {
    if (root == null) return 0;
    if (map.containsKey(root)) return map.get(root);
    
    int result = 0;
    if (root.left != null) {
        result += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right != null) {
        result += rob(root.right.left) + rob(root.right.right);
    }
    
    result = Math.max(root.val + result, rob(root.left) + rob(root.right));
    map.put(root, result);
    
    return result;
}

這里用map來記下當前結點的和，避免一些重復記算。

2.Greedy算法

public int[] Helper(TreeNode root) {
    if (root == null) return new int[2];
    //記錄下取和不取兩種情況的最大值
    int[] left = Helper(root.left);
    int[] right = Helper(root.right);
    int[] res = new int[2];
    res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    res[1] = root.val + left[0] + right[0];
    
    return res;
}

public int rob(TreeNode root) {
    int[] res = Helper(root);
    return Math.max(res[0], res[1]);
}

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64904.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 評論0 收藏0

  • leetcode337. House Robber III

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

    AlphaWallet 評論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 評論0 收藏0

  • RxJava系列四（過濾操作符）

    摘要：過濾類操作符主要包含等等。獲取房源列表中的最后一套房源小區房源描述程序輸出小區中糧海景壹號房源描述南北通透，豪華五房只發射觀測序列中符合條件的最后一個數據項。 轉載請注明出處：https://zhuanlan.zhihu.com/p/21966621 RxJava系列1(簡介) RxJava系列2(基本概念及使用介紹) RxJava系列3(轉換操作符) RxJava系列4(過濾操作符...

    Ryan_Li 評論0 收藏0

發表評論

0條評論

妤鋒シ

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<