面试常遇的打家劫舍问题你学会了吗~

打家劫舍I

问题描述

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ec9b2891-2dab-4fc5-8a11-3f6773c8b3d6

示例：

输入：[1，2，3，1]

输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

分析问题

首先，我们先将问题简化处理。假设目前只有一间房屋，则偷窃该房屋，此时就是偷窃到的最高总金额。如果只有两间房屋，因为此时两间房屋相邻，只能偷窃其中的一间房屋，可以选择其中金额较高的房屋进行偷窃，就是可以偷窃到的最高总金额。如果房屋的数量大于两间，假设小偷此时处于第k（k>2）间房屋，那么他有两个选择。

• 如果他偷窃第k间房屋，那么他就不能偷窃第k-1间房屋，此时其能偷窃到的总金额为前k-2间房屋的最高总金额和第k间房屋的金额之和。
• 如果他不偷窃第k间房屋，那么此时其能偷窃到的总金额为前k-1间房屋的最高总金额。

在上述两个选项中选择金额较大的即为前k间房屋能偷窃到的最高总金额。

我们用 dp[i] 来表示前 i 间房屋能偷窃到的最高总金额，经过前面的分析，可以知道其状态转移方程为：

dp[i] = max( dp[i-2] + nums[i] , dp [i-1])

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d4252c7a-196c-488b-99e7-4d62fb12725e

• 当只有一间房屋时，此时dp[0] = nums[0]，表示偷窃该房屋。
• 当只有两间房屋时，此时 dp[1] = max(nums[0] , nums[1])，即在这两间房屋中选择金额较大的房屋进行偷窃。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:cb4f7370-7318-4ad5-8652-3d461e83ca22

class Solution:
    def rob(self, nums):
        #如果数组为空，则直接返回0
        if not nums:
            return 0

        length = len(nums)
        #如果房屋数量等于1
        #则直接偷窃第一间房屋，
        #所以此时能偷窃到的最大金额是nums[0]
        if length == 1:
            return nums[0]
        dp = [0] * length
        #边界条件
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, length):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

        return dp[length - 1]

该算法的时间复杂度是O(n)，空间复杂度也是O(n)。

通过观察，我们发现dp[i] 只和 dp[i-2] 和 dp[i-1]有关，即只和该房屋的前两间房屋的最高总金额相关，所以我们可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额即可，从而降低空间复杂度。我们来看一下代码的实现。

class Solution:
    def rob(self, nums):
        #如果数组为空，则直接返回0
        if not nums:
            return 0

        length = len(nums)
        #如果房屋数量等于1
        #则直接偷窃第一间房屋，
        #所以此时能偷窃到的最大金额是nums[0]
        if length == 1:
            return nums[0]

        #边界条件
        first, second = nums[0], max(nums[0], nums[1])

        for i in range(2, length):
            first, second = second, max(first + nums[i], second)

        return second

该算法的时间复杂度是O(n)，空间复杂度是O(1)。

打家劫舍II

问题描述

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b3f9e15d-076d-4f1e-bf75-87fbf84b4aba

示例：

输入：nums = [2,3,2]

输出：3

解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

分析问题

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:82c0efb5-3a28-45c9-8a59-4ef2dfcac042

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e7810c64-a109-4019-a20d-4658c8822309

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:0f24136d-a42c-452f-b438-e7fbe2ce5c7b

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:93faece7-59ad-4cf4-a184-98498586d0cc

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:edfc0ecd-c8c3-473e-872b-b212c4a91218

我们假设数组 nums 的长度为n。如果不偷窃最后一间房屋，则可以偷窃的房屋的下标是0n-2；如果不偷窃第一间房屋，则可以偷窃的房屋的下标是1n-1。

接下来我们就可以采用上一题的解法，对于两段下标范围分别计算可以偷窃到的最高总金额，其中的最大值即为在 n 间房屋中可以偷窃到的最高总金额。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:733e1838-ebe8-4a45-a095-a963df6b86b7

class Solution:
    def rob(self, nums):
        #求nums[start,end]范围内可以偷窃到的最大金额
        def help(start, end):
            first = nums[start]
            second = max(nums[start], nums[start + 1])
            for i in range(start + 2, end + 1):
                first, second = second, max(first + nums[i], second)
            return second

        length = len(nums)
        #边界条件
        if length == 1:
            return nums[0]
        elif length == 2:
            return max(nums[0], nums[1])
        else:
            return max(help(0, length - 2), help(1, length - 1))

该算法的时间复杂度是O(n)，空间复杂度是O(1)。

打家劫舍III

问题描述

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:02343fcb-65f9-45e5-9a1d-1b0de629ad8f

示例：

输入：[3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \
     3   1

输出：7

解释：小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7。

分析问题

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ed41d2f9-a42e-493d-8475-82117c89e5fe

首先我们用f(a)来表示选择a节点的情况下，a节点的子树上被选择的节点的最大权值和。g(a)表示在不选择a节点的情况下，a节点的子树上被选择的节点的最大权值和。l 和 r 分别表示a的左右孩子。

小偷对于树中的每个节点都有偷或者不偷两种选择，假设当前的节点是a。

• 当a被选中时，a的左右孩子都不能被选中，所以a被选中的情况下，它的子树上被选择的节点的最大权值和为l 和 r 不被选中的最大权值和相加，即 f(a) = g(l) + g(r)。
• 当a不被选中时，a的左右孩子可以被选中，也可以不被选中。此时 g(a) = max { f(l) , g(l) } + max{ f(r) , g(r) }。

这里我们可以使用深度优先搜索的办法后序遍历这棵二叉树，就可以得到每一个节点的 f 和 g。根节点的 f和 g 的最大值就是我们要找的答案。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:db553247-8671-40cc-8e18-fa5710b4c1d8

class Solution:
    def __init__(self):
        self.f={}
        self.g={}
    def dfs(self,node):
        if not node:
            return
        self.dfs(node.left)
        self.dfs(node.right)
        #表示选中该节点
        self.f[node]=node.val + self.g.get(node.left,0) + self.g.get(node.right,0)
        #表示没有选择该节点
        self.g[node] = max(self.f.get(node.left,0),self.g.get(node.left,0)) \
                       + max(self.f.get(node.right,0),self.g.get(node.right,0))

    def rob(self, root):
        self.dfs(root)
        return max(self.f.get(root,0),self.g.get(root,0))

该算法的时间复杂度是O(n)，空间复杂度也是O(n)。

这里我们还可以优化一下，因为无论是求 f(a) 还是 g(a)，他们的值只和 f(l) 、g(l)、f(r)和g(r)有关。所以对于每一个节点，我们只关心它的左右孩子的 f 和 g 是多少。在python中，我们可以用元组来表示，每次递归返回的时候，都把这个点对应的 f 和 g 返回给上一级调用。这样我们就可以省去哈希表的空间，下面我们来看一下具体的代码实现。

class Solution:
    def dfs(self,node):
        if not node:
            return (0,0)
        left=self.dfs(node.left)
        right=self.dfs(node.right)
        #表示选中该节点
        selected = node.val + left[1] + right[1]
        #表示没有选择该节点
        noselected = max(left[0],left[1]) \
                       + max(right[0],right[1])
        return (selected,noselected)

    def rob(self, root):
        result=self.dfs(root)
        return max(result[0],result[1])

该算法的时间复杂度是O(n)，空间复杂度也是O(n)。

Original: https://www.cnblogs.com/cxyxz/p/15599580.html
Author: 算法推荐管
Title: 面试常遇的打家劫舍问题你学会了吗~