前言+說明

??旺仔兄弟們！如果覺得博主分享的不錯，希望能留下您的一鍵??三連??（點贊+評論+收藏） ，您的支持就是我的動力??，您的三連對我特別重要，
注明：下述題目只用于學習交流所用，禁止用于商業銷售，同時在題解方面也希望大家能提出寶貴建議，共同進步??！

一、斐波那契數（Leecode_509）

題目描述：
斐波那契數，通常用 F(n) 表示，形成的序列稱為 斐波那契數列 ，該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和，也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
給你 n ，請計算 F(n) ，

樣例1：

輸入： 2
輸出： 1
解釋: F(2) = F(1) + F(0) = 1 + 0 = 1

樣例2：

輸入： 3
輸出： 2
解釋: F(3) = F(2) + F(1) = 1 + 1 = 2

樣例.3：

輸入： 4
輸出： 3
解釋: F(4) = F(3) + F(2) = 2 + 1 = 3

【方法一】：遞回
參考代碼：

import java.util.Scanner;

public class Leecode509_Fib {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = fib(n);
        System.out.println(ans);
    }
    public static int fib(int n){
        if (n<=1){
            return n;
        }else{
            return fib(n-1) + fib(n-2);
        }
    }
}

【結果裂開啦】

【方法二】：滾動陣列
斐波那契數的邊界條件是 F(0)=0和 F(1)=1，當 n>1 時，每一項的和都等于前兩項的和，因此有如下遞推關系：F(n)=F(n?1)+F(n?2)
由于斐波那契數存在遞推關系，因此可以使用動態規劃求解，動態規劃的狀態轉移方程即為上述遞推關系，邊界條件為 F(0) 和 F(1)，
根據狀態轉移方程和邊界條件，可以得到時間復雜度和空間復雜度都是 O(n) 的實作，由于 F(n) 只和 F(n?1)與 F(n?2)有關，因此可以使用「滾動陣列思想」把空間復雜度優化成 O(1)，

參考代碼：

import java.util.Scanner;

public class Leecode509_Fib {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = fib(n);
        System.out.println(ans);
    }
    public static int fib(int n){
        int[] arr = new int[3];
        arr[0] = 0;arr[1]=1;
        if (n<=1){
            return n;
        }
        for (int i=2; i<=n; i++){
            arr[0] = arr[1];
            arr[1] = arr[2];
            arr[2] = arr[0]+arr[1];
        }
        return arr[2];
    }
}

二、位元組跳動編程題（數列變換）

時間限制： 3000MS
記憶體限制： 1048576KB
題目描述：
存在兩個長度相等數列a和b，其中存盤的是正整數，判斷有沒有一個操作能使a數列變化成b數列，
操作：在數列a中選取一個區間a[l] - a[r]，對這個區間中的所有數字加上一個正整數k，
其中，1 ≤ l ≤ r ≤ n，k ≥ 0，

輸入描述

第一行： 表示 t 組資料；
第二行：n₁?表示數列的長度；
第三行：X₁ X₂ X₃ … X _n 表示a數列
第四行：Y₁ Y₂ Y₃ … Y _n 表示b數列
…
接下來k行為其它 t-1 組資料

輸出描述

YES或者NO

樣例輸入

2
6
3 7 1 4 1 2
3 7 3 6 3 2

樣例輸出

YES
NO

規則

請盡量在全場考試結束10分鐘前除錯程式，否則由于密集排隊提交，可能查詢不到編譯結果，點擊“除錯”亦可保持代碼
編程題可以使用本地編譯器，此頁面不記錄跳出次數

解題思路：
（1）用兩個整數型陣列分別來存放數列a、數列b；
（2）同時遍歷數列a和數列b
（2.1）如果數列相同位置值相同則繼續遍歷
（2.2）如果數列相同位置值不相同：
（2.2.1） 判斷值不同的陣列位置是否連續，不連續輸出NO，連續的繼續遍歷;
（2.2.2） 判斷兩陣列相差的值相同且b數列的值 - a數列的值大于0，則繼續遍歷，否則輸出NO;
（3）如果全部遍歷完成且滿足條件則輸出YES，
參考代碼：

import java.util.Arrays;
import java.util.Scanner;

public class Test01_Arrays {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] ans = new String[n];
        for (int i=0; i<n; i++){
            int m = sc.nextInt();
            int[] list1 = new int[m];
            int[] list2 = new int[m];
            for (int j=0; j<m; j++){
                list1[j] = sc.nextInt();
            }
            for (int j=0; j<m; j++){
                list2[j] = sc.nextInt();
            }
            if (isTransform(list1,list2)){
                ans[i]="YES";
            }else {
                ans[i]="NO";
            }

        }
        for (int i=0; i<ans.length; i++){
            System.out.println(ans[i]);
        }
    }
    public static boolean isTransform(int[] list1, int[] list2){
        if (list1.length==0 || list2.length==0){
            return false;
        }

        int temp=0;
        int point = 0;
        for (int i=0; i<list1.length; i++){
            if (list1[i] == list2[i])
                continue;
            if (list1[i] != list2[i]){
                if (point!=0 && point+1!=i){//判斷是區間需要連續，如果不連續則回傳false
                    return false;
                }
                point = i;
                if ((temp<0 || temp!=list2[i]-list1[i]) && temp!=0){//temp必須為正整數
                    return false;
                }
                temp = list2[i] - list1[i];
            }
        }
        return true;
    }
}