Leetcode-213. 打家劫舍 II

Posted on In Views: Disqus:
Leetcode刷题系列.

描述

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

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：213. House Robber II

解题思路

这道题是Leetcode-198. 打家劫舍的延伸, 主要的区别就是头尾两间房子连到了一起, 给解题增加了一定的难度. 不过这个难度非常有限.

既然头尾两间房子连到了一起, 那么就是意味着不能够同时抢劫A1A_1和 AnA_n两间房子, 问题可以等价于从[1, n-1]或者[2, n]的房子序列当中哪个序列能够抢到最多的钱. 这相当于两个已经解决的Leetcode-198. 打家劫舍的小问题, 分别求出在上述两个序列当中能够抢到的钱的最大值, 然后取其中的较大者. 另外, 还要考虑下特殊情况, 当只有一间房子的时候直接返回数组元素.

具体代码如下:

代码

解法一

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
27
28
29
#define max(a, b) ((a)>(b)?(a):(b))


int robhelp(int* nums, int numsSize)
{
    
    int max1 = 0, max2 = 0;

    for(int i = 0; i < numsSize; i++)
    {
        int tmp = max2;
        max2 = max(max1 + nums[i], max2);
        max1 = tmp;
    }
    
    return max2;

}

int rob(int* nums, int numsSize)
{
    if(numsSize == 1) return nums[0];
    
    int max1 = robhelp(nums, numsSize - 1);
    int max2 = robhelp(nums+1, numsSize - 1);
    
    return max(max1, max2);
}

解法二

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
27
28
29
30
31
32
#define max(a, b) ((a)>(b)?(a):(b))

int robhelp(int* nums, int numsSize) 
{
    int robEven = 0;
    int robOdd = 0;
    
    for (int i = 0; i< numsSize; i++)
    {
        if (i % 2 == 0)
        {
            robEven = max(robEven + nums[i], robOdd);
        }
        else
        {
            robOdd = max(robEven, robOdd + nums[i]);
        }
    }
    
    return max(robOdd, robEven);
}


int rob(int* nums, int numsSize)
{
    if(numsSize == 1) return nums[0];
    
    int max1 = robhelp(nums, numsSize - 1);
    int max2 = robhelp(nums+1, numsSize - 1);
    
    return max(max1, max2);
}

参考