题解 | #反转链表#

递归实现——斐波那契数列

  //斐波那契数列的递归实现  fib(n) = fib(n-1) + fib(n-2);斐波那契数列的递归公式。
  static int fib(int n){
      if(n <=0) {
          throw new IllegalArgumentException("不合理的参数");
      }
      if(n == 1 || n== 2) return 1;
      return fib(n-1) + fib(n-2);
  }

时间复杂度O(2^n)，空间复杂度 O(n)
出现了特别多的重复计算。
是一种TopDown的调用过程，（自顶向下）由大的数递推出小的数。（由大的数调用小的数）

记忆化（数组保存重复计算的结果） —— 斐波那契数列

  public static long fib(int n){
      if (n <= 0){
          throw new IllegalArgumentException("参数 > 0,数组越界。");
      }
      long[] fibArr = new long[n];
      fibArr[0] = 1;
      fibArr[1] = 1;
      return fib(fibArr,n-1);
  }
  //使用数组记忆化 —— 实现斐波那契数列
  private static long fib(long[] fibArr,int n){
      if(fibArr[n] == 0){
          fibArr[n] = fib(fibArr,n-1) + fib(fibArr,n-2);
      }
      return fibArr[n];
  }

调用过程
时间复杂度O(n) 空间复杂度O(n)
时间复杂度降成O(n),从上图可以看出，因保存原来计算过的数据了，因此减少了重复计算
空间复杂度仍然是递归调用的深度。
还是存在递归调用，函数重复调用的次数大大较小，不过还有一点递归调用。

取出递归（循环实现） —— 斐波那契数列
- ```
  //直接使用 循环 就能实现斐波那契数列的计算。
  public static long fib(int n) {
      long[] fibArr = new long[n + 1];
      fibArr[1] = fibArr[2] = 1L;
      for (int i = 3; i <= n; i++) {
          fibArr[i] = fibArr[i - 1] + fibArr[i - 2];
      }
      return fibArr[n];
  }
```
- 事件复杂度 O(n) 空间复杂度O(n)
- 优化取出了递归调用的空间复杂度，因为记忆化的递归空间复杂度O(2n) 现在是 O(n)了。
- 改成非递归以后变成 BottomUp的计算方式（自底向上），由小的计算出大的。

滚动数组 —— 斐波那契数列。空间复杂度上的优化。（取余和位运算实现）

  // 使用滚动数组，优化空间复杂度
  public static long fib2(int n) {
      if( n < 1){
          throw new IllegalArgumentException("参数 》=1");
      }
      //循环使用一个两个元素的数组完成，大大减小了空间复杂度。
      long[] fibArr = new long[2];
      fibArr[0] = 1;
      fibArr[1] = 1;
      for (int i = 2; i <= n; i++) {
          fibArr[i&1] = fibArr[0] + fibArr[1];
      }
      return fibArr[(n-1)&1];
  }

    // 使用%运算计算奇数和偶数
    public static long fib(int n) {

        if ( n <= 2) return 1L;
        //循环使用一个两个元素的数组完成，大大减小了空间复杂度。
        long[] fibArr = new long[2];
        fibArr[0] = 1;
        fibArr[1] = 1;
        // 0 : 1 , 1 : 1, 2:2,3:3,4:5
        // 下标从0开始对应，fibArr[0] 存储 偶数下标的数， fibArr[1] 存储奇数下标的数
        for (int i = 2; i <= n; i++) {
            fibArr[i%2] = fibArr[(i-1)%2] + fibArr[(i-2)%2];
        }
        return fibArr[(n-1)%2];
    }


    // 使用位运算计算奇数和偶数
    public static long fib3(int n) {

        if ( n <= 2) return 1L;
        //循环使用一个两个元素的数组完成，大大减小了空间复杂度。
        long[] fibArr = new long[2];
        fibArr[0] = 1;
        fibArr[1] = 1;
        // 0 : 1 , 1 : 1, 2:2,3:3,4:5
        // 下标从0开始对应，fibArr[0] 存储 偶数下标的数， fibArr[1] 存储奇数下标的数
        for (int i = 2; i <= n; i++) {
            fibArr[i&1] = fibArr[(i-1)&1] + fibArr[(i-2)&1];
        }
        return fibArr[(n-1)&1];
    }
    ```

- <img src="G:\大数据\数据结构体和算法笔记\image-20210629163648043.png" alt="image-20210629163648043" style="zoom:67%;" />

- 在循环实现的时候发现只用到了，前两个元素，因此只开辟两个空间就可以了。（使用数组记录完整的斐波那契数列的话，计算完成一遍，以后计算都是常数级别的时间复杂度了。）

- 时间复杂度O(n) ,空间复杂度O(1)级别。

- 计算 奇数和偶数 的技巧

    - 因为**位运算** 比乘法 、除法 、取模 运算效率要高很多

    - ![image-20210623173742642](https://uploadfiles.nowcoder.com/images/20190919/56_1568900435177_29C080A5413E925FE3B3CCB4048AB99B)

使用变量来解决 —— 斐波那契数列

  // 使用两个变量来存储,使用了斐波那契数列的性质
  public static long fib(int n) {
      if (n < 3) return 1;
      long first = 1L;
      long second = 1L;
      for (int i = 3; i <= n; i++) {
          second = first + second;
          first = second - first;
      }
      return second;
  }

  //一般情况下，temp进行轮转。
  public static long fib2(int n){

      if (n < 3) return 1;
      long first = 1L;
      long second = 1L;
      long temp = 0L;

      for (int i=3;i<=n;i++){
          temp = second +first;
          first = second;
          second = temp;
      }

      return second;
  }

时间复杂度 O(n) 空间复杂度O(1)

使用公式计算斐波那契数列