【LeetCode】Day51-打家劫舍 I&II&变形

198. 打家劫舍【中等】

第一道自己动手做出来的动态规划，快哭了

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n];
        dp[0]=nums[0];
        for(int i=1;i
            if(i==1){
                dp[i]=Math.max(dp[i-1],nums[i]);
                continue;
            }
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
}

时间复杂度： O ( n ) O(n) O(n)

空间复杂度： O ( n ) O(n) O(n)，也可以用常数个变量，空间复杂度O(1)

213. 打家劫舍 II【中等】

和上一题的不同是这题中房屋是首尾相连的，即偷了第一家的就不能偷最后一家的，偷了最后一家也不能偷第一家的

重点是如何不同时偷第一家和最后一家呢？

可以通过改变偷的房屋范围来确定：

• 如果要偷第一家，就一定不偷最后一家，那偷的范围可以写成[0，n-2]；
• 如果要偷最后一家，就一定不偷第一家，那偷的范围可以写成[1，n-1]。

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==1)
            return nums[0];
        else if(n==2)
            return Math.max(nums[0],nums[1]);
        return Math.max(dp_rob(nums,0,n-1),dp_rob(nums,1,n));
    }
    //O(1)空间复杂度实现打家劫舍
    public int dp_rob(int[] nums,int start,int end){
        int first=nums[start],second=Math.max(nums[start],nums[start+1]);
        for(int i=start+2;i
            int tmp=second;
            second=Math.max(first+nums[i],second);
            first=tmp;
        }
        return second;
    }
}

时间复杂度： O ( n ) O(n) O(n)

空间复杂度： O ( 1 ) O(1) O(1)

740. 删除并获得点数【中等】

看了题目毫无思路，看了题解豁然开朗，这题是打家劫舍的变形题

不能被同时选择邻居 = 同步删除的 -1 AND +1 元素

所以只需要统计每个数字在数组中出现之和（比如3出现了3次，则sums[3]=9），然后按照打家劫舍的方法，相邻的sums不能选，选最大的点数即可

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n=nums.length,max_num=0;
        for(int i=0;i
            sums[nums[i]]+=nums[i];
        }
        return DP(sums,max_num+1);
    }
    //打家劫舍
    public int DP(int[] sums,int count){
        int first=(sums[0]);
        int second=Math.max(sums[0],sums[1]);
        for(int i=2;i
            int tmp=second;
            second=Math.max(first+sums[i],second);
            first=tmp;
        }
        return second;
    }
}

时间复杂度： O ( n + m ) O(n+m) O(n+m)，m是nums数组中的最大值，即sums数组的大小

空间复杂度： O ( n ) O(n) O(n)

p.s 五一假期过的好快啊，歇了5天，虽然要封校，但是还过的挺快乐的，体会到了不一样的校园生活。今天开始又要学习了，力扣每日一题，加油！