共计 619 个字符,预计需要花费 2 分钟才能阅读完成。
- 题目要求:
-
思路:
- 如果抢第一个房屋,就不能抢最后一个房屋,抢最后一个房屋,就不能抢第一个房屋,所以把 nums 分为两种情况,一部分是 nums[:-1] 和 nums[1:],遍历这两个数组,再比较抢来的最高金额
- 到达当前房屋能抢到的最大金额是,(抢当前房屋,那么就不能抢前一个房屋)和(不抢当前房屋,可以抢前一个房屋)
- 也就是(当前房屋的金额 + 到前前个房屋抢来的最高金额)和(到前一个为止,抢到的最大金额)
- 核心代码:
pre1, cur1 = 0, 0
for i in nums[:-1]:
pre1, cur1 = cur1, max(pre1 + i, cur1)
pre2, cur2 = 0, 0
for j in nums[1:]:
pre2, cur2 = cur2, max(pre2 + j, cur2)
return max(cur1, cur2)
-
完整代码:
- 如果数组为空,抢来的最高金额为 0
- 如果数组长度为 1,那么抢来的最高金额为 nums[0]
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
pre1, cur1 = 0, 0
for i in nums[:-1]:
pre1, cur1 = cur1, max(pre1 + i, cur1)
pre2, cur2 = 0, 0
for j in nums[1:]:
pre2, cur2 = cur2, max(pre2 + j, cur2)
return max(cur1, cur2)
正文完