337. 打家劫舍 III [medium]

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.

通过次数56,880 | 提交次数95,684

Second Try [golang]

2020-08-05

go练手来一波。同样的写法，速度果然要比python快几倍

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type key struct {
    node *TreeNode
    allowed bool
}

var cache map[key]int = make(map[key]int)

func dfs(node *TreeNode, allowed bool) int {
    if node == nil {
        return 0 
    }

    if val, ok := cache[key{node, allowed}]; ok {
        return val 
    }
    not_sel := dfs(node.Left, true) + dfs(node.Right, true)
    maxv := not_sel
    if allowed {
        sel := node.Val + dfs(node.Left, false) + dfs(node.Right, false)
        if not_sel < sel {
            maxv = sel
        } 
    }
    cache[key{node, allowed}] = maxv 
    return maxv 
}

func rob(root *TreeNode) int {
    rv := dfs(root, true)
    return rv 
}

执行用时：12 ms, 在所有 Go 提交中击败了52.08%的用户
内存消耗：6.1 MB, 在所有 Go 提交中击败了6.67%的用户

First Try

2020-08-05

没想到竟然超时了，写了个递归+内存索引的cache版本。因为对python熟悉，写个内存定位信手拈来，不知道其他语言的话该如何处理？

# 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:
        # 遍历可能性，对于每个节点，要么选择要么不选择。对程序而言暴力法最容易了。
        # oops, 竟然超时了，看来还是得上缓存才行, 但是没有个标记法啊。。。
        # 找不到合适的标记方法，直接上内存标记，并且携带上allowed selected信息， 而不是is_selected信息
        cache = dict()
        def path(node, allowed_selected):
            if not node:
                return 0 
            if (id(node), allowed_selected) in cache:
                return cache[(id(node), allowed_selected)]
            # if not selected, the child node could be selected
            # even if allowed selected, current node could be not selected
            maxv = not_sel = path(node.left, allowed_selected=True) + path(node.right, allowed_selected=True)

            # if allowed to be selected and being selected, child node could not be selected
            if allowed_selected:
                sel = node.val + path(node.left, allowed_selected=False) + path(node.right, allowed_selected=False)
                maxv = max(not_sel, sel)
            
            cache[(id(node), allowed_selected)] = maxv 
            return maxv 
        
        return path(root, allowed_selected=True)
        

执行用时：72 ms, 在所有 Python3 提交中击败了31.91%的用户
内存消耗：18.7 MB, 在所有 Python3 提交中击败了5.36%的用户

337. 打家劫舍 III [medium]​

Second Try [golang]​

First Try​

337. 打家劫舍 III [medium]

Second Try [golang]

First Try