30个经典算法题及Java解答(含实例代码)

前言

算法面试中，最怕的不是题目难，而是见过但写不出来。这里整理了一份高频算法题的实战清单，覆盖了排序、搜索、动态规划、链表、树、图等核心类别，每个题目都附上了可直接运行的Java实现。为了方便理解，每个题目都拆成了三部分：问题描述、核心思路、以及代码解答。所有代码都经过实际测试，可以直接复制到项目中使用。闲话不多说，直接上干货。

1. 快速排序

题目描述：实现快速排序算法，对整数数组进行升序排序。

关键思路：基于分治策略，选择一个基准元素，将数组划分为小于基准和大于等于基准的两部分，然后递归排序。平均时间复杂度为$O(n \log n)$，实际应用中表现非常稳定。

Java解答：

public class QuickSort {
    public 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);
        }
    }
    
    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

2. 二分查找

题目描述：在已排序整数数组中查找目标值，返回其索引，若不存在返回-1。

关键思路：每次比较中间元素，根据大小关系缩小搜索范围。时间复杂度$O(\log n)$，是分治思想的经典应用。

Java解答：

public class BinarySearch {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

3. 冒泡排序

题目描述：实现冒泡排序算法，对整数数组进行升序排序。

关键思路：重复遍历数组，比较相邻元素并交换，直到没有交换发生。时间复杂度$O(n^2)$，适合小规模数据。

Java解答：

public class BubbleSort {
    public 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]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

4. 选择排序

题目描述：实现选择排序算法，对整数数组进行升序排序。

关键思路：每次从未排序部分选出最小元素，放到已排序部分末尾。时间复杂度$O(n^2)$。

Java解答：

public class SelectionSort {
    public void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) minIdx = j;
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }
}

5. 插入排序

题目描述：实现插入排序算法，对整数数组进行升序排序。

关键思路：将每个元素插入到已排序部分的正确位置，像打牌时整理手牌。时间复杂度$O(n^2)$，但在近乎有序的数据上表现很好。

Java解答：

public class InsertionSort {
    public void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

6. 归并排序

题目描述：实现归并排序算法，对整数数组进行升序排序。

关键思路：分治策略，递归将数组分成两半，分别排序后合并。时间复杂度$O(n \log n)$，稳定且适合外部排序。

Java解答：

public class MergeSort {
    public void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    private void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) arr[k++] = L[i++];
            else arr[k++] = R[j++];
        }
        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }
}

7. 堆排序

题目描述：实现堆排序算法，对整数数组进行升序排序。

关键思路：构建最大堆，然后反复将堆顶元素与末尾元素交换，并调整堆。时间复杂度$O(n \log n)$，无需额外空间。

Java解答：

public class HeapSort {
    public void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    
    private void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
}

8. 计数排序

题目描述：实现计数排序算法，对非负整数数组进行升序排序。

关键思路：统计每个元素出现次数，然后根据计数重建有序数组。时间复杂度$O(n + k)$，$k$为最大值，适合数据范围不大的场景。

Java解答：

public class CountingSort {
    public void countingSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();
        int range = max - min + 1;
        int[] count = new int[range];
        int[] output = new int[arr.length];
        for (int num : arr) count[num - min]++;
        for (int i = 1; i < range; i++) count[i] += count[i - 1];
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

9. 桶排序

题目描述：实现桶排序算法，对浮点数数组进行升序排序。

关键思路：将元素分布到多个桶中，对每个桶单独排序，然后合并。平均时间复杂度$O(n + k)$，适合均匀分布的数据。

Java解答：

import java.util.*;

public class BucketSort {
    public void bucketSort(float[] arr) {
        int n = arr.length;
        List[] buckets = new ArrayList[n];
        for (int i = 0; i < n; i++) buckets[i] = new ArrayList<>();
        for (float num : arr) {
            int idx = (int) (num * n);
            buckets[idx].add(num);
        }
        for (List bucket : buckets) Collections.sort(bucket);
        int index = 0;
        for (List bucket : buckets) {
            for (float num : bucket) arr[index++] = num;
        }
    }
}

10. 基数排序

题目描述：实现基数排序算法，对非负整数数组进行升序排序。

关键思路：按位从低到高进行排序，每次使用稳定排序（如计数排序）。时间复杂度$O(d \cdot (n + k))$，$d$为位数。

Java解答：

public class RadixSort {
    public void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        for (int exp = 1; max / exp > 0; exp *= 10) countSort(arr, exp);
    }
    
