213. House Robber II
你是一名專業強盜，計劃搶劫沿街的房屋。每個房屋藏有一定數量的金錢。在這個地方，所有房屋呈圓形排列，這意味著第一間房屋是最後一間房屋的鄰居。同時，相鄰的房屋有一個安全系統連接，如果同一晚上有兩間相鄰的房屋被闖入，它會自動聯繫警察。
給定一個整數數組 nums，表示每個房屋的金錢數量，返回今晚在不驚動警察的情況下可以搶劫的最大金額。
範例：
輸入：nums = [2,3,2] 輸出：3 解釋：你不能搶劫第1間房屋（金錢 = 2），然後搶劫第3間房屋（金錢 = 2），因為它們是相鄰的房屋。
Python
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
def rob_linear(houses):
prev = curr = 0
for money in houses:
prev, curr = curr, max(curr, prev + money)
return curr
# Case 1: Rob houses from 0 to n-2 (not including the last house)
case1 = rob_linear(nums[:-1])
# Case 2: Rob houses from 1 to n-1 (not including the first house)
case2 = rob_linear(nums[1:])
return max(case1, case2)
16.56MB, 35ms
C++
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
// Helper function to calculate the maximum amount of money that can be robbed
// from a linear arrangement of houses.
auto rob_linear = [](vector<int>& houses) {
int prev = 0, curr = 0;
for (int money : houses) {
int temp = max(curr, prev + money);
prev = curr;
curr = temp;
}
return curr;
};
// Case 1: Rob houses from 0 to n-2 (not including the last house)
vector<int> case1(nums.begin(), nums.end() - 1);
int max1 = rob_linear(case1);
// Case 2: Rob houses from 1 to n-1 (not including the first house)
vector<int> case2(nums.begin() + 1, nums.end());
int max2 = rob_linear(case2);
return max(max1, max2);
}
};
9.72MB, 4ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
const robLinear = (houses) => {
let prev = 0, curr = 0;
for (const money of houses) {
let temp = Math.max(curr, prev + money);
prev = curr;
curr = temp;
}
return curr;
};
// Case 1: Rob houses from 0 to n-2 (not including the last house)
const case1 = robLinear(nums.slice(0, nums.length - 1));
// Case 2: Rob houses from 1 to n-1 (not including the first house)
const case2 = robLinear(nums.slice(1));
return Math.max(case1, case2);
};
49.20MB, 50ms
