213. 打家劫舍 II
题目描述
若干间房子排成一个环，nums[i] 是第 i 间房子里的现金，都是非负整数。由于是环形，第一间与最后一间也相邻。
相邻房子的防盗系统相连：同一晚闯入任意两间相邻房子都会报警。
在不报警的前提下，返回今晚最多能偷到多少钱。
示例 1
输入：nums = [2,3,2] 输出：3
解释：第 1 间和第 3 间首尾相邻，不能同时偷，只偷中间的 3 最好。
示例 2
输入：nums = [1,2,3,1] 输出：4
解释：偷第 1 间和第 3 间，共 1 + 3 = 4。
示例 3
输入：nums = [1,2,3] 输出：3
解释：三间两两相邻，只能偷一间，最多拿 3。
数据范围
1 <= nums.length <= 1000 <= nums[i] <= 1000
解题思路
环的麻烦只在于首尾不能同时选。分两种情况：不偷最后一间（只看 nums[0..n-2]），或不偷第一间（只看 nums[1..n-1]）。两种情况都变成一排房子的打家劫舍，用滚动变量 a、b 分别表示“到前前一间”和“到前一间”的最优值，答案取两者较大值。只有一间房时直接返回它。
为什么正确
处理完第 i 间后，b 是这一排中到第 i 间为止的最大金额，a 是到第 i-1 间为止的最大金额。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
只有一间房时，两排都是空的，会得到 0，必须特判返回 nums[0]。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def rob(self, nums: List[int]) -> int:
def line(lo, hi):
a, b = 0, 0
for i in range(lo, hi):
a, b = b, max(b, a + nums[i])
return b
if len(nums) == 1:
return nums[0]
return max(line(0, len(nums) - 1), line(1, len(nums)))class Solution {
int line(int[] nums, int lo, int hi) {
int a = 0, b = 0;
for (int i = lo; i < hi; i++) {
int c = Math.max(b, a + nums[i]);
a = b;
b = c;
}
return b;
}
public int rob(int[] nums) {
if (nums.length == 1)
return nums[0];
return Math.max(line(nums, 0, nums.length - 1), line(nums, 1, nums.length));
}
}class Solution {
public:
int line(vector<int>& nums, int lo, int hi) {
int a = 0, b = 0;
for (int i = lo; i < hi; i++) {
int c = max(b, a + nums[i]);
a = b;
b = c;
}
return b;
}
int rob(vector<int>& nums) {
if (nums.size() == 1)
return nums[0];
return max(line(nums, 0, nums.size() - 1), line(nums, 1, nums.size()));
}
};func rob(nums []int) int {
line := func(lo, hi int) int {
a, b := 0, 0
for i := lo; i < hi; i++ {
a, b = b, max(b, a+nums[i])
}
return b
}
if len(nums) == 1 {
return nums[0]
}
return max(line(0, len(nums)-1), line(1, len(nums)))
}var rob = function(nums) {
const line = (lo, hi) => {
let a = 0, b = 0;
for (let i = lo; i < hi; i++) {
[a, b] = [b, Math.max(b, a + nums[i])];
}
return b;
};
if (nums.length === 1)
return nums[0];
return Math.max(line(0, nums.length - 1), line(1, nums.length));
};function rob(nums: number[]): number {
const line = (lo: number, hi: number): number => {
let a = 0, b = 0;
for (let i = lo; i < hi; i++) {
[a, b] = [b, Math.max(b, a + nums[i])];
}
return b;
};
if (nums.length === 1)
return nums[0];
return Math.max(line(0, nums.length - 1), line(1, nums.length));
}