[数据结构与算法]LeetCode每日一题-打家劫舍II

题目

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]

输出：3

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

分析

这是一道典型的动态规划题，同时题目也贴近现实工程，尤其是在分布式领域有一些类似的问题，所以有必要认真对待。

这道题是“打家劫舍1”的升级版(https://leetcode-cn.com/problems/house-robber/),打家劫舍1没有环，只需要考虑从街头到街尾。

先看一下打家劫舍1解题思路， 小偷是每进入一个房子都有两个最终金额：偷与不偷，偷就把当前房子的金额与上上个房子得到的最大金额相加，不偷就表示保留上个房子得到的金额，然后比较这两个金额选择大者当作这个房子能得到的最大收益。

但如果有环呢? 这样首尾的房子就得放弃一个，因为它们防盗系统是相通的。

一开始我的想法是在打家劫舍1的基础上，增加一个状态用于记录最大值是否包含了街首的房子，但代码越来越复杂，尤其是当最大值有包含街首时，需要把街首删除再重算一遍。

这个思路下代码非常多，越写到后面代码越别扭，最后不了了之。

但这个思路也提供了下面的解题思路，就是将数组复制成两个数组，一个数组去掉街头，一个数组去掉街尾。

代码

class Solution {
    public int rob(int[] nums) {
        if(nums.length ==1){
            return nums[0];
        }
        
        int[] nums1 = new int[nums.length-1];
        int[] nums2 = new int[nums.length-1];
        
        //生成两个新数组，长度减1
        System.arraycopy(nums,0, nums1, 0, nums.length-1);
        System.arraycopy(nums,1, nums2, 0, nums.length-1);
        return Math.max(doRob(nums1),doRob(nums2));
    }
    
    public int doRob(int[] nums){
        int res = Integer.MIN_VALUE;
        int[] dp = new int[nums.length+2];
        for(int i=0;i<nums.length;i++){
            dp[i+2] = Math.max(dp[i+1], nums[i]+dp[i]);
            res = Math.max(res, dp[i+2]);
        }
        
        return res;
    }
}

结果

?

关注个人微信公众号：肌肉码农，回复“好友”讨论问题。

?