二分查找算法

二分查找算法（Binary Search Algorithm）是一種在有序數組中查找特定元素的搜索算法。該算法的基本思想是將數組從中間分成兩部分，然后與目標元素進行比較，進而確定目標元素位于左半部分還是右半部分，不斷縮小搜索范圍，直到找到目標元素或確定目標元素不存在。

以下是一個使用 Java 實現二分查找算法的示例：

public class BinarySearch {

    // 二分查找函數
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

    // 測試示例
    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;

        int result = binarySearch(array, target);

        if (result != -1) {
            System.out.println("目標元素 " + target + " 在索引 " + result + " 處找到了。");
        } else {
            System.out.println("目標元素 " + target + " 未找到。");
        }
    }
}

在上述示例中，binarySearch函數接受一個有序數組array和目標元素target作為參數。它使用left和right兩個指針來表示搜索范圍的左右邊界。初始時，left指向數組的第一個元素，right指向數組的最后一個元素。

在每次循環中，通過計算中間索引mid，將目標元素與中間元素進行比較。如果相等，說明找到了目標元素，返回mid作為結果。如果目標元素小于中間元素，說明目標元素可能在左半部分，將right更新為mid - 1。如果目標元素大于中間元素，說明目標元素可能在右半部分，將left更新為mid + 1。循環繼續進行，直到left大于right，表示搜索范圍為空，目標元素未找到，返回 -1 作為結果。

在main函數中，定義了一個有序數組array和目標元素target，然后調用binarySearch函數進行二分查找。根據返回的結果，輸出目標元素是否找到以及相應的索引位置。

如何衡量算法好壞？

衡量算法好壞的常用指標包括：

1. 時間復雜度：算法執行所需的時間，通常用 O(n)、O(nlogn)、O(n^2) 等表示。
2. 空間復雜度：算法執行所需的空間，通常用 O(n)、O(nlogn)、O(n^2) 等表示。
3. 正確性：算法是否能正確地解決問題。
4. 可讀性：算法是否易于理解和維護。
5. 效率：算法的執行效率，通常用執行時間和所需空間來衡量。
6. 穩定性：算法在不同輸入下的表現是否穩定。

這些指標并不是絕對的，不同的應用場景可能有不同的要求，需要根據具體情況進行權衡。

時間復雜度和空間復雜度

時間復雜度和空間復雜度是衡量算法效率的兩個重要指標。

時間復雜度是指算法執行所需的時間，通常用大 O 表示法來表示。大 O 表示法是一種漸近表示法，它表示算法的執行時間隨著輸入規模的增長而增長的速度。常見的時間復雜度有 O(1)、O(logn)、O(n)、O(nlogn)、O(n^2) 等。例如，O(n)表示算法的執行時間隨著輸入規模的增長呈線性增長，O(n^2)表示算法的執行時間隨著輸入規模的增長呈平方增長。

空間復雜度是指算法執行所需的空間，通常也用大 O 表示法來表示。空間復雜度包括算法所需的內存空間和輔助空間。內存空間是指算法在執行過程中需要存儲的變量和數據結構所需的空間，輔助空間是指算法在執行過程中需要額外的空間來存儲臨時數據或進行其他操作。常見的空間復雜度有 O(1)、O(logn)、O(n)、O(nlogn)、O(n^2) 等。

在實際應用中，通常需要綜合考慮時間復雜度和空間復雜度，選擇在時間和空間上都盡可能高效的算法。同時，還需要考慮算法的實現難度、可讀性和可維護性等因素。

以下是計算算法時間復雜度的步驟：

1. 確定算法中的基本操作：確定算法中執行次數最多的操作，通常是循環或遞歸中的操作。
2. 計算基本操作的執行次數：對于循環，計算循環體執行的次數；對于遞歸，計算遞歸調用的次數。
3. 使用大 O 表示法表示時間復雜度：根據基本操作的執行次數，選擇適當的時間復雜度表示法。常見的時間復雜度有 O(1)、O(logn)、O(n)、O(nlogn)、O(n^2) 等。
4. 簡化時間復雜度：如果算法中存在多個循環或遞歸，可以將它們合并成一個時間復雜度。例如，如果一個算法中有兩個循環，一個循環執行 n 次，另一個循環執行 n^2 次，可以將時間復雜度表示為 O(n^2)。

