import java.util.*;

// 1. 對(duì)List排序
List<Integer> numbersList = new ArrayList<>(Arrays.asList(23, 5, 42, -1, 99));
Collections.sort(numbersList);
System.out.println("Sorted List: " + numbersList); // 輸出: Sorted List: [-1, 5, 23, 42, 99]

// 2. 對(duì)數(shù)組排序
int[] numbersArray = {23, 5, 42, -1, 99};
Arrays.sort(numbersArray);
System.out.println("Sorted Array: " + Arrays.toString(numbersArray)); // 輸出: Sorted Array: [-1, 5, 23, 42, 99]

// 3. 自定義排序規(guī)則（使用Comparator）
List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "David");
// 按字符串長(zhǎng)度排序
Collections.sort(names, (a, b) -> a.length() - b.length());
// 或使用方法引用：Collections.sort(names, Comparator.comparingInt(String::length));
System.out.println("Sorted by length: " + names); // 輸出: Sorted by length: [Bob, Alice, David, Charlie]

List<Integer> sortedList = Arrays.asList(10, 20, 30, 40, 50);
int index1 = Collections.binarySearch(sortedList, 30);
System.out.println("Index of 30: " + index1); // 輸出: 2 (找到了)

int index2 = Collections.binarySearch(sortedList, 25);
System.out.println("Index of 25: " + index2); // 輸出: -3 (未找到。插入點(diǎn)應(yīng)為 2, 所以返回 -2-1 = -3)

int[] sortedArray = {10, 20, 30, 40, 50};
int index3 = Arrays.binarySearch(sortedArray, 40);
System.out.println("Index of 40 in array: " + index3); // 輸出: 3

List<Integer> cards = new ArrayList<>();
for (int i = 1; i <= 10; i++) {
    cards.add(i);
}
System.out.println("Original deck: " + cards);
Collections.shuffle(cards);
System.out.println("Shuffled deck: " + cards);

// 其他工具方法
Collections.reverse(cards);
System.out.println("Reversed deck: " + cards);

int max = Collections.max(cards);
int frequencyOfFive = Collections.frequency(cards, 5);
System.out.println("Max card: " + max + ", Frequency of 5: " + frequencyOfFive);

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交換 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // 找到，返回索引
        }
    }
    return -1; // 未找到
}

// 簡(jiǎn)單遞歸（效率極低，存在大量重復(fù)計(jì)算）
public static int fibonacciRecursive(int n) {
    if (n <= 1) return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// 使用動(dòng)態(tài)規(guī)劃（迭代+記憶化，高效）
public static int fibonacciDP(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 使用鄰接表（最常用）
// 1. 使用 Map 和 List
Map<Integer, List<Integer>> graph = new HashMap<>();
// 2. 或創(chuàng)建一個(gè) Node 類
class GraphNode {
    int val;
    List<GraphNode> neighbors;
    GraphNode(int x) { val = x; neighbors = new ArrayList<>(); }
}

// 使用二維數(shù)組（鄰接矩陣）表示帶權(quán)圖
int[][] graphMatrix;

public int bfsShortestPath(Map<Integer, List<Integer>> graph, int start, int end) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    Map<Integer, Integer> distance = new HashMap<>(); // 記錄到起點(diǎn)的距離

    queue.offer(start);
    visited.add(start);
    distance.put(start, 0);

    while (!queue.isEmpty()) {
        int currentNode = queue.poll();
        if (currentNode == end) {
            return distance.get(currentNode);
        }
        for (int neighbor : graph.getOrDefault(currentNode, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
                distance.put(neighbor, distance.get(currentNode) + 1);
            }
        }
    }
    return -1; // 未找到路徑
}

public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
// 可以進(jìn)一步優(yōu)化空間復(fù)雜度到 O(1)，只保留前兩個(gè)狀態(tài)