149 - 213 打家劫舍2

题目

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

输入: [1,2,3,1] 输出: 4 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。

解答

https://leetcode-cn.com/problems/house-robber-ii/solution/213-da-jia-jie-she-iidong-tai-gui-hua-jie-gou-hua-/

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums or len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]

        def helper(nums):
            cur, pre = 0, 0
            for i in nums:
                cur, pre = max(pre+i, cur), cur
            return cur
        return max(helper(nums[:-1]), helper(nums[1:]))

Runtime: 28 ms, faster than 95.53% of Python3 online submissions for House Robber II.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for House Robber II.

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}
func rob(nums []int) int {
    if nums == nil || len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }
    helper := func(arr []int) int {
        var pre, cur int
        for _, v := range arr {
            cur, pre = max(pre+v, cur), cur
        }
        return cur
    }
    return max(helper(nums[:len(nums)-1]), helper(nums[1:]))
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for House Robber II.

Memory Usage: 2 MB, less than 100.00% of Go online submissions for House Robber II.

var rob = function(nums) {
  if (!nums || nums.length === 0) {
    return 0
  }
  if (nums.length === 1) {
    return nums[0]
  }
  const helper = function(nums) {
    let cur = 0,
      pre = 0
    nums.forEach(e => {
      [cur, pre] = [Math.max(pre + e, cur), cur]
    })
    return cur
  }
  const first = nums.slice(1)
  nums.pop()
  return Math.max(helper(nums), helper(first))
};

Runtime: 48 ms, faster than 93.93% of JavaScript online submissions for House Robber II.

Memory Usage: 34.6 MB, less than 33.33% of JavaScript online submissions for House Robber II.

var rob = function(nums) {
  if (!nums || nums.length === 0) {
    return 0
  }
  if (nums.length === 1) {
    return nums[0]
  }
  const helper = function(nums) {
    let cur = 0,
      pre = 0
    for (const i of nums) {
      let tmp = cur
      cur = Math.max(pre + i, cur)
      pre = tmp
    }
    return cur
  }
  const first = nums.slice(1)
  nums.pop()
  return Math.max(helper(nums), helper(first))
};

Runtime: 60 ms, faster than 30.34% of JavaScript online submissions for House Robber II.

Memory Usage: 33.8 MB, less than 66.67% of JavaScript online submissions for House Robber II.