Ricky.L的随笔
0%

LeetCode.213.打家劫舍 II（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.213.打家劫舍 II（中等）

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

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

题解

环形排列影响了什么？

第1间房子和最后一间房子只能偷一个，不知道偷哪个金额最高。

不知道偷第一间还是最后一间，怎么办？

两种情况都偷一下，取金额大的那个方案。即：

  1. 偷第1间房子，不偷最后一间房子
  2. 不偷第1间房子，偷最后一间房子

转换为两个非环问题取较大值的问题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    fun rob(nums: IntArray): Int {
        val n = nums.size
        if (n == 0) return 0
        if (n == 1) return nums[0]
        return maxOf(
            linearRob(nums.copyOfRange(0, n - 1)),
            linearRob(nums.copyOfRange(1, n))
        )
    }

    fun linearRob(nums: IntArray): Int {
            val n = nums.size
            if (n == 0) return 0
            if (n == 1) return nums[0]
            var pre2 = nums[0]
            var pre1 = maxOf(nums[0], nums[1])
            var cur = pre1
            for (i in 2 until n) {
                cur = maxOf(pre1, pre2 + nums[i])
                pre2 = pre1
                pre1 = cur
            } 
            return cur
    }
}