需要注意的是，大 O 表示法只關心算法的最壞情況下的時間復雜度，而不考慮最好情況或平均情況。因此，在計算時間復雜度時，只需要考慮最壞情況下的執行次數。

以下是一個計算算法時間復雜度的示例：

public class Main {
    public static void main(String[] args) {
        int n = 1000;
        System.out.println(factorial(n));
    }

    public static int factorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

在上述示例中，factorial函數計算整數的階乘。在這個算法中，基本操作是乘法操作，執行次數是遞歸調用的次數。對于輸入規模為 n 的情況，遞歸調用的次數為 n，因此時間復雜度為 O(n)。

動態數組

動態數組是一種可以在運行時動態調整大小的數組。與靜態數組不同，動態數組不需要在編譯時指定數組的大小，可以根據實際需要動態地分配內存空間。

在 Java 中，可以使用ArrayList類來實現動態數組。ArrayList是 Java 集合框架中的一個動態數組實現，它可以根據元素的添加和刪除自動調整大小。

以下是一個使用 Java 實現動態數組的示例：

import java.util.ArrayList;

public class DynamicArrayExample {
    public static void main(String[] args) {
        DynamicArray array = new DynamicArray();

        // 向動態數組中添加元素
        array.add(10);
        array.add(20);
        array.add(30);
        array.add(40);

        // 獲取動態數組的大小
        int size = array.size();
        System.out.println("動態數組的大小：" + size);

        // 遍歷動態數組并打印元素
        for (int i = 0; i < size; i++) {
            int element = array.get(i);
            System.out.println("動態數組中的元素：" + element);
        }
    }
}

class DynamicArray {
    private ArrayList<Integer> arrayList;

    public DynamicArray() {
        // 創建一個 ArrayList 對象
        this.arrayList = new ArrayList<>();
    }

    public void add(int element) {
        // 向 ArrayList 中添加元素
        this.arrayList.add(element);
    }

    public int get(int index) {
        // 獲取 ArrayList 中指定索引處的元素
        return this.arrayList.get(index);
    }

    public int size() {
        // 獲取 ArrayList 的大小
        return this.arrayList.size();
    }
}

在上述示例中，我們創建了一個名為DynamicArray的類，其中包含一個私有成員變量arrayList，它是一個ArrayList對象，用于存儲動態數組的元素。

在DynamicArray類的構造函數中，我們創建了一個空的ArrayList對象。然后，我們提供了add方法來向動態數組中添加元素，get方法來獲取動態數組中指定索引處的元素，以及size方法來獲取動態數組的大小。

在main方法中，我們創建了一個DynamicArray對象，并使用add方法向動態數組中添加了一些元素。然后，我們通過size方法獲取動態數組的大小，并使用get方法遍歷動態數組并打印元素。

數組緩存與局部性原理

數組緩存是一種硬件優化技術，用于提高對數組的訪問速度。現代計算機系統中的 CPU 通常都集成了高速緩存（Cache），它是一種容量較小但訪問速度非常快的存儲器。當 CPU 訪問主存中的數據時，會將一部分數據緩存在高速緩存中，以便下次訪問時可以更快地獲取。

局部性原理是指在程序執行過程中，CPU 訪問的數據往往具有局部性，即在某個時間段內，CPU 會頻繁訪問某個特定區域的數據。這種局部性可以分為時間局部性和空間局部性。

時間局部性是指 CPU 在訪問某個數據后，很可能在不久的將來再次訪問該數據。這是因為程序中的循環、遞歸等結構會導致對相同數據的重復訪問。

空間局部性是指 CPU 在訪問某個數據時，很可能也會訪問附近的數據。這是因為程序中的數據通常是以數組、結構體等形式組織的，相鄰的數據之間往往存在著某種關聯。

基于局部性原理，數組緩存可以利用 CPU 訪問數據的局部性，將經常訪問的數據緩存在高速緩存中，從而提高訪問速度。當 CPU 需要訪問數組中的某個元素時，如果該元素已經緩存在高速緩存中，就可以直接從高速緩存中獲取，而不需要訪問主存，從而提高了訪問速度。

為了利用數組緩存，程序編寫時應該盡量保持數據的局部性。例如，可以將經常訪問的數據組織成數組形式，并按照一定的順序訪問數組元素，以提高緩存的命中率。同時，還可以使用一些編程技巧，如循環展開、數據預取等，來進一步提高程序的性能。

多路遞歸

多路遞歸（Multiway Recursion）是一種遞歸算法的設計技巧，它允許在一個遞歸函數中有多個遞歸調用路徑，從而實現更復雜的問題解決方案。

下面是一個使用多路遞歸計算斐波那契數列前 n 項的示例：

public class Main {
    public static void main(String[] args) {
        int n = 10;
        System.out.println(fibonacci(n));
    }

