新星計劃Day9【資料結構與算法】遞歸

👩‍💻部落格首頁：京與舊鋪的部落格首頁

✨歡迎關注🖱點贊🎀收藏⭐留言✒

🔮本文由京與舊鋪原創

😘系列專欄：java學習

👕參考網課：尚矽谷

💻首發時間：🎞2022年5月10日🎠

🎨你做三四月的事，八九月就會有答案，一起加油吧

🀄如果覺得部落客的文章還不錯的話，請三連支援一下部落客哦

🎧最後的話，作者是一個新人，在很多方面還做的不好，歡迎大佬指正，一起學習哦，沖沖沖

💬推薦一款模拟面試、刷題神器👉點選進入網站

🛒導航小助手🎪

文章目錄

新星計劃Day9【資料結構與算法】遞歸
🛒導航小助手🎪

@[toc]

🧇43p 遞歸應用場景和調用機制
🥩44p 遞歸能解決的問題和規則
🥘45p 迷宮回溯問題分析和實作（1）
🌯46 迷宮回溯問題分析和實作（2）
🥡47 八皇後問題分析和實作

🧇43p 遞歸應用場景和調用機制

遞歸的概念

簡單的說：遞歸就是方法自己調用自己，每次調用時傳入不同的變量，遞歸有助于程式設計者解決複雜的問題。同時可以讓代碼變得簡潔。

🥩44p 遞歸能解決的問題和規則

遞歸能解決什麼樣的問題呢

各種數學問題如: 8皇後問題 , 漢諾塔, 階乘問題, 迷宮問題, 球和籃子的問題(google程式設計大賽)
各種算法中也會使用到遞歸，比如快排，歸并排序，二分查找，分治算法等.
将用棧解決的問題—>遞歸代碼比較簡潔

遞歸需要遵守的重要規則

執行一個方法時，就建立一個新的受保護的獨立空間(棧空間)
方法的局部變量是獨立的，不會互相影響，比如n變量
如果方法中使用的是引用類型變量(比如數組)，就會共享該引用類型的資料
遞歸必須向退出遞歸的條件逼近，否則就是無限遞歸，出現StackOverflowError
當一個方法執行完畢，或者遇到return，就會傳回，遵守誰調用，就将結果傳回給誰，同時當方法執行完畢或者傳回時，該方法也就執行完畢

🥘45p 迷宮回溯問題分析和實作（1）

說明:

小球得到的路徑，和程式員設定的找路政策有關即：找路的上下左右的順序相關
再得到小球路徑時，可以先使用(下右上左)，再改成(上右下左)，看看路徑是不是有變化
測試回溯現象
思考**: **如何求出最短路徑?

/**
 * @author wuyou
 */
public class Maze {
    public static void main(String[] args) {
        // 先建立一個二維數組，模拟迷宮
        int[][] map = new int[8][7];

        // 使用1表示牆，上下邊界全部置為1
        for (int i = 0; i < map.length; i++) {
            if (i == 0 || i == map.length - 1) {
                for (int j = 0; j < map[i].length; j++) {
                    map[i][j] = 1;
                }
            } else {
                map[i][0] = 1;
                map[i][map[i].length - 1] = 1;
            }
        }

        // 設定擋闆，1表示
        map[3][1] = 1;
        map[3][2] = 1;

        // 列印地圖
        System.out.println("原本地圖的情況");
        printMap(map);

        // 使用遞歸回溯
        setWay(map, 1, 1);
        System.out.println("小球走過并且辨別的地圖的情況：");
        printMap(map);
    }

