Java面试中的算法题：从易到难，逐个击破
在Java开发岗位的面试中，算法题往往是考察候选人编程能力和逻辑思维的重要环节。本文将从简单到复杂，系统地介绍几种常见的算法题型，并提供详细的Java代码实现，帮助你在面试中游刃有余。
一、基础算法题：数组与字符串
1.1 两数之和
这是LeetCode上的经典入门题，考察基本的数组操作和哈希表使用。
import java.util.HashMap;
import java.util.Map;
public class TwoSum {
public int[] twoSum(int[] nums, int target) {
Map
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);
}
throw new IllegalArgumentException("No two sum solution");
}
public static void main(String[] args) {
TwoSum solution = new TwoSum();
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = solution.twoSum(nums, target);
System.out.println("Indices: " + result[0] + ", " + result[1]);
}
}
1.2 字符串反转
考察基本的字符串操作和双指针技巧。
public class StringReverse {
public String reverseString(String s) {
char[] chars = s.toCharArray();
int left = 0, right = chars.length - 1;
while (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
return new String(chars);
}
public static void main(String[] args) {
StringReverse solution = new StringReverse();
String input = "hello world";
System.out.println("Reversed: " + solution.reverseString(input));
}
}
二、中级算法题：链表与树
2.1 反转链表
链表操作是面试中的高频考点，反转链表是基础中的基础。
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 nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
// 递归法
public ListNode reverseListRecursive(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseListRecursive(head.next);
head.next.next = head;
head.next = null;
return p;
}
public static void main(String[] args) {
// 构建链表 1->2->3->4->5
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
ReverseLinkedList solution = new ReverseLinkedList();
ListNode reversed = solution.reverseList(head);
// 输出反转后的链表
while (reversed != null) {
System.out.print(reversed.val + " ");
reversed = reversed.next;
}
}
}
2.2 二叉树的中序遍历
树的遍历是必须掌握的基础算法。
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BinaryTreeInorder {
// 递归解法
public List
List
helper(root, res);
return res;
}
private void helper(TreeNode root, List
if (root != null) {
if (root.left != null) {
helper(root.left, res);
}
res.add(root.val);
if (root.right != null) {
helper(root.right, res);
}
}
}
// 迭代解法（使用栈）
public List
List
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;
}
public static void main(String[] args) {
// 构建二叉树
// 1
// \
// 2
// /
// 3
TreeNode root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);
BinaryTreeInorder solution = new BinaryTreeInorder();
List
System.out.println("Inorder traversal: " + result);
}
}
三、高级算法题：动态规划与图论
3.1 最长递增子序列（LIS）
动态规划是算法面试中的难点，也是区分候选人水平的重要标准。
public class LongestIncreasingSubsequence {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < dp.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = Math.max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
// 优化解法：二分查找 O(nlogn)
public int lengthOfLISBinary(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int i = 0, j = size;
while (i != j) {
int m = (i + j) / 2;
if (tails[m] < x) {
i = m + 1;
} else {
j = m;
}
}
tails[i] = x;
if (i == size) ++size;
}
return size;
}
public static void main(String[] args) {
LongestIncreasingSubsequence solution = new LongestIncreasingSubsequence();
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("Length of LIS (DP): " + solution.lengthOfLIS(nums));
System.out.println("Length of LIS (Binary): " + solution.lengthOfLISBinary(nums));
}
}
3.2 课程表（拓扑排序）
图论问题在面试中也经常出现，拓扑排序是解决依赖关系问题的有效方法。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class CourseSchedule {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 构建邻接表和入度数组
List
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
int[] indegree = new int[numCourses];
for (int[] edge : prerequisites) {
adj.get(edge[1]).add(edge[0]);
indegree[edge[0]]++;
}
// 拓扑排序
Queue
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int visited = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
visited++;
for (int neighbor : adj.get(node)) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
return visited == numCourses;
}
public static void main(String[] args) {
CourseSchedule solution = new CourseSchedule();
int numCourses = 4;
int[][] prerequisites = {{1,0}, {2,0}, {3,1}, {3,2}};
System.out.println("Can finish courses: " + solution.canFinish(numCourses, prerequisites));
}
}
四、算法优化技巧与面试策略
4.1 时间复杂度分析
在面试中，能够分析算法的时间复杂度和空间复杂度至关重要。常见复杂度：
O(1): 常数时间，如哈希表查找
O(logn): 对数时间，如二分查找
O(n): 线性时间，如遍历数组
O(nlogn): 如快速排序、归并排序
O(n²): 如冒泡排序
O(2ⁿ): 指数时间，如穷举搜索
4.2 面试策略建议
先理解问题：确保完全理解题目要求，可以举例说明
提出暴力解法：先给出简单解法，再考虑优化
分析复杂度：说明当前解法的时间空间复杂度
优化思路：考虑是否有更优的数据结构或算法
编写代码：注意代码规范、边界条件和异常处理
测试用例：用多个测试用例验证代码正确性
结语
掌握算法不仅是为了通过面试，更是提升编程能力的必经之路。建议平时多练习LeetCode、牛客网等平台的题目，分类刷题，总结规律。记住，算法能力的提升没有捷径，只有不断练习和思考。希望本文能帮助你在Java算法面试中取得好成绩！
