題目網址：https://leetcode.cn/problems/house-robber-ii/

題意：你是一名專業的強盜, 計劃搶劫沿街的房屋。每棟房子都藏有一定數量的錢。所有的房子都排成一圈。這意味著第一棟房子是最後一棟的鄰居。同時, 相鄰的房屋都連接了安全系統, 如果同一晚上有兩間相鄰的房屋被闖入，它會自動報警。

給定一個整數 array nums, 表示每棟房子的金額, 返回在不報警的情況下搶劫的最大金額。

Solution：

想法：跟 198. House Robber 類似, 只是首尾相連, 如果搶了第一家，就不能搶最後一家, 所以第一家和最後一家只能搶其中的一家, 或者都不搶。 所以把第一家和最後一家分別去掉, 各算一遍能搶的最大值, 然後比較兩個值取其中較大的一個即為所求

class Solution {
public:
    int rob(vector<int>& nums) {
        const int n = nums.size();
        if (n <= 1) {
            return nums.empty() ? 0 : nums[0];
        }
        return max(helper(nums, 0, n - 2), helper(nums, 1, n - 1));
    }

private:
    int helper(vector<int>& nums, const int left, const int right){
        int one = 0, two = 0;
        for (int i = left; i <= right; ++i) {
            const int curMax = max(one, two + nums[i]);
            two = one;
            one = curMax;
        }
        return one;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間