- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/house-robber-ii/description/
Youare 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:
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.
Example 2:
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.
这个是198. House Robberopen in new window的拓展。本题目里面的房间是一个环的,也就是说第一个房子和最后一个房子是相邻的。在这种情况下,相邻的两个房子不能一起偷,求能偷到的金额的最大值。
这个题多了环的条件,在这个约束下就多了个不同时偷第一个和最后一个就可以了。所以,两种偷的情况:第一种不偷最后一个房间,第二种不偷第一个房间,求这两种偷法能获得的最大值。所以只多了一个切片的过程。
状态转移方程仍然是:
dp[0] = num[0] (当i=0时)
dp[1] = max(num[0], num[1]) (当i=1时)
dp[i] = max(num[i] + dp[i - 2], dp[i - 1]) (当i !=0 and i != 1时)
第三个式子就是当前的房间偷的情况和不偷情况下的最大值。
时间复杂度是O(N),空间复杂度是O(N). (Beats 98%.)
代码如下:
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
if len(nums) == 1: return nums[0]
if len(nums) == 2: return max(nums[0], nums[1])
N = len(nums)
return max(self.rob_range(nums[0 : N - 1]), self.rob_range(nums[1 : N]))
def rob_range(self, nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
if len(nums) == 2: return max(nums[0], nums[1])
N = len(nums)
dp = [0] * N
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, N):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
参考资料:
http://www.cnblogs.com/grandyang/p/4518674.html
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我正在为即将到来的实际编程测试练习,所以一直在网上浏览示例并遇到了这个 “编写一个函数 translate() 将文本翻译成“rövarspråket”(瑞典语“强盗的语言”)。也就是说,将每个辅音加
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开,visit the help center . 关闭 1
题目地址:https://leetcode.com/problems/house-robber-iii/description/ 题目描述 Thethief has found himself a
题目地址:https://leetcode.com/problems/house-robber-ii/description/ 题目描述: Youare a professional robber
我已经解决了LeetCode's "House Robber" problem ,但我无法打印路径。我尝试了一些使用列表的技巧,但总是得到错误的答案。我如何记住之前的决定并删除元素并将元素添加到列表以
我是一名优秀的程序员,十分优秀!