【LeetCode】213、打家劫舍II

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

213、House Robber II打家劫舍II

难度：中等

题目描述

  • 英文：

    You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

    Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

  • 中文：

    你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

    给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

  • 示例

    Example 1:

    1
    2
    3
    4
    5
    6
    7
    8
    Input: [2,3,2]
    Output: 3
    Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
                 because they are adjacent houses.

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

    Example 2:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    Input: [1,2,3,1]
    Output: 4
    Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
                 Total amount you can rob = 1 + 3 = 4.

    输入: [1,2,3,1]
    输出: 4
    解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
         偷窃到的最高金额 = 1 + 3 = 4 。

解题思路

思路一

相比“打家劫舍I”多了首尾不能相连的限制，可以通过对1~n-1和2~n两个序列分别按“打家劫舍I”的思路计算一遍，最后取最大值返回即可。

顺序遍历整个数组，当遍历到第i个值时，有两种情况：

  1. 之前遍历过程中的curSum始终大于0，假设当前子序列为a,a+1,a+2,...,b-2,b-1,b，此时考虑所有可能：

    • 以当前子序列开头为开头，以中间任一处结尾的序列，如a,a+1,a+2,...b-2：这种情况一致在遍历过程中保存更新；
    • 以当前子序列结尾为结尾，以中间任一处开头的序列，如a+2,...,b-2,b-1,b：这种情况一定小于当前的完整子序列的和，因为前面缺失的部分的和一定是大于0的（讨论的前提就是遍历过程加和始终大于0）；
    • 以中间元素为开头和结尾的序列，如a+2,...,b-2：这种情况，首先按照前一条讨论，补全前面缺失的部分，之后就变成了第一条讨论的情况；

    也就是说，i前面的所有可能序列情况都已经考虑到了；

  2. curSum出现小于0的情况，此时由于已遍历过的连续子序列加和<0，则遍历过的这个连续子序列不能完整的被包含到新形成的序列中了；而是否要全部放弃，还是保留末尾的部分元素？参考之前的讨论，以当前子序列结尾为结尾，以中间任一处开头的序列的加和是小于完整子序列的，也就是说是<0的，因为此时遍历过的连续子序列需要全部放弃，即curSum置0，并重新开始累加。

其中，每次curSum<0时的下一位置即为和最大的子序列的开始，每次curSum>maxSum时的位置即为和最大的子序列的结尾。

代码提交

Python3，用时56ms，内存13.2M

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def rob1(self, nums):
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        
        temp = [nums[0], max(nums[0], nums[1])]
        for i in range(2, len(nums)):
            temp.extend([max(temp[i-1], temp[i-2]+nums[i])])
        return temp[-1]
    
    def rob(self, nums):
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        return max(self.rob1(nums[1:]), self.rob1(nums[:-1]))
-------------本文结束感谢您的阅读-------------
0%