    /**
     * 終點為右下角位置
     * 當map[i][j]為0時，表示沒有走過
     * 當map[i][j]為1時，表示牆
     * 當map[i][j]為2時，表示通路可以走
     * 當map[i][j]為3時，表示該點走不通
     * 在走迷宮時，需要确定一個測略（方法） 下 -> 右 -> 上 -> 左 ， 如果該點走不通，再回溯
     * @param map 地圖
     * @param i 出發點x坐标
     * @param j 出發點y坐标
     * @return
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if (map[map.length - 2][map[map.length - 2].length - 2] == 2) {
            // 說明通路已經找到
            return true;
        } else {
            // 說明目前這個點還沒有走過
            if (map[i][j] == 0) {
                // 按照政策 下 -> 右 -> 上 -> 左

                // 假定該店是可以走通的
                map[i][j] = 2;

                // 向下走
                if (setWay(map, i + 1, j)) {
                    return true;
                }
                // 向右走
                else if (setWay(map, i ,j +1)) {
                    return true;
                }
                // 向上走
                else if (setWay(map, i - 1, j)) {
                    return true;
                }
                // 向左走
                else if (setWay(map, i - 1, j)) {
                    return true;
                }
                // 說明該點走不通，是思路，不過既然上下左右都走不通，那麼這點不會經過的
                else {
                    map[i][j] = 3;
                    return false;
                }
            }
            // 說明該節點，可能是1 2 3，2的出現是因為迷宮問題不會走重複路，不然會繞圈
            else {
                return false;
            }
        }
    }

    /**
     * 列印地圖
     * @param map 二維地圖
     */
    public static void printMap(int[][] map) {
        // 列印地圖
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
}

🌯46 迷宮回溯問題分析和實作（2）

常常我們有這樣一個問題：從一個起點開始要到一個終點，我們要找尋一條最短的路徑。

我們采用示例圖來說明這個過程，在搜尋的過程中，初始所有節點是白色（代表了所有點都還沒開始搜尋），把起點V0标志成灰色（表示即将輻射V0），下一步搜尋的時候，我們把所有的灰色節點通路一次，然後将其變成黑色（表示已經被輻射過了），進而再将他們所能到達的節點标志成灰色（因為那些節點是下一步搜尋的目标點了），但是這裡有個判斷，就像剛剛的例子，當通路到V1節點的時候，它的下一個節點應該是V0和V4，但是V0已經在前面被染成黑色了，是以不會将它染灰色。這樣持續下去，直到目标節點V6被染灰色，說明了下一步就到終點了，沒必要再搜尋（染色）其他節點了，此時可以結束搜尋了，整個搜尋就結束了。然後根據搜尋過程，反過來把最短路徑找出來，下圖中把最終路徑上的節點标志成綠色。

/**
 *
 * @author wuyou
 */
public class BFSMaze {
    public static void main(String[] args) {
        char[][] ditu = new char[10][10];
        for (int i = 0; i < 10; i++) {
            Arrays.fill(ditu[i], 'O');
        }
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                ditu[0][i] = '#';
                ditu[9][i] = '#';
                ditu[i][0] = '#';
                ditu[i][9] = '#';
            }
        }

        // 建立圍牆
        ditu[1][3] = ditu[1][7] = ditu[2][3] = ditu[2][7] = '#';
        ditu[3][5] = '#';
        ditu[4][2] = ditu[4][3] = ditu[4][4] = '#';
        ditu[5][4] = ditu[6][2] = ditu[6][6] = '#';
        ditu[7][2] = ditu[7][3] = ditu[7][4] = ditu[7][6] = ditu[7][7] = '#';
        ditu[8][1] = ditu[8][2] = '#';
        System.out.println("迷宮地形圖：");

        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                System.out.print(ditu[i][j] + " ");
            }
            System.out.println();
        }



        // 設定起始點與終點。
        int[] start = new int[]{1, 1};
        int[] end = new int[]{1, 8};

        int[][] d = bfs(ditu, start, end);

        System.out.println("該地圖最短路徑長為：" + d[end[0]][end[1]]);
        System.out.println("---上帝視角迷宮最短路徑地形圖：---");
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                // 有步數的情況下列印步數，沒有步數的情況下列印對應的字元
                if (d[i][j] > 0 && d[i][j] < Integer.MAX_VALUE) {
                    System.out.printf("%-5d", d[i][j]);
                } else {
                    System.out.printf("%-5c", ditu[i][j]);
                }
            }
            System.out.println();
        }
    }

    /**
     * bfs算法得到最端路徑
     * @param map 二維地圖
     * @param start 開始點
     * @param end 終點
     * @return
     */
    public static int[][] bfs(char[][] map, int[] start, int[] end) {
        // 移動的四個方向（下右上左）。
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        // 用隊列存儲對應點的橫坐标與縱坐标。
        Queue<int[]> que = new LinkedList<>();
        // 到起始點的距離，我們先全部初始化為最大值。
        int[][] min = new int[map.length][map[0].length];
        for (int i = 0; i < min.length; i++) {
            Arrays.fill(min[i], Integer.MAX_VALUE);
        }
        // 起始點的距離設為0
        min[start[0]][start[1]] = 0;
        // 将起始點入隊
        que.offer(start);

        // 隊列為空的情況跳出循環，即該迷宮走不出去，無解。
        while (!que.isEmpty()) {
            // 取出隊列中最前端的點
            int[] temp = que.poll();
            // 如果是終點則結束
            if (temp[0] == end[0] && temp[1] == end[1]) {
                break;
            }
            // 四個方向循環
            for (int i = 0; i < 4; i++) {
                int y = temp[0] + dy[i];
                int x = temp[1] + dx[i];
                // 判斷是否可以走，條件為該點不是牆，并且沒有走過
                if (map[y][x] != '#' && min[y][x] == Integer.MAX_VALUE) {
                    // 如果可以走，則将該點的距離加1
                    min[y][x] = min[temp[0]][temp[1]] + 1;
                    // 将可以走的點入隊
                    que.offer(new int[]{y, x});
                }
            }
        }
        // 傳回所有點到到起始點的距離的二維數組。
        return min;
    }
}

