#74 爬楼梯


  • 0
    administrators

    有一个楼梯,你一次只能往上走一阶或者两阶。请编写函数 climbStairs,它接受一个整数 n 作为参数,表示这个楼梯有多少阶。请你返回一个整数,表示这个楼梯一共有多少种走法。例如:

    climbStairs(1) // => 1
    climbStairs(2) // => 2
    climbStairs(3) // => 3
    climbStairs(10) // => 89
    

  • 0

    @胡子大哈

    map is not defined
    

    这个错误是怎么回事,完全没用到map


  • 0
    administrators

    @CodeHz 好了


  • 0

    @胡子大哈

    输入 42,应该返回 433494436.9999999,而你的是 433494437
    

    这是啥情况


  • 0

    @CodeHz 大概是写反了2333


  • 4

    代数解法

    const climbStairs = n => n <= 0 ? 0 : Math.round((s5 => 1/s5*(((1+s5)/2)**(n+1) - ((1-s5)/2)**(n+1)))(Math.sqrt(5)))
    

    记忆化解法

    const memorize = [0, 1, 2]
    const climbStairs = n => n in memorize ? memorize[n] : (memorize[n] = climbStairs(n - 2) + climbStairs(n - 1))
    

    矩阵快速乘法

    const mul = (a, b) => {
      const s = [0, 1]
      const ret = [[0, 0], [0, 0]]
      for (let i of s)
        for (let j of s)
          for (let k of s)
            ret[i][j] = ret[i][j] + a[i][k] * b[k][j]
      return ret
    }
    const climbStairs = n => {
      let src = [[1, 1], [1, 0]]
      let cot = [[1, 0], [0, 1]]
      n = n + 1
      while (n) {
        if(n & 1) cot = mul(cot,src);
        src = mul(src,src);
        n /= 2
      }
      return cot[0][1]
    }
    

  • 0
    管理员

    // 弱鸡直接递归法:
    // const climbStairs = (n) => n < 3 ? n : climbStairs(n-1) + climbStairs(n-2) // 此答案运行超时- -
    
    // 弱鸡递推法(其实就是楼上的 记忆化解法)
    const climbStairs = (n) => {
      let arr = new Array(n)
      for(let i = 1; i <= n; i++) {
        if(i < 3) {
          arr[i - 1] = i
        } else {
          arr[i - 1] = arr[i - 2] + arr[i - 3]
        }
      }
      return n <= 0 ? 0 : arr[n - 1]
    }
    
    // 楼上大神 (逃
    

  • 0

    以前面试的时候见过这道题,当时面试官提示我,我才知道规律的,不过现在也没搞懂这是为什么。下面给一个递归的答案,但是通不过测试,提示耗时太长,先贴在下面,再考虑其他的解法

    const climbStairs = (n) => {
      if(n <= 0) return 0
      else if(n == 1) return 1
      else if(n == 2) return 2
      else return climbStairs(n-1) + climbStairs(n-2)
    }
    

    前端表单验证工具 https://github.com/WLDragon/SMValidator


  • 0

    用循环来做通过测试了

    const climbStairs = (n) => {
      if(n == 0) return 0
      else if(n == 1) return 1
      else if(n == 2) return 2
      else {
        let n1 = 1
        let n2 = 2
        for(i = 3; i < n; i++) {
          [n1, n2] = [n2, n1 + n2]
        }
        return n1 + n2
      }
    }
    

  • 0

    答案层出不穷

    const climbStairs = (n) => {
      if (!n) return 0
      let pre = 0
      let cur = 1
      while (n--) {
          [cur, pre] = [cur + pre, cur]
      }
      return cur
    }
    

登录后回复
 

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