[LeetCode]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, 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.

题目大意:

小偷又给自己找了一个新的偷盗场所。这片区域只有一个入口,叫做“根”。除了根以外,每一个房间有且仅有一个父级房间。在踩点之后,聪明的盗贼发现“所有的房间形成了一棵二叉树”。如果两个有边直接相连的房间在同一晚上都失窃,就会自动联络警察。

判断盗贼在不惊动警察的情况下最多可以偷到的金钱数目。

测试用例如题目描述。

解题思路:

解法I 深度优先搜索(DFS)

深度优先遍历二叉树,每次遍历返回两个值:分别表示偷窃或者不偷窃当前节点可以获得的最大收益。

状态转移方程见代码。

参考LeetCode Discuss:https://leetcode.com/discuss/91597/easy-understanding-solution-with-dfs

Java代码:

public class Solution {
    public int rob(TreeNode root) {
        int[] num = dfs(root);
        return Math.max(num[0], num[1]);
    }
    private int[] dfs(TreeNode x) {
        if (x == null) return new int[2];
        int[] left = dfs(x.left);
        int[] right = dfs(x.right);
        int[] res = new int[2];
        res[0] = left[1] + right[1] + x.val;
        res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return res;
    }
}

解法II 记忆化搜索(DFS + Memoization)

记当前房间为root,如果偷窃当前房间,则其左右孩子left和right均不能偷窃;而其4个孙子节点(ll,lr,rl,rr)不受影响。

因此最大收益为:

maxBenifit = max(rob(left) + rob(right), root.val + rob(ll) + rob(lr) + rob(rl) + rob(rr))

使用字典valMap记录每一个访问过的节点,可以避免重复运算。

Python代码:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        valMap = dict()
        def solve(root, path):
            if root is None: return 0
            if path not in valMap:
                left, right = root.left, root.right
                ll = lr = rl = rr = None
                if left:  ll, lr = left.left, left.right
                if right: rl, rr = right.left, right.right
                passup = solve(left, path + 'l') + solve(right, path + 'r')
                grabit = root.val + solve(ll, path + 'll') + solve(lr, path + 'lr') \
                         + solve(rl, path + 'rl') + solve(rr, path + 'rr')
                valMap[path] = max(passup, grabit)
            return valMap[path]
        return solve(root, '')

 

本文链接:http://bookshadow.com/weblog/2016/03/13/leetcode-house-robber-iii/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论