Leetcode 198,213 ,337 打家劫舍套题

Leetcode 198

最初的就是考虑一维的dp,代码实现如下

class Solution {

 public static int rob(int[] nums) {
        if(nums==null||nums.length==0) return 0;
        if(nums.length<=2) return nums.length==1?nums[0]:Math.max(nums[0],nums[1]);
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[1],nums[0]);
        for(int i=2;i<nums.length;i++)
        {
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}

leetcode 213 围成一圈的打家劫舍

图片说明
对于这种情况就需要比较三种情况的大小,但是第一种情况是不需要比较的,因为情况2和情况3都包括了第一种情况,因为,如果不包括两端,但是仍是最大的话,情况2和情况3都是涵盖

class Solution {

    public int rob(int[] nums)
    {
        if(nums==null||nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        if(nums.length==2) return Math.max(nums[0],nums[1]);
        if(nums.length==3) return Math.max(nums[0],Math.max(nums[1],nums[2]));
        int res=rob1(nums,0,nums.length-2);
        int res2=rob1(nums,1,nums.length-1);
        return Math.max(res,res2);
    }

    public int rob1(int[] nums,int start,int end)
    {
        int[] dp=new int[nums.length];
        dp[start]=nums[start];
        dp[start+1]=Math.max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++)
        {
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[end];
    }
}

二叉树的打家劫舍

对于递归的方法就是脱离了上面两种动态规划的规则

暴力

 public int rob(TreeNode root)
    {
        if(root==null) return 0;
        int money=root.val;
        int money2=0;
        if(root.left!=null)
        {
            money+=rob(root.left.left)+rob(root.left.right);
            money2+=rob(root.left);
        }
        if(root.right!=null)
        {
            money+=rob(root.right.left)+rob(root.right.right);
            money2+=rob(root.right);
        }
        return Math.max(money,money2);
        return robWithMemory(root,new HashMap<TreeNode,Integer>());
    }

带记忆的递归

public int robWithMemory(TreeNode root,HashMap<TreeNode,Integer> map)
    {
        if(root==null) return 0;
        if(map.containsKey(root)) return map.get(root);
        int money=root.val;
        int money2=0;
        if(root.left!=null)
        {
            money+=robWithMemory(root.left.left,map)+robWithMemory(root.left.right,map);
            money2+=robWithMemory(root.left,map);
        }
        if(root.right!=null)
        {
            money+=robWithMemory(root.right.left,map)+robWithMemory(root.right.right,map);
            money2+=robWithMemory(root.right,map);
        }
        int curRes=Math.max(money,money2);
        map.put(root,curRes);
        return Math.max(money,money2);
    }

需要注意的点,就是设置map和取map的两个位置,我本来想着在robWithMemory(root.left.left,map)的这些位置都加上取map的操作,后来看到解析,直接
if(map.containsKey(root)) return map.get(root);即可,这儿是需要注意的

时间最快的递归方式

和二叉树有关的,我们就可以想到二叉树的遍历。
当前这道题其实已经和前面两道题都已经脱离开了,对于这一道题来说,我们可以考虑当前位置要不要偷两种情况。
这一道题可以考虑改写二叉树的后序遍历

public static int rob3(TreeNode root)
    {
        if(root==null) return 0;
        int[] f = f(root);
        return Math.max(f[0],f[1]);
    }
    public static int[] f(TreeNode root)
    {
        if(root==null) return new int[]{0,0};
        //res[0]当前位置不偷
        //res[1]当前位置要偷
        int[] res=new int[2];
        int[] left = f(root.left);
        int[] right=f(root.right);

        res[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        res[1]=root.val+left[0]+right[0];
        return res;
    }

每一个节点,都对应这个两个结果,就是偷和不偷,而且上面的节点是依赖于下面的节点的,所以考虑使用后续遍历,得到左右孩子的结果,然后再来处理当前的

全部评论

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
今天 13:16
湖南工学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务