一、算法思想介紹

常用的算法包含但不限于以下幾種：

• 分治： 分而治之，將問題拆解為形式相同子問題處理，然后合并為原問題解。
• 窮舉： 無差別例舉每一種可能解。
• 迭代： 不斷用變量的舊值推出新值。
• 回溯： 按條件走，走不通就退回重新再走，回溯的核心在遞歸。
• 遞歸： 函數(shù)調(diào)用自身來處理相同邏輯。
• 貪心： 將問題拆解為子問題來處理，每一步都先考慮當(dāng)前最優(yōu)(貪心)選擇。
• 動(dòng)態(tài)規(guī)劃：將問題拆解為子問題來處理，整體問題的最優(yōu)解依賴各個(gè)子問題的最優(yōu)解，自下而上求解，需要記錄之前的所有局部最優(yōu)解。

二、經(jīng)典案例分析

1）二分查找 （分治）

題干：在一個(gè)有序數(shù)組中，在不增加空間復(fù)雜度的前提下，高效查找目標(biāo)數(shù)。

public static int binarySearch(int[] arr, int target, int low, int high) {
    if (target < arr[low] || target > arr[high] || low > high) {
        return -1;
    }
    int middle = (low + high) / 2;
    if (target < arr[middle]) {
        return binarySearch(arr, target, low, middle);
    } else if (target > arr[middle]) {
        return binarySearch(arr, target, middle, high);
    } else {
        return middle;
    }
}

注：這里用了遞歸來簡化邏輯。

2）雞兔共籠 （窮舉）

題干：一個(gè)籠子里關(guān)有雞兔共35頭，一共94只腳，籠中雞兔各有多少只？

public static void exhaustion(int head, int foot) {
    int chicken ;
    int rabbit ;
    for (int i = 0; i <= head; i++) {
       chicken = i;
        rabbit = head - i;
        if (2 * chicken + 4 * rabbit == foot) {
            System.out.println("chicken:" + chicken + "; rabbit:" + rabbit);
        }
    }
}

3）Fibonacci數(shù)列 （迭代）

題干：求Fibonacci數(shù)列：1、1、2、3、5、8、13、21、34、…… 第N位元素值

public static int iteration(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1 || n == 2) {
        return 1;
    } else if (n > 2) {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    return -1;
}

4）八皇后問題 （回溯）

題干：將八個(gè)皇后放在棋盤上，沒有任何兩個(gè)皇后在同一行、同一列或者同一對角線上

static int count = 0;
static int size = 4;
public static void main(String[] args) {
    LinkedList<Location> arr = new LinkedList<>();
    traceBack(arr, 0, 0);
    printResult(arr);
    System.out.println("八皇后共有: " + count + "種擺放方式");
}
static class Location {
    int x;
    int y;
    public Location(int x, int y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public String toString() {
        return "（" + x + "," + y + "）";
    }
}
public static void printResult(LinkedList<Location> arr) {
    if (arr.size() == 0) {
        return;
    }
    System.out.println("第" + (count + 1) + "種:");
    for (int i = 0; i < arr.size(); i++) {
        System.out.print(arr.get(i).toString() + "\t");
    }
    System.out.println();
    count++;
}
public static void traceBack(LinkedList<Location> arr, int x, int y) {
    if (arr.size() == size) {
        printResult(arr);
    }
    for (int i = x; i < size; i++) {
        Location location = new Location(i, y);
        if (isOk(arr, location)) {//判斷是否滿足排列要求，不滿足回溯到上一層 判斷同行的下一列位置
            arr.offer(location);//保存擺好的皇后
            System.out.println("offer:" + "(" + location.x + ", " + location.y + ")");
            traceBack(arr, 0, y + 1);//開始排下一行的皇后
            arr.pollLast();//當(dāng)前不滿足條件則取消上一次擺放方案，重新擺放
            System.out.println("polllast:" + "(" + location.x + ", " + location.y + ")");
        }
    }
}
public static boolean isOk(LinkedList<Location> arr, Location oriLocation) {
    for (Location loc : arr) {
        if (loc.x == oriLocation.x || loc.y == oriLocation.y) { //同行同列判斷
            return false;
        } else if (Math.abs(loc.x - oriLocation.x) == Math.abs(loc.y - oriLocation.y)) {//斜對角線判斷
            return false;
        }
    }
    return true;
}

5）剪繩子問題 （貪心與動(dòng)態(tài)規(guī)劃）

題干：一根長度為n的繩子，請把繩子剪成m段，最終每段繩子長度的乘積最大值是多少？例如，當(dāng)繩子的長度為8時(shí)，我們剪成3,3,2三段，最大乘積是18。
動(dòng)態(tài)規(guī)劃解：

public static int dp(int len) {
    if (len < 2)
        return 0;
    if (len == 2)
        return 1;
    if (len == 3)
        return 2;
    //子問題的最優(yōu)解存儲在arr數(shù)組中，第i個(gè)元素表示把長度為i的繩子剪成若干段后各段長度乘積的最大值
    int[] arr = new int[len + 1];
    //這些情況下，不剪的時(shí)候長度比剪的時(shí)候長，所以作為初始條件
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 3;
    for (int i = 4; i <= len; i++) {
        int max = 0;
        for (int j = 1; j <= i / 2; j++) {
            //動(dòng)態(tài)規(guī)劃：以上一個(gè)子問題的最優(yōu)解為依據(jù)來求下一個(gè)子問題的最優(yōu)解
            int num = arr[j] * arr[i - j];
            System.out.println("i:" + i + " arr[" + j + "] * " + "arr[" + (i - j) + "]" + " " + "num:" + num);
            if (max < num)
                max = num;
        }
        arr[i] = max;
    }
    return arr[len];
}

貪心解：

public static int greedy(int len) {
    /**
     * 先找規(guī)律
     * len = 1  1
     *
     * len = 2  1
     * len = 3  2
     *
     * len = 4  2*2 4
     * len = 5  2*3 6
     * len = 6  3*3 9
     * len = 7  3*2*2 12
     * len = 8  3*3*2 18
     * len = 9  3*3*3 27
     * len = 10 3*3*2*2 36
     * ...
     * 從5開始，就由3和2組成，有3盡量滿足3，如何最后剩余3和1則轉(zhuǎn)為2*2
     * 貪心：有最優(yōu)解3，盡量湊成3，最后3*1 的情況特殊考慮轉(zhuǎn)為2*2
     */
    if (len == 1) {
        return 1;
    }
    if (len > 1 && len < 4) {
        return len - 1;
    }
    if (len == 4) {
        return len;
    }
    if (len % 3 == 1) {
        return (int) Math.pow(3, len / 3 - 1) * (int) Math.pow(2, 2);
    } else {
        return (int) Math.pow(3, len / 3) * 2;
    }
}