每日一道算法题（二）

题目来源：213. 打家劫舍 II - 力扣（LeetCode）

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

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

想法就是看第一个房间偷不偷了

如果偷的话，那最后一个就不能偷，即队列为第一个房间到倒数第二个

如果不偷的话，最后一个可以偷，即队列为第二个房间到倒数第一个

代码编写如下：

 int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        if (n == 2) return (nums[0] > nums[1]) ? nums[0]  : nums[1] ;
        if (n == 3) 
        {
            if (nums[0] > nums[1])return (nums[0] > nums[2]) ? nums[0]  : nums[2] ;
            else return (nums[1] > nums[2]) ? nums[1]  : nums[2] ;

        }
           
        //仅用两个变量保存即可
        int a=nums[0];
        int b=max(nums[0],nums[1]);

        int c=nums[1];
        int d=max(nums[1],nums[2]);
        int temp1,temp2;
  
        for(int i=2;i<n-1;i++)
        {
            
            temp1=max(a+nums[i],b);
            a=b;
            b=temp1;
        }
        for(int i=3;i<n;i++)
        {
            
            temp2=max(c+nums[i],d);
            c=d;
            d=temp2;
        }

        return (temp1 > temp2) ? temp1   : temp2 ;
    }

刚开始如果不考虑三个房间的情况，就会发生报错，得加进特殊情况处理，后来就通过了。

优化一下代码，合为一个循环：

int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        if (n == 2) return (nums[0] > nums[1]) ? nums[0]  : nums[1] ;
        if (n == 3) 
        {
            if (nums[0] > nums[1])return (nums[0] > nums[2]) ? nums[0]  : nums[2] ;
            else return (nums[1] > nums[2]) ? nums[1]  : nums[2] ;

        }

        //仅用两个变量保存即可
        int a=nums[0];
        int b=max(nums[0],nums[1]);

        int c=nums[1];
        int d=max(nums[1],nums[2]);
        int temp1,temp2;
  
        for(int i=2;i<n-1;i++)
        {
            
            temp1=max(a+nums[i],b);
            a=b;
            b=temp1;
            temp2=max(c+nums[i+1],d);
            c=d;
            d=temp2;
        }
        
        return (temp1 > temp2) ? temp1   : temp2 ;
    }

应该还可以在优化，但我觉得已经可以了