#92 专业盗贼


  • 0
    administrators

    你是一个盗窃专家,某一天晚上你要去盗窃某一条街道的一排房子。这些房子都有相连的防盗系统,如果你把相邻的两家都偷了那么就会触发报警器。

    用一个数组来表示这些房子的金钱数量,请你完成 rob 函数,计算出在不触发报警器的情况下最多能偷多少钱。例如:

    rob([1, 2, 3]) // => 4
    

  • 0

    const rob = nums => {
        let max = 0
        let l = nums.length
        let cache = {}
    
        function getNextNum(i, sum) {
            let val = nums[i]
            sum += val
            sum = sum || 0
            if (cache[i] >= sum) return
            cache[i] = sum
            if (i >= l - 2) return max = max > sum ? max : sum
            if (i < l - 2) getNextNum(i + 2, sum)
            if (i < l - 3) getNextNum(i + 3, sum)
        }
        getNextNum(-2, 0)
        return max
    }
    console.log(rob([5, 3, 3, 6, 1, 1, 7]))
    console.log(rob([1, 2, 3, 4, 5, 6, 7]))
    console.log(rob([16, 382, 73, 373, 189, 71, 251, 246, 231, 122, 440, 230, 323, 74, 220, 188, 333, 388, 190]))
    

    只想到了递归的笨思路,当然运行超时了……
    等着学习大神的解答~~~


  • 0

    const rob = (nums) => {
    const l = nums.length

    if (l === 0) {
    return 0
    }

    const arr = []

    let i
    let v

    for (i = 0; i < l; i++) {
    v = nums[i]

    arr.push(
      i === 0
      ? v
      : Math.max(arr[i - 1], v + (i === 1 ? 0 : arr[i - 2]))
    )
    

    }

    return arr[l - 1]
    }


  • 2

    from leetcode

    //f(k) = max(f(k – 2) + Ak, f(k – 1))
    const rob = (nums) => {
      let prevMax = 0;
      let curMax = 0;
      nums.forEach(n => {
        let temp = curMax;
        curMax = Math.max(prevMax + n, curMax);
        prevMax = temp;
      })
      return curMax;
    }

  • 0

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

  • 3

    const rob = (nums) => {
      let masterChallenger = 0; //总额数擂主
      let signUped = 0; //报名挑战者
      nums.forEach((item)=>{
        const newChallenger = signUped; //newChallenger是正在参赛的挑战者
        signUped = item + masterChallenger; //更新报名挑战者
        masterChallenger = Math.max(masterChallenger, newChallenger); //比较大小决定新的擂主;
      });
      return Math.max(masterChallenger, signUped); //最后一次报名的挑战者的挑战赛不会在forEach循环中进行,所以手动比一次,并作为结果返回。
    }
    

  • 0

    为什么我这套代码总提醒我“ 输入 [3,4,5,6,7],应该返回 15,但你返回的是 9”。但在node和chrome上都正常呢?

    const rob = ((memo) => {
        const _rob = (nums)=>{
            let n = nums.length
            if(!n) return 0
    
            if(!memo[n-1]){
                if(n===1) memo[0] = nums[0]
                else if(n===2) memo[1] = Math.max(nums[0],nums[1])
                else memo[n-1] = Math.max(_rob(nums.slice(0,-1)), _rob(nums.slice(0,-2))+nums[n-1])
            }
            return memo[n-1]
        }
        return _rob
    })([])
    
    

  • 0

    @ScriptOJ

    const rob = (nums) => {
    let max = 0,flag = true;
    let numsMin5 = () => {
    	nums.length == 0 ? max +=0 : '';
    	nums.length < 3 && nums.length != 0? max += Math.max(...nums) : '';
    	nums.length == 3 ? max += Math.max(nums[1], nums[0] + nums[2]) : '';
    	nums.length == 4 ? max += Math.max(nums[0] + nums[2], nums[0] +   >    nums[3], nums[1] + nums[3]) : '';
    
    }
    
    let numMax5 = () => {
    	if(nums.length >= 5) {
    		let farr = nums.splice(0, 5);
    		max += Math.max(farr[0] + farr[2], farr[0] + farr[3], farr[0] + farr[4],
         farr[1] + farr[3], farr[2] + farr[4]);
    	}
    }
    if (nums.length < 5) {
    	numsMin5();
    	flag = false;
    }else{
    	numMax5();
    }
    while(nums.length >= 5){
    	numMax5();
    }
    nums.length < 5 && flag ? numsMin5() : numMax5();
    return max;
     }
    

    为什么提示Wrong Answer
    输入 [6,7],应该返回 16,但你返回的是 15


  • 0

    const rob = (nums) => {
    let max = 0,flag = true;
    let numsMin5 = () => {
    	nums.length == 0 ? max +=0 : '';
    	nums.length < 3 && nums.length != 0? max += Math.max(...nums) : '';
    	nums.length == 3 ? max += Math.max(nums[1], nums[0] + nums[2]) : '';
    	nums.length == 4 ? max += Math.max(nums[0] + nums[2], nums[0] + nums[3], nums[1] + nums[3]) : '';
    }
    let numMax5 = () => {
    	if(nums.length >= 5) {
    		let farr = nums.splice(0, 5);
    		max += Math.max(farr[0] + farr[2], farr[0] + farr[3], farr[0] + farr[4], farr[1] + farr[3], farr[2] + farr[4]);
    	}
    }
    if (nums.length < 5) {
    	numsMin5();
    	flag = false;
    }else{
    	numMax5();
    }
    while(nums.length >= 5){
    	numMax5();
    }
    nums.length < 5 && flag ? numsMin5() : numMax5();
    return max;
    }

  • 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

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


  • 0

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

    每个房子能否偷取决于前一个房子是否被偷过. 当我们想知道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];
    }
    

登录后回复
 

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