最新公告
  • 欢迎您光临网站无忧模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 【算法题】打家劫舍

    正文概述 掘金(Axie)   2021-02-12   523

    个人觉得,学、思、练三者是相辅相成的关系,既然已经学习了动态规划,就拿力扣上的题来练下手吧! leetcode-cn.com/problems/ho…

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

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

    示例 1:

    输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。   偷窃到的最高金额 = 1 + 3 = 4 。 示例 2:

    输入:[2,7,9,3,1] 输出:12 解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

    思路分析:

    针对每一个房屋,有2种选择:偷、不偷

    如果现在有房子编号为0,1,2,3,4,5

    如果偷第0号房子,sum1 = nums[0] + rob([2,3,4,5])

    如果不偷第0号房子

    sum2 = rob([1,2,3,4,5]) 偷到的最高金额应为二者中的最大值max(sum1,sum2)

    思路一:递归(从前往后偷,从第一个偷或不偷开始)

    var rob = function(nums) {
        if(nums == null || nums.length == 0) return 0;
        return robFn(nums,0);
    
    };
    function robFn(nums,begin){
        // begin 是从0开始逐渐变大,加上这句,避免下标超过数组长度而越界,也是递归基。
        if(begin == nums.length - 1) return nums[begin];
        if(begin == nums.length - 2) return Math.max(nums[begin], nums[begin+1]);
        let sum1 = nums[begin] + robFn(nums, begin+2) //偷begin
        let sum2 = robFn(nums, begin+1) //不偷begin
        return Math.max(sum1, sum2)
        
    }
    

    思路二:递归(从后往前偷,从最后一个偷或不偷开始)

    var rob = function(nums) {
        if (nums == null || nums.length == 0) return 0;
        return robFn(nums, nums.length - 1);
    };
    function robFn(nums, begin) {
        if (begin == 0) return nums[0];
        if (begin == 1) return Math.max(nums[0], nums[1]) //避免下标成为负数而越界
        let sum1 = nums[begin] + robFn(nums, begin - 2);//偷begin
        let sum2 = robFn(nums, begin - 1);//不偷begin
        return Math.max(sum1, sum2)
    
    }
    

    思路三:缓存(从后往前偷,从最后一个偷或不偷开始)

    var rob = function(nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];//加上这句,nums至少有2个数据才会往下走,就不会报错了(NaN),这句一可以提高效率,二可以避免报错。
        let arr = new Array(nums.length);//arr[begin]存放从begin开始往前偷的最大数
        arr[0] = nums[0];
        arr[1] = Math.max(nums[0], nums[1]);
        for (let begin = 2; begin < nums.length; begin++){
            arr[begin] = Math.max(nums[begin] + arr[begin - 2], arr[begin - 1]);
        }
        return arr[arr.length - 1]
    
    };
    

    思路四:优化从简复杂度,从O(n)到O(1)(从后往前偷,从最后一个偷或不偷开始)

    var rob = function (nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];//加上这句,nums至少有2个数据才会往下走,就不会报错了(NaN),这句一可以提高效率,二可以避免报错。
        let first = nums[0], second = Math.max(nums[0], nums[1]);
        for (let begin = 2; begin < nums.length; begin++) {
            let tmp = second;
            second = Math.max(nums[begin] + first, second);
            first = tmp;
        }
        return second;
    
    };
    

    再次优化

    var rob = function (nums) {
        if (nums == null) return 0;
        let first = 0, second = 0;
        for (let begin = 0; begin < nums.length; begin++) {
            let tmp = second;
            second = Math.max(nums[begin] + first, second);
            first = tmp;
        }
        return second;
    
    };
    

    我的独创:空间复杂度0

    var rob = function (nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length >= 2) nums[1] = Math.max(nums[0], nums[1]);
        for (let i = 2; i < nums.length; i++) {
            nums[i] = Math.max(nums[i] + nums[i - 2], nums[i - 1])
        }
        return nums[nums.length - 1]
    };
    

    下载网 » 【算法题】打家劫舍

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元