美文网首页
LeetCode 337. 打家劫舍 III | Python

LeetCode 337. 打家劫舍 III | Python

作者: 大梦三千秋 | 来源:发表于2020-08-05 19:07 被阅读0次

    337. 打家劫舍 III


    题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/house-robber-iii

    题目


    在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

    计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

    示例 1:

    输入: [3,2,3,null,3,null,1]
    
         3
        / \
       2   3
        \   \ 
         3   1
    
    输出: 7 
    解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
    

    示例 2:

    输入: [3,4,5,1,3,null,1]
    
         3
        / \
       4   5
      / \   \ 
     1   3   1
    
    输出: 9
    解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
    

    解题思路


    这道题是 【198. 打家劫舍】、【213. 打家劫舍 II】 的后续

    思路:递归、动态规划

    在这道题当中,偷窃的对象不再是一条街或者围成圈的房屋。而是看似二叉树排布的房屋。在这里,我们会用动态规划的方法来解决。

    不过在此之前,我们先看题目,【如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警】,这里的意思是,不能够偷窃相连的两个节点,也就是不能同时偷窃属于父子关系的节点。

    题目给定的二叉树中,节点上的权值也就是要偷窃的金额,按照上面的条件,也就是说,每个节点都有两种状态:已偷取、未偷取。由于不能同时偷窃属于父子关系的节点,求该条件限定下,能偷取的金额最大值为多少。

    递归

    在这里,我们先用递归的方法来解决,这里根据上面的分析,分情况来讨论,具体思路如下(基于三层的二叉树描述):

    • 当偷窃根节点时,则无法偷窃根节点下的左右子节点,但是可以选择投左右子节点下的子树。
    • 当不偷窃根节点时,则可以考虑偷窃根节点下的左右子节点。

    那么,大致的代码如下:

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def rob(self, root: TreeNode) -> int:
            if not root:
                return 0
            # 分情况
            # 偷窃根节点 与 不偷窃根节点
            in_root = root.val
            if root.left:
                # 偷窃根节点时,无法偷取子节点,那么偷窃子孙节点
                in_root += self.rob(root.left.left) +self. rob(root.left.right)
            if root.right:
                in_root += self.rob(root.right.left) +self. rob(root.right.right)
            
            # 不偷取根节点,那么收益就是左右子节点权值的总和
            not_in_root = self.rob(root.left) + self.rob(root.right)
    
            # 返回大值
            return max(in_root, not_in_root)
    

    上面这段代码执行后超时,因为在计算子孙节点的时候,计算了根节点下的左右子树,而后续计算又重复计算了子孙节点。在这里,我们来进行优化,将计算后的结果存储到哈希表中,遇到需要重复计算的部分,直接拿过来,不需要再次递归计算。

    优化后代码见【代码实现 # 递归(优化)】

    动态规划

    从上面递归的方法中,我们可以发现,最终最大收益为 in_root 和 not_in_root 的最大值。

    也就是说,每个子树都有最优解:偷窃根节点 和 不偷窃根节点下的最优解。

    我们重新定义这个问题,每个节点可以选择偷或者不偷,那么相连节点不能一起偷,那么:

    • 如果当前节点选择偷窃时,左右子节点不选择偷;
    • 如果当前节点选择不偷时,左右子节点主要能获得最优解就行。

    定义数组存储两个状态,索引 0 表示不偷,索引 1 表示偷。那么每个节点能偷到最大金额可定义为:

    • 当前节点选择偷窃时,最大金额数 = 左子节点不偷能获得的最大金额 + 右子节点不偷能获得的最大金额 + 当前节点的金额
    • 当前节点选择不偷时,最大金额 = 左子节点能偷的最大金额 + 右子节点能偷的最大金额。

    那么相应的转移公式为:

    # 当前节点不偷
    ans[0] = max(rob(root.left)[0], rob(root.left)[1])
           + max(rob(root.right)[0], rob(root.right)[1])
    # 当前节点选择偷
    ans[1] = rob(root.left)[0] + rob(root.right)[0] +  root.val
    

    具体代码见【代码实现 # 动态规划】

    代码实现


    # 递归(优化)
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def rob(self, root: TreeNode) -> int:
            # 存储计算过的结果
            hash_map = {}
            def helper(root):
                if not root:
                    return 0
                # 如果存在于哈希表中,直接拿过来用
                if root in hash_map:
                    return hash_map[root]
                in_root = root.val
                if root.left:
                    # 偷窃根节点时,无法偷取子节点,那么偷窃子孙节点
                    in_root += helper(root.left.left) +helper(root.left.right)
                if root.right:
                    in_root += helper(root.right.left) +helper(root.right.right)
    
                # 不偷取根节点,那么收益就是左右子节点权值的总和
                not_in_root = helper(root.left) + helper(root.right)
                ans = max(in_root, not_in_root)
                # 这里计算完之后,将结果存入哈希表中
                hash_map[root] = ans
                return ans
            return helper(root)
    
    # 动态规划
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def rob(self, root: TreeNode) -> int:
            def helper(root):
                if not root:
                    return [0, 0]
                
                ans = [0, 0]
    
                left = helper(root.left)
                right = helper(root.right)
    
                # 两个索引对应两种状态,索引 0 表示不偷,索引 1 表示偷
                ans[0] = max(left[0], left[1]) + max(right[0], right[1])
                ans[1] = left[0] + right[0] + root.val
    
                return ans
            
            ans = helper(root)
            return max(ans[0], ans[1])
    

    实现结果


    实现结果 | 递归(优化) 实现结果 | 动态规划

    欢迎关注


    公众号 【书所集录

    相关文章

      网友评论

          本文标题:LeetCode 337. 打家劫舍 III | Python

          本文链接:https://www.haomeiwen.com/subject/qgvorktx.html