Java算法面试题解析与实战
本文包含配套学习资料，点击获取 
简介：算法能力是互联网企业面试的核心考察点。本文聚焦谷歌、亚马逊等科技巨头的高频考题，覆盖数据结构、排序策略、图论应用等核心领域。通过系统化讲解与代码实践，帮助开发者掌握算法设计思维，提升工程化问题解决能力，为技术面试和实际开发奠定坚实基础。
- 数据结构与实现
1.1 Java数据结构概览
在软件开发中，合理选择数据结构直接影响程序性能。Java通过集合框架（Collection Framework）提供多样化的数据结构实现，包括基础类型如数组、链表，以及高级结构如栈、队列、树、图等。理解这些结构的特性与使用场景，是构建高效程序的基础。
1.2 集合框架应用实例
Java的集合体系通过接口继承实现高度扩展性。以下示例展示列表与集合的基本用法：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class DataStructureExample {
public static void main(String[] args) {
List<Integer> myList = new ArrayList<>();
myList.add(10);
myList.add(20);
myList.add(30);
Set<Integer> mySet = new HashSet<>();
mySet.add(10);
mySet.add(20);
mySet.add(30);
}
}
列表结构允许重复元素并保持插入顺序，而集合结构通过哈希机制实现元素唯一性。这种差异决定了它们在不同场景下的适用性。
- 排序算法实践
排序算法效率直接影响程序性能。本文将分析基础与高级排序算法的实现原理及适用场景。
2.1 基础排序算法
2.1.1 交换排序与选择排序
交换排序通过相邻元素比较实现有序化，而选择排序通过逐轮定位最小元素完成排序。
// 交换排序实现
public static void bubbleSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
// 选择排序实现
public static void selectionSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}
两种算法时间复杂度均为O(n²)，适用于小规模数据集或教学场景。
2.1.2 插入排序与快速排序
插入排序通过维护有序子序列实现排序，快速排序采用分治策略进行递归处理。
// 插入排序实现
public static void insertionSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int key = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = key;
}
}
// 快速排序实现
public static void quickSort(int[] nums, int low, int high) {
if (low < high) {
int pivot = partition(nums, low, high);
quickSort(nums, low, pivot - 1);
quickSort(nums, pivot + 1, high);
}
}
private static int partition(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (nums[j] <= pivot) {
i++;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
int temp = nums[i + 1];
nums[i + 1] = nums[high];
nums[high] = temp;
return i + 1;
}
快速排序平均效率为O(n log n)，通过随机化基准值可避免最坏情况。插入排序在部分有序数据中表现优异。
- 搜索算法应用
3.1 线性搜索与二分搜索
线性搜索逐个比对元素，适用于无序数据；二分搜索通过折半查找实现高效检索。
// 线性搜索实现
public int linearSearch(int[] data, int target) {
for (int i = 0; i < data.length; i++) {
if (data[i] == target) {
return i;
}
}
return -1;
}
// 二分搜索实现
public int binarySearch(int[] data, int target) {
int left = 0, right = data.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (data[mid] == target) {
return mid;
} else if (data[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
二分搜索要求数据有序，时间复杂度为O(log n)，适用于大规模数据检索。
3.2 深度优先与广度优先搜索
DFS通过递归实现深度遍历，BFS使用队列进行层次遍历。
// DFS实现
public void dfsTraversal(int[][] graph, int start, boolean[] visited) {
visited[start] = true;
System.out.print(start + " ");
for (int i = 0; i < graph[start].length; i++) {
if (graph[start][i] == 1 && !visited[i]) {
dfsTraversal(graph, i, visited);
}
}
}
// BFS实现
public void bfsTraversal(int[][] graph, int start) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[graph.length];
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.print(current + " ");
for (int i = 0; i < graph[current].length; i++) {
if (graph[current][i] == 1 && !visited[i]) {
queue.add(i);
visited[i] = true;
}
}
}
}
DFS适用于路径查找和拓扑排序，BFS常用于最短路径计算。
- 图论问题解决方案
图论研究节点与边的关系，广泛应用于网络分析、路径规划等领域。
4.1 图的表示与遍历
图的实现主要有邻接矩阵和邻接表两种方式。
// 邻接矩阵实现
public class GraphMatrix {
private int[][] matrix;
private int size;
public GraphMatrix(int size) {
this.size = size;
matrix = new int[size][size];
}
public void connectNodes(int src, int dest) {
matrix[src][dest] = 1;
matrix[dest][src] = 1;
}
}
// 邻接表实现
class Node {
int value;
List<Node> neighbors;
public Node(int value) {
this.value = value;
neighbors = new ArrayList<>();
}
}
public class GraphList {
private List<Node> nodes;
public GraphList(int size) {
nodes = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
nodes.add(new Node(i));
}
}
public void connect(int src, int dest) {
nodes.get(src).neighbors.add(nodes.get(dest));
nodes.get(dest).neighbors.add(nodes.get(src));
}
}
4.2 图算法应用
最短路径算法如Dijkstra和Floyd-Warshall，最小生成树算法如Kruskal和Prim。
// Dijkstra算法实现
public Map<Node, Integer> dijkstra(Node start) {
Map<Node, Integer> distances = new HashMap<>();
Set<Node> visited = new HashSet<>();
for (Node node : nodes) {
distances.put(node, Integer.MAX_VALUE);
}
distances.put(start, 0);
while (!visited.containsAll(nodes)) {
Node minNode = null;
int minDist = Integer.MAX_VALUE;
for (Node node : distances.keySet()) {
if (!visited.contains(node) && distances.get(node) < minDist) {
minDist = distances.get(node);
minNode = node;
}
}
if (minNode == null) break;
visited.add(minNode);
for (Node neighbor : minNode.neighbors) {
int newDist = distances.get(minNode) + getWeight(minNode, neighbor);
if (newDist < distances.get(neighbor)) {
distances.put(neighbor, newDist);
}
}
}
return distances;
}
- 动态规划实践
动态规划通过存储子问题解实现效率优化，常用于组合优化问题。
5.1 核心原理
动态规划具有最优子结构和重叠子问题特性。以0-1背包问题为例：
public int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] table = new int[n+1][capacity+1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
if (w >= weights[i-1]) {
table[i][w] = Math.max(table[i-1][w],
table[i-1][w-weights[i-1]] + values[i-1]);
} else {
table[i][w] = table[i-1][w];
}
}
}
return table[n][capacity];
}
5.2 优化技巧
空间优化通过滚动数组减少内存占用，时间优化利用数学特性减少计算量。
- 字符串处理
字符串操作是编程基础技能，涉及查找、替换、匹配等操作。
6.1 基础操作
// 字符串比较
String str1 = "Java";
String str2 = "Java";
System.out.println(str1.equals(str2)); // true
// 字符串连接
StringBuilder builder = new StringBuilder();
builder.append("Hello").append(" World");
String result = builder.toString();
6.2 高级算法
KMP算法通过预处理模式串实现高效匹配：
public int[] buildLPS(String pattern) {
int[] lps = new int[pattern.length()];
int len = 0;
for (int i = 1; i < pattern.length(); ) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len-1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
