leetcode213打家劫舍II

缺乏、安全感 2021-11-23 04:54 245阅读 0赞

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

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

示例 1:

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

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

error: 有一种情况没考虑到，那种情况下，从0,或者从1,开始，但是最后一个环状引起的情况。

解决很棘手的，于是多数情况下，遍历2遍。0-n-1.1-n.比较谁最大即可。

*  第一种情况：第一间打劫，最后一天不打劫(也就是不用考虑最后一间房屋)
 *  第二种情况：第一间不打劫，最后一天打劫或者不打劫

\[1,2,1,1\]

输出：2

预期：3

class Solution {
        public int rob(int[] nums) {
            
            if(nums.length<=0)
                return 0;
            
            if(nums.length==1)
                return nums[0];
            
            if(nums.length==2){
                return nums[0]>nums[1]?nums[0]:nums[1];
            }
            
            int[] numbers1 = new int[nums.length-1];
             int[] numbers2 = new int[nums.length-1];
            
            numbers1[0] = nums[0];
            numbers1[1] = Math.max(numbers1[0],nums[1]);
            numbers2[0] = nums[1];
            numbers2[1] = Math.max(numbers2[0],nums[2]);
         
           
            for(int n=2;n<nums.length-1;n++){
        
                
            numbers1[n] = Math.max(numbers1[n-1],numbers1[n-2]+nums[n]);
            numbers2[n] = Math.max(numbers2[n-1],numbers2[n-2]+nums[n+1]);    
                
                
            }
            
         
            
            return Math.max(numbers1[nums.length-2],numbers2[nums.length-2]);
            
        }
    }