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

登录后回复
 

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