#102 记忆化斐波那契函数(Memoization)


  • 0

    @老人羽海 厉害厉害


  • 0

    @aipeidong 厉害啊


  • 0

    @老人羽海#102 记忆化斐波那契函数(Memoization) 中说:

    @aipeidong 厉害厉害,简直大声确实


  • 0

    const fibonacci = n => {
    fibonacci.cacheArray = fibonacci.cacheArray || [1, 1, 1]
    if (n <= 2) {
    return fibonacci.cacheArray[n]
    }
    fibonacci.cacheArray.push(
    fibonacci.cacheArray[n - 1] + fibonacci.cacheArray[n - 2]
    )
    return fibonacci.cacheArray[n]
    }


  • 0

    const fibonacci = (n) => /* TODO */
    {
    if(!fibonacci.data){
    let i;
    fibonacci.data={}
    for(i = 0; i < n ;i++){
    if(i == 0 || i == 1){
    fibonacci.data[i] = 1;
    }else{
    fibonacci.data[i] = fibonacci.data[i-1] + fibonacci.data[i -2];
    }
    }
    }
    return fibonacci.data[n-1];
    }
    请问这个代码为什么它报错n=2为undefined?


  • 0

    @aipeidong 可是输入10000就Maximum call stack size exceeded了哎


  • 0

    分享链接打不开我的哥哥


  • 0

    const fibonacci = (function () {
      const cached = [null, 1, 1];
      return (n) => {
        if (cached[n]) {
          return cached[n];
        } else {
          const result = fibonacci(n - 1) + fibonacci(n - 2);
          cached.push(result);
          return result;
        }
      }
    })();
    // 通过测试
    

  • 1

    @ScriptOJ
    function fibonacci(n) {
    if (n == 0) {
    return 0
    }else if (n == 1){
    return 1
    }else {
    return fibonacci(n-1) + fibonacci(n-2)
    }
    }
    我还是觉得递归最简单,为什么不行


  • 0

    const fibonacci = (buffer => n => 
    	n < 2 ? buffer[n] : (
    		buffer.push(buffer[n - 1] + buffer[n - 2]),
    		buffer[n - 2]
    	)
    )([1, 1]);

  • 0

    用闭包的缓存功能
    const fibonacci = (function() {
    var cache = []
    return (n) => {
    if (n<=2) {
    cache.push(1)
    return 1
    } else {
    cache.push(cache[n-3]+cache[n-2])
    return cache[n-1]
    }
    }
    })()


  • 0

    const fibonacci = (n) => {
    fibonacci.mapValue = fibonacci.mapValue || {};
    if(fibonacci.mapValue[n]) {
    return fibonacci.mapValue[n];
    }
    if(n < 3) {
    return 1;
    }
    if(fibonacci.mapValue[n]) {
    return fibonacci.mapValue[n];
    }
    fibonacci.mapValue[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return fibonacci.mapValue[n];
    }


  • 0

    缓存很关键

    const fibonacci = (n) => {
      if (!fibonacci.cache) {
        fibonacci.cache = {
          0:0,
          1:1,
          2:1
        };
      }
       if (!fibonacci.cache[n]) {
          fibonacci.cache[n] = (fibonacci(n - 1) + fibonacci(n - 2));
          return fibonacci.cache[n]
        }else {
          return fibonacci.cache[n]
        }
    }
    

  • 0

    let arr = [0, 1, 1]
    
    const fibonacci = (n) => {
      if (!arr.hasOwnProperty(n)) {
        arr[n] = fibonacci(n - 1) + fibonacci(n - 2)
      }
      return arr[n]
    }
    

  • 0

    const fibonacci = (n) => n<=2?1:(fibonacci(n-1)+fibonacci(n-2))
    

  • 0

    const fibonacci = (()=>{
      const arr=[0,1,1];
      return (n)=>{
        if (arr[n]) return arr[n];
        else {
          arr[n]=fibonacci(n - 1) + fibonacci(n - 2);
          return arr[n];
        }
      }
    })()
    

  • 0

    const fibonacci = (n) => {
    fibonacci.list = fibonacci.list || []
    let list = fibonacci.list
    let len = list.length

    if (len >= n) return list[n - 1]

    for(let i = len; i < n; i++) {
    if (i < 2) {
    list.push(1)
    } else {
    list.push(list[i-1] + list[i-2])
    }
    }
    return list[n - 1]
    }


登录后回复
 

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