#92 专业盗贼


  • 0

    @zhouyu 这个函数写的真漂亮


  • 0

    const rob = ((data = []) => {
        const task = nums => {
            const doPlus = (value, index) => {
                if (index >= nums.length) {
                    data.push(value)
                    return
                }
                value += nums[index]
                doPlus(value, index + 2)
                doPlus(value, index + 3)
            }
            doPlus(0, 0)
            doPlus(0, 1)
            return data.sort((a, b) => {
                return b - a
            })[0]
        }
        return task
    })()
    

    这个代码在[3,4,5,6,7]的时候为什么本地用node跑出来结果是正确的15,提交的时候却提示我结果是16,错误了,有大神能讲解一下嘛


  • 0

    这题好难,答案的过程在纸上画了下,虽然能理解过程中的运算,但是答案本身一头雾水,真是厉害,希望有人贴出完整解题思路。


  • 2

    @剪云者
    简单的动态规划问题, 主要在于状态转移.

    每个房子能否偷取决于前一个房子是否被偷过. 当我们想知道i个房子最多能偷多少钱时, 可以分为两种情况:

    1. 如果想偷房子i, 需要知道不偷i - 1时前i - 1个房子最多能偷多少, 也就是偷前i - 2个. 知道偷前i - 2个最多偷多少, 然后加上第i个房子的钱数, 就是偷i时最多的钱数.
    2. 如果不偷i, 那最多的钱数就是偷前i - 1个房子能偷到的最多的钱.

    保留两种情况的更优解, 就是i个房子最多能偷到多少钱的答案.

    因此我们可以通过i - 2i - 1个房子的最优解推i个房子的最优解, 当我们知道i = 0i = 1是的解时(都是显而易见的答案), 就可以依次往后推导了.


  • 0

         computerMax(arr)function{
                  var _left = 0,_right=0;
    	      for(var i=0;i<arr.length;i++){
                       if(String(i/2).indexOf(".")>-1){
    		          _left += arr[i]
    	           }else{
    			  _right += arr[i] 
    		  }
    		}
    
    		return  _left>_right?_left:_right
    	}

  • 0

    function maxTotal(left, right) {
      var total;
      total = left >= right ? left : right;
      return total;
    }
    const rob = (nums) => {
      var n = nums.length;
      var totalNum = [];
      totalNum[0] = 0;
      totalNum[1] = nums[0];
      totalNum[2] = maxTotal(nums[0], nums[1]);
      for (var i = 2; i< n; i++) {
        totalNum[i+1] = maxTotal(totalNum[i-1]+nums[i], totalNum[i]);
      }
      return totalNum[n];
    }
    

  • 0

    @bedodo 兄弟你好歹测试过再发出来啊


  • 0

    状态转移方程自己都没完全想清楚,一点提交居然AC了。。。
    两个数组a,b,i为当前位置,a[i],b[i]分别表示抢这个房子和不抢这个房子时能得到的最大金额,那么
    a[i] = max(b[i-1]+nums[i], a[i-1])
    b[i] = max(b[i-1], a[i-1])
    代码就简单了

    const rob = (nums) => {
      var l = nums.length;
      if (!l) {
        return 0;
      }
      if (l === 1) {
        return nums[0];
      }
      var a = [nums[0]];
      var b = [0];
      for (var i=1; i<l; i++) {
        a[i] = Math.max(b[i-1]+nums[i], a[i-1]);
        b[i] = Math.max(b[i-1], a[i-1]);
      }
      return Math.max(a[l-1], b[l-1])
    }
    

  • 0

    函数式能行?(dp 无递归

    const rob = nums => nums.reduce((info, n) => [info[1], Math.max(info[0] + n, info[1])], [0, 0])[1];
    

  • 0

    根据@ST_Lighter 的提示实现

    const rob = (nums) => {
      var dp = [];
      if(nums.length == 0){
        return 0;
      }
      nums.map((item, index) => {
        if(index == 0){
          dp[index] = item;
        }else if (index == 1){
          dp[index] = Math.max(nums[0], nums[1]);
        }else{
          dp[index] = Math.max(dp[index - 2] + nums[index], dp[index - 1]);
        }
      });
      return dp[nums.length - 1];
    }
    

登录后回复
 

与 ScriptOJ 的连接断开,我们正在尝试重连,请耐心等待