House Robber I, II

发表于 | 分类于 | |

198. House Robber

题目描述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

题目大意

小偷打算在街上抢劫房屋，每户都会存放一定数额的现金，以nums表示，唯一的限制是，如果每相邻的两家同一晚上被盗就会自动联系警察。求今晚能偷到的最大金额

解题思路

动态规划
根据下标将数组分为奇数和偶数，以此确保两个相邻的不会被偷，设奇数和偶数变量分别为even、odd。
even表示打劫到奇数下标时所能累计的最大值，odd亦然。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    func rob(_ nums: [Int]) -> Int {
        var even = 0
        var odd = 0
        for i in 0..<nums.count {
            if i % 2 == 0 {
                even = max(even + nums[i], odd)
            }else {
                odd = max(odd + nums[i], even)
            }
        }
        return max(even, odd)
    }
}

213. House Robber II

题目描述

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

题目大意

House Robber的扩展，小偷找到新的目标，但是这条街上所有的房屋是环形，即第一个房屋和最后一个房屋是相邻，警报的规则同House Robber相同。

解题思路

具体实现思路与House Robber
不同的是需要把第一个数从数组中移除，数组记为nums1；最后一个从数组中移除，数组记为nums2。如此才能保证第一个房屋和最后一个房屋不同时被偷。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    func rob(_ nums: [Int]) -> Int {
        func auxiliary(nums: [Int]) -> Int {
            var even = 0
            var odd = 0
            for i in 0..<nums.count {
                if i % 2 == 0 {
                    even = max(even + nums[i], odd)
                }else {
                    odd = max(odd + nums[i], even)
                }
            }
            return max(even, odd)
        }
        if nums.count == 1 { return nums[0] }
        if nums.count == 0 { return 0 }
        var nums1 = nums
        var nums2 = nums
        nums1.removeFirst()
        nums2.removeLast()
        return max(auxiliary(nums: nums1), auxiliary(nums: nums2))
    }
}
0%