程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:House Robber III

leetcode筆記:House Robber III

編輯:C++入門知識

leetcode筆記:House Robber III


一. 題目描述

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.

二. 題目分析

該題是House Robber II和House Robber的後續。

題目的意思是,小偷找到了一個新的偷盜場所。這片區域只有一個入口,叫做“根”。除了根以外,每個屋子有且僅有一個父屋子。在踩點之後盜賊發現,所有的房間構造形成了一棵二叉樹。如果兩個直接相連的屋子在同時被盜竊,就會驚動警察。

編寫函數判斷盜賊在不驚動警察的情況下最多可以偷到的金錢數目。測試用例如題目描述。

針對該題,可使用深度優先搜索來解決。對於當前節點,只有盜竊和不盜竊兩種操作,這取決於當前節點的子節點的狀態,可用兩個變量表示:precurr

pre:當前節點(屋子)不偷盜時,所能獲得的收益;取決於在該節點的兩個子節點被偷盜時的收益之和

curr:當前節點(屋子)偷盜時,所能獲得的收益;由於相鄰節點不能同時偷盜否則會引來警察,所以兩個子節點不能偷盜,此時收益等於:父節點->val + 左子節點->pre + 右子節點->pre。

比較兩種收益pre和curr,取較大者作為當前節點的最大收益。

三. 示例代碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    struct Money {
        int pre;  // 該節點不偷,收益為子節點偷的情況下的收益和
        int curr; // 該節點處偷,加上兩子節點不偷時的收益
        Money():pre(0), curr(0){}
    };

    int rob(TreeNode* root) {
        Money sum = dfs(root);
        return sum.curr;
    }

    Money dfs(TreeNode* root)
    {
        if (root == NULL) return Money();
        Money leftMoney = dfs(root->left);   // 當前節點的左子節點收益情況
        Money rightMoney = dfs(root->right); // 當前節點的右子節點收益情況
        Money sumMoney;
        sumMoney.pre = leftMoney.curr + rightMoney.curr; // 當前節點不偷
        sumMoney.curr = max(sumMoney.pre, root->val + leftMoney.pre + rightMoney.pre);
        return sumMoney;
    }
};

四. 小結

該題屬於DFS的經典題目。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved