LeetCode-第509题-斐波那契数-题解

• 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由0 和1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。

• 题解：

  class Solution {
      /**
       * 替换法(0ms,效率最高,内存消耗都差不多)
       * 时间复杂度是 O(n)
       */
      public int fib(int N) {
          if(N <= 1) return N;
          int first = 0;
          int second = 1;
          for(int i=0; i<N-1; i++){
              second = first + second;
              first = second - first;
          }
          return second;
      }
  
      /**
       * 递归法(21ms,代码少，效率低)
       * 时间复杂度是 O(2 ^ n)
       */
       public int fib2(int N) {
           if(N <=1) return N;
           return fib2(N-1) + fib2(N-2);
       }
  
      /**
       * 数组法(1ms,要操作数组,效率比操作整型低一点)
       * 时间复杂度O(n)
       */
       public int fib3(int N) {
           if(N <= 1) return N;
           int[] arr = new int[N];
           arr[0] = 0;
           arr[1] = 1;
           for(int i=2; i<=N; i++){
               arr[i] = arr[i-2] + arr[i-1];
           }
           return arr[N];
       }
  }