LeetCode 打家劫舍系列问题整理

本文对文章 https://labuladong.github.io/algo/1/14/ 多有参考。

198. 打家劫舍

主要的思想是动态规划。

纯粹的递归，效率很低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 纯递归，会超时

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        self.nums = nums

        def dp(start: int):
            if start >= len(self.nums):
                return 0
            res = max(dp(start + 1), self.nums[start] + dp(start + 2))
            return res

        return dp(0)


solu = Solution()
nums = [1, 2, 3, 1]
nums = [183, 219, 57, 193, 94, 233, 202, 154, 65, 240, 97, 234, 100, 249, 186, 66, 90, 238,
        168, 128, 177, 235, 50, 81, 185, 165, 217, 207, 88, 80, 112, 78, 135, 62, 228, 247, 211]
res = solu.rob(nums)
print(res)

使用备忘录的递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 依然是自顶向下，使用备忘录

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        self.nums = nums
        self.memo = [-1] * len(self.nums)

        def dp(start: int):
            if start >= len(self.nums):
                return 0
            if self.memo[start] != -1:
                return self.memo[start]
            res = max(dp(start + 1), self.nums[start] + dp(start + 2))
            self.memo[start] = res
            return res

        return dp(0)


solu = Solution()
nums = [1, 2, 3, 1]
nums = [183, 219, 57, 193, 94, 233, 202, 154, 65, 240, 97, 234, 100, 249, 186, 66, 90, 238,
        168, 128, 177, 235, 50, 81, 185, 165, 217, 207, 88, 80, 112, 78, 135, 62, 228, 247, 211]
# 这个测试用例决定了备忘录中的默认值不能是 0
nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
res = solu.rob(nums)
print(res)

方法三：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 自底向上构建

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        res = [0] * (len(nums) + 2)
        for i in range(len(nums) - 1, -1, -1):
            res[i] = max(res[i + 1], nums[i] + res[i + 2])
        return res[0]


solu = Solution()
nums = [1, 2, 3, 1]
nums = [183, 219, 57, 193, 94, 233, 202, 154, 65, 240, 97, 234, 100, 249, 186, 66, 90, 238,
        168, 128, 177, 235, 50, 81, 185, 165, 217, 207, 88, 80, 112, 78, 135, 62, 228, 247, 211]
# 这个测试用例决定了备忘录中的默认值不能是 0
# nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
#         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
res = solu.rob(nums)
print(res)

优化方法三，得到方法四：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 自底向上构建，优化空间复杂度

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        res = 0
        oneStep = 0
        twoSteps = 0
        for i in range(len(nums) - 1, -1, -1):
            res = max(oneStep, nums[i] + twoSteps)
            oneStep, twoSteps = res, oneStep

        return res


solu = Solution()
nums = [1, 2, 3, 1]
# nums = [183, 219, 57, 193, 94, 233, 202, 154, 65, 240, 97, 234, 100, 249, 186, 66, 90, 238,
#         168, 128, 177, 235, 50, 81, 185, 165, 217, 207, 88, 80, 112, 78, 135, 62, 228, 247, 211]
# 这个测试用例决定了备忘录中的默认值不能是 0
# nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
#         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
res = solu.rob(nums)
print(res)

213. 打家劫舍 II

对于这种动态规划，还是不优化这个空间使用更加容易理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
'''
原来思路很简单。和简单版本的打家劫舍是一样的。
只需要考虑去头或者去尾的情况即可。
'''

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        dp1 = [0] * (len(nums) + 1)
        dp2 = [0] * (len(nums) + 1)
        numsExclueHead = nums[1:]
        numsExcludeTail = nums[:-1]

        for i in range(len(numsExclueHead) - 1, -1, -1):
            dp1[i] = max(dp1[i + 1], numsExclueHead[i] + dp1[i + 2])

        for i in range(len(numsExcludeTail) - 1, -1, -1):
            dp2[i] = max(dp2[i + 1], numsExcludeTail[i] + dp2[i + 2])

        return max(dp1[0], dp2[0])


solu = Solution()
nums = [2, 3, 2]
nums = [1, 2, 3, 1]
res = solu.rob(nums)
print(res)

337. 打家劫舍 III

一般的递归。思路很容易想。代码也比较容易写。只是，为了效率，要加备忘录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
# 使用备忘录的递归，不然会超时

from typing import List
from queue import Queue