    public static long fibonacci(int n) {
        if (n <= 1) {
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

在上述示例中，fibonacci函數有兩個遞歸調用路徑：當 n <= 1 時，直接返回 n；否則，分別遞歸地計算 fibonacci(n - 1) 和 fibonacci(n - 2)，并將它們的和作為結果返回。

多路遞歸可以使遞歸函數更加靈活和強大，但也需要注意控制遞歸深度，避免出現棧溢出等問題。

漢諾塔

漢諾塔（Tower of Hanoi）別名河內塔，是一種起源于印度古老傳說的益智玩具。傳說在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針，其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。

玩家可以將漢諾塔的三根柱子設置為編號A、B、C，每次只能移動一個積木，并且在移動的過程中三根柱子上始終保持最大的積木在最下面，最小的積木在最上面。在操作過程中可以將積木置于A、B、C任意一根柱子上，最后通過反復移動將積木從一根柱子移動到另一個柱子上。

漢諾塔問題可以使用遞歸算法和迭代算法來解決。

遞歸算法是一種通過自身不斷調用自身來解決問題的算法。在漢諾塔問題中，可以使用遞歸算法來實現將盤子從一個柱子移動到另一個柱子的過程。遞歸算法的核心思想是將問題分解為較小的子問題，并通過遞歸調用自身來解決子問題。

迭代算法是一種通過循環來解決問題的算法。在漢諾塔問題中，可以使用迭代算法來實現將盤子從一個柱子移動到另一個柱子的過程。迭代算法的核心思想是通過循環來模擬盤子的移動過程，并在每次循環中更新盤子的位置。

無論是遞歸算法還是迭代算法，都可以有效地解決漢諾塔問題。

好的，以下是使用 Java 實現漢諾塔問題的遞歸算法和迭代算法的示例代碼：

1. 遞歸算法：

public class TowerHanoi {
    public static void main(String[] args) {
        int num = 3;
        String source = "A";
        String target = "C";
        String auxiliary = "B";
        hanoi(num, source, target, auxiliary);
    }

    public static void hanoi(int num, String source, String target, String auxiliary) {
        if (num > 0) {
            // 將 num-1 個盤子從源柱移動到輔助柱（借助目標柱）
            hanoi(num - 1, source, auxiliary, target);
            // 將第 num 個盤子從源柱移動到目標柱
            System.out.println("將盤子 " + num + " 從 " + source + " 移動到 " + target);
            // 將 num-1 個盤子從輔助柱移動到目標柱（借助源柱）
            hanoi(num - 1, auxiliary, target, source);
        }
    }
}

在上述代碼中，hanoi方法使用遞歸算法來解決漢諾塔問題。它接受四個參數：num表示盤子的數量，source表示源柱，target表示目標柱，auxiliary表示輔助柱。

2. 迭代算法：

public class TowerHanoi {
    public static void main(String[] args) {
        int num = 3;
        String source = "A";
        String target = "C";
        String auxiliary = "B";
        hanoi(num, source, target, auxiliary);
    }

    public static void hanoi(int num, String source, String target, String auxiliary) {
        // 創建一個列表來存儲盤子的移動過程
        Stack<String> moves = new Stack<>();

        while (num > 0) {
            // 將 num-1 個盤子從源柱移動到輔助柱（借助目標柱）
            for (int i = num - 1; i >= 0; i--) {
                moves.push(source + " -> " + auxiliary);
                source = (source.charAt(0) == 'A'? source : source.substring(1)) + source.charAt(0);
            }
            // 將第 num 個盤子從源柱移動到目標柱
            moves.push(source + " -> " + target);
            // 將 num-1 個盤子從輔助柱移動到目標柱（借助源柱）
            for (int i = num - 1; i >= 0; i--) {
                moves.push(auxiliary + " -> " + target);
                target = (target.charAt(0) == 'C'? target : target.substring(1)) + target.charAt(0);
            }
            // 源柱和輔助柱交換位置
            String temp = source;
            source = auxiliary;
            auxiliary = temp;
            // 減少盤子的數量
            num--;
        }

        for (String move : moves) {
            System.out.println(move);
        }
    }
}

在上述代碼中，hanoi方法使用迭代算法來解決漢諾塔問題。它創建一個列表moves來存儲盤子的移動過程。

反轉單向鏈表

在 Java 中，反轉單向鏈表的算法可以通過迭代和指針操作來完成。以下是一個簡單的示例代碼：

public class LinkedListReversal {

    public static void main(String[] args) {
        // 創建一個單向鏈表
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        // 打印反轉前的鏈表
        System.out.println("Original LinkedList: ");
        printList(n1);

        // 反轉鏈表
        Node reversedList = reverseList(n1);

        // 打印反轉后的鏈表
        System.out.println("Reversed LinkedList: ");
        printList(reversedList);
    }

    // 定義節點類
    static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    // 反轉鏈表的方法
    public static Node reverseList(Node head) {
        Node prev = null;
        Node current = head;
        Node next = null;

        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        return prev;
    }

    // 打印鏈表的方法
    public static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

上述代碼定義了一個Node類來表示鏈表中的節點，然后通過reverseList方法實現了反轉鏈表的功能。該方法使用三個指針prev、current和next，通過將當前節點的next指針指向前一個節點，并更新prev和current指針的方式，逐個反轉鏈表中的節點。最后，返回反轉后的頭節點。

在main方法中，創建了一個單向鏈表，并調用reverseList方法反轉鏈表，然后通過printList方法打印反轉前后的鏈表內容。

刪除倒數節點

刪除鏈表的倒數第n個節點，可以使用雙指針法，也可以使用棧來實現。下面是兩種算法的示例代碼：

雙指針法：

public static ListNode removeNthFromEnd(ListNode head, int n) {
    // 哨兵節點
    ListNode sb = new ListNode();
    sb.next = head;

    // k 快指針，m 慢指針
    ListNode k = sb, m = sb;
    int count = 0;
    while (k.next != null) {
        k = k.next;
        // 快指針先走 N 步
        if (++count > n) {
            m = m.next;
        }
    }
    m.next = m.next.next;
    return sb.next;
}

棧法：

public static ListNode removeNthFromEnd2(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    Stack<ListNode> stack = new Stack<>();
    ListNode cur = dummy;

    // 先入棧
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }

    // 出棧后 N 個節點
    for (int i = 0; i < n; i++) {
        stack.pop();
    }

    // 獲取到倒數第 N+1 個 node
    ListNode node = stack.peek();
    node.next = node.next.next;
    return dummy.next;
}

雙指針法的時間復雜度為 O(n)，棧法的時間復雜度為 O(n)，空間復雜度均為 O(1)。

有序鏈表去重

在 Java 中，有序鏈表去重可以使用雙指針的方法進行實現。以下是一個簡單的示例代碼：

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class RemoveDuplicatesFromSortedList {
    public ListNode removeDuplicates(ListNode head) {
        // 創建前指針和后指針
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            // 如果后指針指向的節點值與當前節點值相同，則跳過當前節點
            if (prev != null && prev.val == curr.val) {
                curr = curr.next;
            } else {
                // 更新前指針和后指針
                prev = curr;
                curr = curr.next;
            }
        }

        return prev;
    }

    public static void main(String[] args) {
        // 創建測試鏈表
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(4);
        ListNode node7 = new ListNode(5);
        ListNode node8 = new ListNode(5);

        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;

        RemoveDuplicatesFromSortedList solution = new RemoveDuplicatesFromSortedList();
        // 調用去重方法
        ListNode result = solution.removeDuplicates(head);

        // 打印去重后的鏈表
        System.out.println("去重后的鏈表:");
        solution.printList(result);
    }
}

在上述代碼中，removeDuplicates方法接受一個有序鏈表的頭節點作為參數，并返回去重后的鏈表的頭節點。在方法內部，使用了兩個指針prev和curr，分別表示前一個節點和當前節點。遍歷整個鏈表，如果后一個節點的值與前一個節點的值相同，則跳過當前節點，否則更新prev和curr的值。最后，返回prev，即為去重后的鏈表的頭節點。

在main方法中，創建了一個有序鏈表，并調用removeDuplicates方法進行去重。最后，打印出去重后的鏈表。

下面是一個經過性能優化的示例代碼：

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class RemoveDuplicatesFromSortedList {
    public ListNode removeDuplicates(ListNode head) {
        // 使用虛擬頭節點
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 使用快指針和慢指針
        ListNode fast = dummy;
        ListNode slow = dummy;

        while (fast.next != null) {
            // 緩存當前節點的值
            int currVal = fast.next.val;

            while (fast.next != null && fast.next.val == currVal) {
                fast.next = fast.next.next;
            }

            // 更新慢指針和虛擬頭節點的 next 指針
            slow.next = fast.next;
            fast = slow.next;
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        // 創建測試鏈表
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(4);
        ListNode node7 = new ListNode(5);
        ListNode node8 = new ListNode(5);

        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;

        RemoveDuplicatesFromSortedList solution = new RemoveDuplicatesFromSortedList();
        // 調用去重方法
        ListNode result = solution.removeDuplicates(head);

        // 打印去重后的鏈表
        System.out.println("去重后的鏈表:");
        solution.printList(result);
    }

    // 打印鏈表的方法
    public void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}

在這個優化后的代碼中，使用了虛擬頭節點和雙指針來優化遍歷和刪除操作。此外，還使用了緩存來避免重復比較節點值。這些優化可以提高代碼的性能，特別是在處理大規模數據時。

合并有序鏈表算法

以下是兩種常見的合并有序鏈表的算法：

• 遞歸算法：
  • 判斷兩個鏈表的當前節點誰大誰小，將小的那個節點賦值給需要合并的鏈表；
  • 移動到較小鏈表的下一個節點，依次遞歸合并。
• 非遞歸算法：
  • 創建一個新的指針head，在兩個指針所指都不是null時，讓head指向data更小的那個；
  • 更新node1和node2的指針，讓它們分別指向各自鏈表中的下一個節點；
  • 讓head指針也向后移動，即head = head.next ，直到其中一個鏈表為空，將另一個鏈表的剩余節點合并到合并鏈表的后面。

判環算法

判環算法是一種常見的鏈表問題，用于判斷鏈表是否存在環。以下是一個基于Java的判環算法實現：

public boolean hasCycle(ListNode head) {
    ListNode p1 = head;  //烏龜
    ListNode p2 = head;  //兔子

    while (p2 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next.next;

        if (p1 == p2) {
            return true;
        }
    }

    return false;
}

該算法使用兩個指針p1和p2，分別指向鏈表的頭和尾。如果存在環，則最終p1和p2會相遇，算法返回true；否則，算法返回false。

java回溯算法、貪心算法、分治算法

好的，回溯算法、貪心算法和分治算法是常見的算法設計思想，可以用于解決不同類型的問題。以下是對這三種算法的簡單介紹：

回溯算法：回溯算法是一種通過遞歸或迭代的方式進行深度優先搜索的算法。它從一個起始狀態開始，然后逐步嘗試不同的可能路徑，直到找到目標狀態或達到搜索的邊界。在回溯過程中，如果遇到不滿足條件的情況，算法會回溯到上一個狀態，并嘗試其他可能的路徑。回溯算法常用于解決一些復雜的問題，如八皇后問題、圖的著色問題等。

貪心算法：貪心算法是一種在每一步都選擇當前看起來最優的解決方案的算法。它在解決問題時做出局部最優選擇，希望通過一系列局部最優選擇來達到全局最優解。貪心算法通常在每一步都不考慮整體問題的最優解，而是只考慮當前步驟的最優選擇。貪心算法常用于優化問題，如找零問題、最小生成樹問題等。

分治算法：分治算法是一種將大問題分解為小問題，并分別解決小問題的算法。它通過遞歸的方式將問題分解成子問題，然后對子問題進行求解，最后將子問題的解合并成原始問題的解。分治算法的核心思想是將問題規模縮小，從而降低問題的復雜性。分治算法常用于排序問題（如快速排序）、矩陣乘法等。

這三種算法在不同的問題中有不同的應用場景。回溯算法適用于解決復雜的搜索問題，貪心算法適用于優化問題，而分治算法適用于遞歸可分解的問題。在實際應用中，需要根據具體問題的特點選擇合適的算法。

下面是一個簡單的 Java 示例，演示了如何使用回溯算法解決八皇后問題：

public class EightQueens {
    public static void main(String[] args) {
        int n = 8;
        solveNQueens(n);
    }

    private static void solveNQueens(int n) {
        // 定義棋盤數組
        boolean[][] board = new boolean[n][n];

        // 放置第一個皇后
        placeQueen(0, 0, board);

        // 如果沒有放置成功，則回溯
        if (!isPlaceValid(0, 0, board)) {
            return;
        }

        // 遞歸放置其他皇后
        solveNQueens(n - 1);
    }

    private static void placeQueen(int row, int col, boolean[][] board) {
        // 在當前位置放置皇后
        board[row][col] = true;

        // 檢查是否與其他皇后沖突
        for (int i = 0; i < row; i++) {
            if (board[i][col]) {
                // 沖突，回溯
                board[row][col] = false;
                return;
            }
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j]) {
                // 沖突，回溯
                board[row][col] = false;
                return;
            }
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j]) {
                // 沖突，回溯
                board[row][col] = false;
                return;
            }
        }
    }

    private static boolean isPlaceValid(int row, int col, boolean[][] board) {
        // 檢查同一列是否有皇后
        for (int i = 0; i < row; i++) {
            if (board[i][col]) {
                return false;
            }
        }

        // 檢查左上角到右下角的對角線是否有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j]) {
                return false;
            }
        }

        // 檢查右上角到左下角的對角線是否有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j]) {
                return false;
            }
        }

        // 如果沒有沖突，則返回 true
        return true;
    }
}

這段代碼使用了遞歸回溯的方法來解決八皇后問題。遞歸函數 solveNQueens 嘗試在棋盤的每一行放置一個皇后，并通過調用 placeQueen 函數來放置皇后。如果放置成功，則繼續遞歸放置下一行的皇后。如果放置失敗，則回溯到上一行，并嘗試其他位置。

placeQueen 函數用于在指定位置放置皇后，并檢查是否與其他皇后沖突。如果沒有沖突，則返回 true；否則，返回 false，并回溯到上一個狀態。

isPlaceValid 函數用于檢查當前位置是否可以放置皇后。它檢查同一列、主對角線和副對角線上是否有其他皇后。

通過遞歸回溯和狀態檢查，算法最終找到了所有可行的八皇后放置方案。