🥡47 八皇後問題分析和實作

暴力解法（窮舉解法）：

第一個皇後先放第一行第一列
第二個皇後放在第二行第一列、然後判斷是否OK，如果不OK，繼續放在第二列、第三列、依次把所有列都放完，找到一個合适
繼續第三個皇後，還是第一列、第二列……直到第8個皇後也能放在一個不沖突的位置，算是找到了一個正确解
當得到一個正确解時，在棧回退到上一個棧時，就會開始回溯，即将第一個皇後，放到第一列的所有正确解，全部得到.
然後回頭繼續第一個皇後放第二列，後面繼續循環執行 1,2,3,4的步驟

說明：理論上應該建立一個二維數組來表示棋盤，但是實際上可以通過算法，用一個一維數組即可解決問題：

arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //對應arr 下标表示第幾行，即第幾個皇後，arr[i] = val , val 表示第i+1個皇後，放在第i+1行的第val+1列

import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author wuyou
 */
public class Queue8 {
    /**
     * 定義一個max表示有多少個皇後
     */
    final static int MAX = 8;

    /**
     * 定義一個Array數組，儲存皇後放置位置的結果，比如array = {0,4,7,5,2,6,1,3}
     */
    static int[] array = new int[MAX];

    /**
     * 如果是多線程，使用原子類能確定得到最終的情況數
     */
    static AtomicInteger count = new AtomicInteger(0);

    /**
     * 統計判斷的次數
     */
    static AtomicInteger judgeCount = new AtomicInteger(0);

    public static void main(String[] args) {
        check(0);
        System.out.println("總共有【" + count + "】情況");
        System.out.println("總共有【" + judgeCount + "】次判斷沖突的次數");
    }

    /**
     * 放置第n + 1個皇後，遞歸
     * @param n 第 n + 1個皇後
     */
    public static void check(int n) {
        // 說明8個皇後已經放好
        if (n == MAX) {
            print();
            count.getAndIncrement();
            return;
        }
        // 依次放入皇後，并判斷是否沖突
        for (int i = 0; i < MAX; i++) {
            // 把目前這個皇後，放到該行的第i列
            array[n] = i;
            // 判斷當放置第n個皇後放到第i列時，是否沖突
            if (judge(n)) {
                // 不沖突，接着放第n+1個皇後，開始遞歸
                check(n + 1);
            }
            // 如果沖突，就繼續指向array[n] = i;
        }
    }

    /**
     * 判斷第 n + 1個皇後是否和前面皇後沖突
     * @param n 表示第 n + 1個皇後
     * @return 是否可以擺放
     */
    public static boolean judge(int n) {
        judgeCount.getAndIncrement();
        for (int i = 0; i < n; i++) {
            // array[i] == array[n] 表示判斷第n個皇後和前面n-1個皇後是否在在同一列
            // Math.abs(n - i) == Math.abs(array[n] - array[i]) 通過判斷直角三角形兩直角邊是否相等确定是否在同一斜線
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 列印皇後的位置
     */
    public static void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

下期預告：力扣每日一練之字元串Day6

新星計劃Day9【資料結構與算法】遞歸