    private void countSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];
        for (int num : arr) count[(num / exp) % 10]++;
        for (int i = 1; i < 10; i++) count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        System.arraycopy(output, 0, arr, 0, n);
    }
}

11. 斐波那契数列

题目描述：计算第n个斐波那契数，其中$F(0) = 0$, $F(1) = 1$。

关键思路：递推公式$F(n) = F(n-1) + F(n-2)$，用动态规划（滚动变量）优化，避免递归的指数爆炸。

Java解答：

public class Fibonacci {
    public int fib(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}

12. 两数之和

题目描述：在整数数组中找到两个数，使它们的和等于目标值，返回其索引。

关键思路：哈希表存储元素值到索引的映射，遍历时检查补数是否存在。时间复杂度$O(n)$，空间换时间的经典用法。

Java解答：

import java.util.*;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) return new int[]{map.get(complement), i};
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

13. 反转链表

题目描述：反转一个单链表。

关键思路：迭代法，遍历链表时逐个改变指针方向。递归方法也可行，但迭代更省空间。

Java解答：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class ReverseLinkedList {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

14. 判断回文链表

题目描述：判断单链表是否为回文结构。

关键思路：快慢指针找到中点，反转后半部分，然后比较。注意边界条件。

Java解答：

public class PalindromeLinkedList {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode secondHalf = reverse(slow);
        ListNode p1 = head, p2 = secondHalf;
        while (p2 != null) {
            if (p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
    
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

15. 判断回文字符串

题目描述：判断字符串是否为回文（忽略大小写和非字母数字字符）。

关键思路：双指针从两端向中间比较，跳过非字母数字字符。注意大小写统一。

Java解答：

public class PalindromeString {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase().replaceAll("[^a-z0-9]", "");
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }
}

16. 最长公共子序列

题目描述：求两个字符串的最长公共子序列（LCS）长度。

关键思路：动态规划，状态转移方程： $$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } s1[i-1] = s2[j-1] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases}$$

Java解答：

public class LongestCommonSubsequence {
    public int lcs(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
}

17. 最长递增子序列

题目描述：求整数数组的最长递增子序列（LIS）长度。

关键思路：动态规划$dp[i] = \max(dp[i], dp[j] + 1)$ for $j < i$ and $arr[j] < arr[i]$。也可以结合贪心+二分查找，将时间复杂度降到$O(n \log n)$。

Java解答：

import java.util.*;

public class LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

18. 0-1背包问题

题目描述：给定物品重量和价值，在背包容量限制下求最大价值。

关键思路：动态规划，状态转移： $$dp[i][w] = \max(dp[i-1][w], dp[i-1][w - \text{weight}[i]] + \text{value}[i])$$

Java解答：

public class Knapsack {
    public int knapSack(int W, int[] wt, int[] val) {
        int n = wt.length;
        int[][] dp = new int[n + 1][W + 1];
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                if (wt[i - 1] <= w) dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
                else dp[i][w] = dp[i - 1][w];
            }
        }
        return dp[n][W];
    }
}

19. 硬币找零问题

题目描述：给定硬币面额和总金额，求凑成金额的最少硬币数。

关键思路：动态规划，$dp[i]$ 表示金额$i$的最小硬币数，$dp[i] = \min(dp[i], dp[i - \text{coin}] + 1)$。

Java解答：

import java.util.*;

public class CoinChange {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

20. 最大子数组和

题目描述：求整数数组的连续子数组的最大和。

关键思路：Kadane算法，动态规划：当前和 = max(当前元素, 当前和+当前元素)，同时维护全局最大和。

Java解答：

public class MaximumSubarray {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0], currentSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}

21. 二叉树的前序遍历

题目描述：实现二叉树的前序遍历（根-左-右）。

关键思路：递归或迭代。迭代用栈模拟，注意先压右子节点后压左子节点。

Java解答：

import java.util.*;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class PreorderTraversal {
    public List preorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        if (root == null) return res;
        Stack stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return res;
    }
}

22. 二叉树的中序遍历