# Definition for a binary tree node.


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.right = None
        self.left = None

    def insert(self, val):
        if self.val == val:
            return
        elif self.val < val:
            if self.right is None:
                self.right = TreeNode(val)
            else:
                self.right.insert(val)
        else:  # self.val > val
            if self.left is None:
                self.left = TreeNode(val)
            else:
                self.left.insert(val)

    def display(self):
        lines, *_ = self._display_aux()
        for line in lines:
            print(line)

    def _display_aux(self):
        """Returns list of strings, width, height, and horizontal coordinate of the root."""
        # No child.
        if self.right is None and self.left is None:
            line = '%s' % self.val
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle

        # Only left child.
        if self.right is None:
            lines, n, p, x = self.left._display_aux()
            s = '%s' % self.val
            u = len(s)
            first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
            second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
            shifted_lines = [line + u * ' ' for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2

        # Only right child.
        if self.left is None:
            lines, n, p, x = self.right._display_aux()
            s = '%s' % self.val
            u = len(s)
            first_line = s + x * '_' + (n - x) * ' '
            second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
            shifted_lines = [u * ' ' + line for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

        # Two children.
        left, n, p, x = self.left._display_aux()
        right, m, q, y = self.right._display_aux()
        s = '%s' % self.val
        u = len(s)
        first_line = (x + 1) * ' ' + (n - x - 1) * \
            '_' + s + y * '_' + (m - y) * ' '
        second_line = x * ' ' + '/' + \
            (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' '
        if p < q:
            left += [n * ' '] * (q - p)
        elif q < p:
            right += [m * ' '] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] + \
            [a + u * ' ' + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2


def buildTree(data: List[int]):
    count = 0
    q = Queue()
    root = TreeNode(data[0])
    q.put(root)
    curNode = None

    for i in range(1, len(data)):
        node = TreeNode(data[i]) if data[i] != None else None
        if count == 0:
            curNode = q.get()
            count += 1
            curNode.left = node
        else:
            count = 0
            curNode.right = node
        if data[i] != None:
            q.put(node)

    return root


class Solution:
    def rob(self, root: TreeNode) -> int:
        self.memo = {}

        def rob(root: TreeNode):
            if root == None:
                return 0
            if root in self.memo:
                return self.memo[root]
            res0 = rob(root.left) + rob(root.right)
            res1 = root.val
            if root.left != None:
                res1 += rob(root.left.left) + rob(root.left.right)
            if root.right != None:
                res1 += rob(root.right.left) + rob(root.right.right)
            res = max(res0, res1)
            self.memo[root] = res
            return res

        return rob(root)


solu = Solution()
data = [3, 2, 3, None, 3, None, 1]
data = [3, 4, 5, 1, 3, None, 1]
data = [79, 99, 77, None, None, None, 69, None, 60, 53, None, 73, 11, None, None, None,
        62, 27, 62, None, None, 98, 50, None, None, 90, 48, 82, None, None, None, 55, 64,
        None, None, 73, 56, 6, 47, None, 93, None, None, 75, 44, 30, 82, None, None, None,
        None, None, None, 57, 36, 89, 42, None, None, 76, 10, None, None, None, None, None,
        32, 4, 18, None, None, 1, 7, None, None, 42, 64, None, None, 39, 76, None, None, 6, None,
        66, 8, 96, 91, 38, 38, None, None, None, None, 74, 42, None, None, None, 10, 40, 5, None,
        None, None, None, 28, 8, 24, 47, None, None, None, 17, 36, 50, 19, 63, 33, 89, None, None,
        None, None, None, None, None, None, 94, 72, None, None, 79, 25, None, None, 51, None, 70,
        84, 43, None, 64, 35, None, None, None, None, 40, 78, None, None, 35, 42, 98, 96, None, None,
        82, 26, None, None, None, None, 48, 91, None, None, 35, 93, 86, 42, None, None, None, None, 0,
        61, None, None, 67, None, 53, 48, None, None, 82, 30, None, 97, None, None, None, 1, None, None]
root = buildTree(data)
root.display()
res = solu.rob(root)
print(res)

LeetCode
#动态规划 #LeetCode
LeetCode 打家劫舍系列问题整理
http://fanlumaster.github.io/2022/03/20/LeetCode-打家劫舍系列问题整理/
作者
fanlumaster
发布于
2022年3月20日
许可协议