打家劫舍-ii

Tips

题目类型: Dynamic Programming

题目

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

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

示例

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

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

题解

本题 helper 函数跟第 198. 打家劫舍 一致, 但由于有环, 意味着第一家和最后一家仅且偷一家, 即偷第一家到倒数第二家, 或者偷第二家到最后一家, 换算成索引就是从 0 到 n - 1, 或者从 1 到 n.

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const n = nums.length
  if (n === 0) return 0
  if (n === 1) return nums[0]

  return Math.max(helper(nums, 0, n - 1), helper(nums, 1, n))
}

var helper = (nums, left, right) => {
  let rob = 0,
    notRob = 0
  for (let i = left; i < right; i++) {
    let temp = rob
    rob = notRob + nums[i]
    notRob = Math.max(temp, notRob)
  }
  return Math.max(rob, notRob)
}

Rust

use std::cmp;

pub fn rob(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    if n == 0 {
        return 0;
    };
    if n == 1 {
        return nums[0];
    };

    cmp::max(helper(&nums, 0, n - 1), helper(&nums, 1, n))
}

fn helper(nums: &Vec<i32>, left: usize, right: usize) -> i32 {
    let mut rob = 0;
    let mut not_rob = 0;

    for i in left..right {
        let temp = rob;
        rob = not_rob + nums[i];
        not_rob = cmp::max(temp, not_rob);
    }

    cmp::max(rob, not_rob)
}