题目描述：实现二叉树的中序遍历（左-根-右）。

关键思路：迭代用栈，一直向左走到尽头，然后出栈访问，再转向右子树。

Java解答：

import java.util.*;

public class InorderTraversal {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        Stack stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

23. 二叉树的后序遍历

题目描述：实现二叉树的后序遍历（左-右-根）。

关键思路：迭代用两个栈，或者一个栈加反转。这里用栈模拟，先根后右再左，最后反转结果。

Java解答：

import java.util.*;

public class PostorderTraversal {
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        if (root == null) return res;
        Stack stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(0, node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return res;
    }
}

24. 二叉树的最大深度

题目描述：求二叉树的最大深度（根节点到最远叶子节点的路径长度）。

关键思路：递归计算左右子树深度，取最大值加1。

Java解答：

public class MaxDepth {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

25. 二叉树的直径

题目描述：求二叉树的直径（任意两节点间最长路径长度）。

关键思路：深度优先搜索，在递归中维护全局最大直径，路径长度为左右子树高度之和。

Java解答：

public class DiameterOfBinaryTree {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }
    
    private int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        max = Math.max(max, left + right);
        return Math.max(left, right) + 1;
    }
}

26. 二叉搜索树验证

题目描述：验证二叉树是否为二叉搜索树（BST）。

关键思路：递归检查节点值是否在合法区间内，或者中序遍历序列是否为升序。

Java解答：

public class ValidateBST {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean helper(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        return helper(node.left, min, node.val) && helper(node.right, node.val, max);
    }
}

27. 图的深度优先搜索

题目描述：实现图的深度优先搜索（DFS），从给定节点遍历所有节点。

关键思路：递归或栈，配合标记集合避免重复访问。

Java解答：

import java.util.*;

public class GraphDFS {
    private Map> graph;
    private Set visited;
    
    public void dfs(int start) {
        visited = new HashSet<>();
        dfsHelper(start);
    }
    
    private void dfsHelper(int node) {
        visited.add(node);
        System.out.print(node + " ");
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) dfsHelper(neighbor);
        }
    }
    
    // 初始化图：graph = new HashMap<>(); 添加节点和邻接表
}

28. 图的广度优先搜索

题目描述：实现图的广度优先搜索（BFS），从给定节点遍历所有节点。

关键思路：队列，按层遍历，配合标记集合。

Java解答：

import java.util.*;

public class GraphBFS {
    public void bfs(Map> graph, int start) {
        Set visited = new HashSet<>();
        Queue queue = new LinkedList<>();
        queue.add(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }
}

29. Dijkstra算法

题目描述：实现Dijkstra算法，求单源最短路径（无负权边）。

关键思路：优先队列（最小堆）维护节点距离，每次取出最近节点，松弛其邻接边。注意处理重复节点。

Java解答：

import java.util.*;

public class Dijkstra {
    public int[] dijkstra(List> graph, int n, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{src, 0});
        while (!pq.isEmpty()) {
            int[] node = pq.poll();
            int u = node[0], d = node[1];
            if (d > dist[u]) continue;
            for (int[] edge : graph.get(u)) {
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }
        return dist;
    }
    
    // 初始化图：graph = new ArrayList<>(); 添加邻接表 [节点, 权重]
}

30. Kruskal算法

题目描述：实现Kruskal算法，求最小生成树。

关键思路：并查集管理连通分量，按边权重升序排序，依次加入不形成回路的边。

Java解答：

import java.util.*;

public class Kruskal {
    static class Edge {
        int src, dest, weight;
        Edge(int s, int d, int w) { src = s; dest = d; weight = w; }
    }
    
    private int[] parent;
    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    private void union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx != ry) parent[rx] = ry;
    }
    
    public List kruskalMST(List edges, int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        Collections.sort(edges, (a, b) -> a.weight - b.weight);
        List mst = new ArrayList<>();
        for (Edge edge : edges) {
            if (find(edge.src) != find(edge.dest)) {
                mst.add(edge);
                union(edge.src, edge.dest);
            }
        }
        return mst;
    }
}

以上列表覆盖了排序、搜索、动态规划、链表、树、图等常见算法类别。每个解答均包含可复用的Java代码，可直接集成到项目中。

总结