几乎所有中大型互联网企业都将算法能力作为招聘与晋升的核心指标之一。从阿里、腾讯、字节跳动到华为、百度、拼多多,算法题几乎成为技术面试的「标配」。
算法不仅是解题技巧,更是编程思维的系统训练。通过分析问题结构、抽象模型、设计策略,逐步培养“问题分解→建模→实现→优化”的全链路能力。
无论是分布式系统设计、数据库查询优化、搜索引擎排序,还是人工智能模型训练,底层都离不开高效的数据结构与算法支撑。掌握算法,才能真正理解技术本质。
本文面向Java初学者,以循序渐进的方式讲解算法入门所需的核心知识。从基本概念到常见题型,从思维建模到代码实现,层层递进。全站无跳转,所有内容通过锚点导航直达,支持手机与桌面端无缝阅读。
内容覆盖:算法基础概念、时间复杂度分析、经典排序算法、递归与分治策略、动态规划思想、贪心算法原理,以及配套的Java代码实现与高频面试题解析。
理解算法本质:算法是解决特定问题的有限指令序列。强调“正确性”“可读性”“效率”三大核心指标。通过生活类比(如找零钱、排序书籍)建立直觉认知。
掌握数组、字符串、栈与队列、链表四大线性结构,理解其操作复杂度。重点练习:遍历、插入删除、反转、查找、合并等基础操作。
系统学习:排序算法(冒泡、选择、插入、归并、快速)、查找算法(顺序、二分)、递归与分治思想。通过LeetCode前100题实战巩固。
深入理解动态规划(状态定义、转移方程、边界条件)、贪心算法(局部最优→全局最优的适用场景)、回溯法(状态空间树遍历)。
结合真实项目场景:如电商秒杀限流(滑动窗口)、日志去重(布隆过滤器)、路径规划(BFS/DFS)、字符串匹配(KMP)等,提升工程化算法思维。
复杂度分析是算法评估的基石,它不依赖具体机器环境,仅关注输入规模增长时的性能变化趋势。分为时间复杂度(执行时间随输入规模的增长率)与空间复杂度(额外内存使用量)。
采用大O表示法:O(f(n)),仅保留最高阶项,忽略常数与低阶项。
// O(1):常数时间
int a = arr[5]; // 数组索引访问
map.put("key", value); // 哈希表插入(平均)
set.add(100); // HashSet添加元素(平均)
// O(n):线性时间
for (int i = 0; i < n; i++) {
System.out.println(i);
}
// O(n²):平方时间
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
process(i, j);
}
}
// O(log n):对数时间
while (n > 1) {
n = n / 2;
}
| 算法 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
排序是算法入门的“第一课”,掌握其原理与实现对后续学习至关重要。以下为五种基础排序算法的Java实现与解析。
原理:重复遍历数组,比较相邻元素,若顺序错误则交换。每轮将最大值“冒泡”至末尾。
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]) {
// 交换相邻元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
原理:每轮从未排序部分选择最小值,放到已排序序列末尾。
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 将最小值交换到当前位置
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
原理:构建有序序列,对未排序数据,在已排序序列中从后向前扫描,找到对应位置并插入。
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将大于key的元素后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
原理:分治策略——先递归拆分数组为单个元素,再合并两个有序数组。
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
原理:选择基准(pivot),将数组划分为小于与大于基准的两部分,递归排序子数组。
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = 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;
}
前提:有序数组。时间复杂度O(log n)。
public static 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;
}
public static int binarySearchFirst(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > target) right = mid - 1;
else if (arr[mid] < target) left = mid + 1;
else {
if (mid == 0 || arr[mid - 1] != target) return mid;
right = mid - 1;
}
}
return -1;
}
递归是函数调用自身的过程,需满足:有终止条件、问题可分解、子问题与原问题同构。
// 递归版(低效,存在重复计算)
public static long fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// 优化版:记忆化递归
public static long fibMemo(int n, long[] memo) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// 迭代版(最优)
public static long fibIter(int n) {
if (n <= 1) return n;
long a = 0, b = 1;
for (int i = 2; i <= n; i++) {
long temp = a + b;
a = b;
b = temp;
}
return b;
}
分治三步:分解 → 解决 → 合并。归并排序完美体现该思想,将大数组递归拆分,再合并有序子数组。
DP核心:将原问题拆解为子问题,通过存储子问题解避免重复计算。关键四要素:状态定义、状态转移方程、初始条件、计算顺序。
问题:每次可爬1或2阶,n阶有多少种方法?
// dp[i] 表示到达第i阶的方法数
// 转移:dp[i] = dp[i-1] + dp[i-2]
public static 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];
}
// 空间优化版
public static int climbStairsOpt(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}
有n个物品,重量为weight[i],价值为value[i],背包容量为W,求最大价值。
public static int knapsack(int[] weight, int[] value, int W) {
int n = weight.length;
int[] dp = new int[W + 1]; // dp[j] 表示容量j的最大价值
for (int i = 0; i < n; i++) {
for (int j = W; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[W];
}
贪心策略:每一步都做当前最优选择,期望全局最优。注意:并非所有问题都适用,需证明其正确性。
问题:每个孩子最多一块饼干,饼干大小需≥孩子胃口值,求最多满足几个孩子。
public static int findContentChildren(int[] g, int[] s) {
Arrays.sort(g); // 孩子胃口值升序
Arrays.sort(s); // 饼干尺寸升序
int i = 0, j = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) {
i++; // 满足一个孩子
}
j++; // 尝试下一块饼干
}
return i;
}
currentIndex 而非 idx)long 替代 int,或使用 Math.addExact()double,用误差范围 Math.abs(a-b) < 1e-6arr.length - 1A:完全可以!建议从简单题开始,如“两数之和”“反转链表”,配合可视化工具理解过程。坚持每日练习,3个月可见显著提升。
A:非常有用!例如:用哈希表优化查找性能、用队列实现消息缓冲、用树结构管理组织架构。高效算法能显著提升系统性能与稳定性。
A:可能陷入“背题”陷阱。正确做法是:理解每道题的“解题模板”,如滑动窗口适用于连续子数组问题,回溯适用于组合/排列问题。
A:Java更严谨,适合培养工程化思维;Python更简洁,适合快速验证思路。推荐初学者用Java,因企业面试多用Java/C++。
A>① 每日一题,保持手感;② 总结模板,形成知识图谱;③ 参与代码评审,学习他人解法;④ 建立错题本,定期复盘。