成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

337. House RobberIII

妤鋒シ / 3180人閱讀

摘要：題目解答最原始的想法是對(duì)每個(gè)點(diǎn)分兩種情況考慮如果取這個(gè)點(diǎn)，那么下一次取的就是它的孫結(jié)點(diǎn)如果不取這個(gè)點(diǎn)，那么下一次取的就是它的子結(jié)點(diǎn)代碼這里用來記下當(dāng)前結(jié)點(diǎn)的和，避免一些重復(fù)記算。算法記錄下取和不取兩種情況的最大值

題目：
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.最原始的想法是對(duì)每個(gè)點(diǎn)分兩種情況考慮：如果取這個(gè)點(diǎn)，那么下一次取的就是它的孫結(jié)點(diǎn)；如果不取這個(gè)點(diǎn)，那么下一次取的就是它的子結(jié)點(diǎn)：
代碼：

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來記下當(dāng)前結(jié)點(diǎn)的和，避免一些重復(fù)記算。

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]);
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64904.html

相關(guān)文章

  • LeetCode[337] House Robber III

    摘要：復(fù)雜度思路對(duì)于每一個(gè)位置來說，考慮兩種情況分別對(duì)和再進(jìn)行計(jì)算。用對(duì)已經(jīng)計(jì)算過的進(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...

    Dr_Noooo 評(píng)論0 收藏0

  • leetcode337. House Robber III

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

    AlphaWallet 評(píng)論0 收藏0

  • LeetCode 337. House Robber III

    摘要：一番偵察之后，聰明的小偷意識(shí)到這個(gè)地方的所有房屋的排列類似于一棵二叉樹。如果兩個(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...

    ymyang 評(píng)論0 收藏0

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

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

    Ryan_Li 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<