外贸公司网站建设哪家好,网站的推广优化,旅游网站源码免费下载,做网站可以用php吗题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer#xff08;专项突击版#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
一个专业的小偷#xff0c;计划偷窃一个环形街道上沿街的房屋专项突击版系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
一个专业的小偷计划偷窃一个环形街道上沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组 nums 请计算 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
示例 1
输入nums [2,3,2]输出3解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。
示例 2
输入nums [1,2,3,1]输出4解释你可以先偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。偷窃到的最高金额 1 3 4 。
示例 3
输入nums [0]输出0
提示
1 nums.length 1000 nums[i] 1000
题目思考
如何处理环形街道首尾相连的问题?
解决方案
分析题目, 不难发现这道题和上一道题目(Leetcode 剑指 Offer II 089. 打家劫舍)非常类似, 只是多了个环形街道首尾相连的条件, 那能否沿用之前的做法呢?答案是肯定的, 既然不能同时偷开头和结尾, 那我们可以分两次计算, 先排除开头, 再排除结尾, 然后取两者偷窃金额的较大值即可这样具体计算过程就可以使用之前的动态规划思路了, 这里就不再重复说明了, 不熟悉的同学可以回去看上一道题目(Leetcode 剑指 Offer II 089. 打家劫舍)另外这里存在一个问题, 假如只有一个房屋, 那么两次计算都计算的是空列表, 最后会错误地得到 0, 所以我们需要特殊判断这种情况, 如果只有一个房屋就直接偷它, 返回其金额即可下面的代码中有详细的注释, 方便大家理解
复杂度
时间复杂度 O(N): 需要遍历整个数组两遍空间复杂度 O(1): 只需要几个常数空间的变量
代码
class Solution:def rob(self, nums: List[int]) - int:# 两次动态规划特殊处理单个房屋n len(nums)if n 1:# 只有一个房屋, 直接偷它return nums[0]def getMax(s, e):# 初始化ppre和pre都为0, 代表没偷时的金额ppre, pre 0, 0for i in range(s, e 1):x nums[i]# 当前dp值是pprex和pre的较大值# 然后滚动更新ppre和preppre, pre pre, max(pre, ppre x)# 最终结果就是pre, 最后一个dp值return prereturn max(getMax(0, n - 2), getMax(1, n - 1))大家可以在下面这些地方找到我~ 我的 GitHub 我的 Leetcode 我的 CSDN 我的知乎专栏 我的头条号 我的牛客网博客 我的公众号: 算法精选, 欢迎大家扫码关注~
