#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]
    }


  • 1

    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
    }
    

  • 1

    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 这个函数写的真漂亮


登录后回复
 

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