您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【LeetCode】Day51-打家劫舍 III

题目1

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<n;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)

题目2

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<end;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)

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


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进