一、分治类算法思想

  1. 分治法 (Divide and Conquer)

    核心：将问题分解为子问题→递归解决→合并结果

    Java示例：二分查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    场景：有序数据查询（时间复杂度： O(log n) ）

  2. 归并排序

    核心：数组分半排序 → 合并有序子数组

    1
    2
    3
    4
    5
    6
    7
    8
    void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int mid = (l + r) / 2;
            mergeSort(arr, l, mid);    // 分治左半
            mergeSort(arr, mid + 1, r);// 分治右半
            merge(arr, l, mid, r);     // 合并结果
        }
    }

    场景：大数据量稳定排序（时间复杂度： O(n log n) ）

  3. 快速排序

    核心：基准分区 → 递归排序子分区

    1
    2
    3
    4
    5
    6
    7
    void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high); // 分区函数
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    场景：通用高效排序（平均 O(n log n) ，最坏 O(n²) ）

二、优化类算法思想

  1. 动态规划 (Dynamic Programming)

    核心：存储子问题解 → 避免重复计算 → 组合最优解

    Java示例：斐波那契数列

    1
    2
    3
    4
    5
    6
    7
    8
    int fib(int 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];
    }

    场景：背包问题、最短路径

  2. 贪心算法 (Greedy)

    核心：局部最优 → 期望全局最优

    Java示例：找零钱问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    List<Integer> coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        List<Integer> res = new ArrayList<>();
        for (int i = coins.length - 1; i >= 0; i--) {
            while (amount >= coins[i]) { // 每次选最大面额
                amount -= coins[i];
                res.add(coins[i]);
            }
        }
        return res;
    }

    场景：霍夫曼编码、Dijkstra算法（不保证全局最优）

三、搜索与枚举类算法

  1. 回溯法 (Backtracking)

    核心：尝试路径 → 失败则回退 → 枚举所有解

    Java示例：全排列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void backtrack(List<List<Integer>> res, List<Integer> tmp, int[] nums) {
        if (tmp.size() == nums.length) {
            res.add(new ArrayList<>(tmp)); // 记录解
            return;
        }
        for (int num : nums) {
            if (tmp.contains(num)) continue;
            tmp.add(num);             // 尝试选择
            backtrack(res, tmp, nums); // 递归
            tmp.remove(tmp.size() - 1);// 回退
        }
    }

    场景：N皇后、数独（时间复杂度常为 O(n!) ）

  2. 穷举法 (Brute Force)

    核心：遍历所有可能解 → 验证正确性

    Java示例：线性搜索

    1
    2
    3
    4
    5
    6
    int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i; // 逐个比较
        }
        return -1;
    }

    场景：小规模问题（简单但效率低 O(n) ）

  3. 分支限界法 (Branch and Bound)

    核心：回溯法 + 剪枝优化 → 减少无效搜索

    场景：旅行商问题（TSP），需结合优先级队列实现

四、迭代与递归思想

  1. 迭代法 (Iterative)

    核心：循环逼近解

    Java示例：计算阶乘

    1
    2
    3
    4
    5
    6
    7
    int factorial(int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;  // 循环累积
        }
        return result;
    }

    场景：避免递归栈溢出

  2. 递归法 (Recursion)

    核心：函数自调用 → 分解为同类子问题

    Java示例：汉诺塔

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void hanoi(int n, char from, char to, char aux) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + from + " to " + to);
            return;
        }
        hanoi(n - 1, from, aux, to);    // 分解为n-1问题
        System.out.println("Move disk " + n + " from " + from + " to " + to);
        hanoi(n - 1, aux, to, from);
    }

    场景：树遍历、分治基础（警惕栈溢出）

五、其他实用技巧

  1. 双指针 (Two Pointers)

    核心：两指针协同遍历 → 降时间复杂度

    Java示例：有序数组去重

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int removeDuplicates(int[] nums) {
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                nums[++slow] = nums[fast]; // 快慢指针赋值
            }
        }
        return slow + 1;
    }

    场景：链表环检测、滑动窗口

  2. 滑动窗口 (Sliding Window)

    核心：动态调整窗口范围 → 高效连续子集处理

    场景：字符串子串匹配、数组连续最值

  3. 位运算 (Bit Manipulation)

    核心：使用位操作加速计算

    Java示例：判断奇偶

    1
    2
    3
    boolean isOdd(int n) {
        return (n & 1) == 1;  // 与运算替代取模
    }

    场景：加密算法、高性能计算

六、算法思想对比表

思想类型 时间复杂度 空间复杂度 特点 典型应用
分治法 O(n log n) O(n) 递归分层处理 归并排序、快速排序
动态规划 O(n²) 或 O(n) O(n) 避免重复子计算 斐波那契、背包问题
贪心算法 O(n log n) O(1) 局部最优但不保全局最优 找零钱、Dijkstra
回溯法 O(n!) O(n) 试错回退 八皇后、全排列
双指针 O(n) O(1) 降低遍历复杂度 数组去重、链表操作
分支限界法 O(b^d) O(bd) 回溯+剪枝 旅行商问题(TSP)