Java程序员面试必刷算法题 LeetCode从入门到实战 附高频真题与刷题路线
嘿,朋友,如果你正在准备Java程序员的面试,那这篇文章就是为你量身定制的。今天咱们不玩虚的,直接把Java面试中最核心的算法题整理出来,让你从入门到实战,稳稳拿下Offer。
为什么算法题是Java面试的必考题
先说个真相:不管是大厂还是中小厂,算法题几乎是Java程序员面试的标配。为什么?因为算法题能最直接地考察一个人的逻辑思维能力和代码实现能力。一个能写出高效、整洁算法的人,通常也能写出可维护、可扩展的业务代码。
我见过太多候选人,简历写得漂漂亮亮,项目经验说得头头是道,结果一问基础算法,直接傻眼。所以,刷算法题不是可选动作,是必做动作。
算法题的刷题路线:从基础到进阶
我建议你按照这个路线来:
第一阶段:数组与字符串(1-2周)
数组和字符串是最基础的数据结构,也是面试中出现频率最高的考点。很多算法题都可以看作是数组或字符串的变体。
必刷真题:
1. 两数之和(LeetCode 1)
这是LeetCode的第一题,也是面试中最常出现的入门题。题目很简单:给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
import java.util.HashMap;
import java.util.Map;
public class TwoSum {
public static int[] twoSum(int[] nums, int target) {
// 用HashMap来存储已经遍历过的数字及其索引
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
// 如果map中存在互补的数,直接返回结果
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
// 将当前数字存入map
map.put(nums[i], i);
}
// 如果没有找到,返回空数组
return new int[]{};
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("[" + result[0] + ", " + result[1] + "]");
// 输出: [0, 1]
}
}
这道题的关键是用HashMap来优化查找效率,将时间复杂度从O(n²)降到O(n)。面试的时候,如果你能说出这个思路,面试官会对你刮目相看。
2. 最长无重复子串(LeetCode 3)
这道题考察的是滑动窗口技术,是数组类题目中非常重要的一个技巧。
import java.util.HashMap;
import java.util.Map;
public class LongestSubstringWithoutRepeating {
public static int lengthOfLongestSubstring(String s) {
// 用HashMap记录字符最后出现的位置
Map<Character, Integer> charIndex = new HashMap<>();
int maxLength = 0;
int left = 0; // 滑动窗口的左边界
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符已经在窗口中出现过,移动左边界
if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
left = charIndex.get(c) + 1;
}
// 更新字符最后出现的位置
charIndex.put(c, right);
// 更新最大长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
public static void main(String[] args) {
String s = "abcabcbb";
System.out.println(lengthOfLongestSubstring(s));
// 输出: 3
}
}
滑动窗口的核心思想是:用两个指针(left和right)来维护一个窗口,通过移动指针来找到满足条件的最优解。这道题在面试中经常被问到,一定要熟练掌握。
第二阶段:链表(1-2周)
链表是Java面试中的另一个高频考点,特别是反转链表、合并链表、检测环等题目。
必刷真题:
3. 反转链表(LeetCode 206)
这是一道非常经典的链表题目,几乎每个Java程序员都应该能手写出来。
public class ReverseLinkedList {
// 链表节点定义
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
// 迭代解法
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next; // 保存下一个节点
current.next = prev; // 反转指针
prev = current; // 移动prev
current = nextTemp; // 移动current
}
return prev;
}
// 递归解法
public static ListNode reverseListRecursive(ListNode head) {
// 基准情况:空链表或只有一个节点
if (head == null || head.next == null) {
return head;
}
// 递归反转后面的链表
ListNode newHead = reverseListRecursive(head.next);
// 反转当前节点的指针
head.next.next = head;
head.next = null;
return newHead;
}
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);
ListNode reversed = reverseList(head);
// 输出反转后的链表
while (reversed != null) {
System.out.print(reversed.val + " -> ");
reversed = reversed.next;
}
// 输出: 5 -> 4 -> 3 -> 2 -> 1 ->
}
}
这道题的迭代解法是最常用的,你一定要能在白板上或者面试时流畅地写出来。递归解法虽然简洁,但面试时迭代解法更受青睐,因为面试官更想看你的逻辑思维过程。
4. 合并两个有序链表(LeetCode 21)
public class MergeTwoSortedLists {
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 创建虚拟头节点
ListNode dummy = new ListNode(0);
ListNode current = dummy;
// 比较两个链表的节点,依次连接较小的节点
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
// 将剩余的节点连接到结果链表
if (list1 != null) {
current.next = list1;
} else {
current.next = list2;
}
return dummy.next;
}
public static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " -> ");
head = head.next;
}
System.out.println("null");
}
public static void main(String[] args) {
// 链表1: 1 -> 2 -> 4
ListNode list1 = new ListNode(1);
list1.next = new ListNode(2);
list1.next.next = new ListNode(4);
// 链表2: 1 -> 3 -> 4
ListNode list2 = new ListNode(1);
list2.next = new ListNode(3);
list2.next.next = new ListNode(4);
ListNode merged = mergeTwoLists(list1, list2);
printList(merged);
// 输出: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null
}
}
这道题的关键是使用虚拟头节点来简化代码,避免处理头节点为空的情况。面试时,如果你能主动提到这个技巧,会让面试官觉得你很有经验。
第三阶段:栈与队列(1周)
栈和队列是基础数据结构,很多算法题都用到它们,比如括号匹配、滑动窗口最大值等。
必刷真题:
5. 有效的括号(LeetCode 20)
import java.util.Stack;
public class ValidParentheses {
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
// 如果是左括号,入栈
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
}
// 如果是右括号,检查栈顶是否匹配
else if (c == ')') {
if (stack.isEmpty() || stack.pop() != '(') return false;
} else if (c == '}') {
if (stack.isEmpty() || stack.pop() != '{') return false;
} else if (c == ']') {
if (stack.isEmpty() || stack.pop() != '[') return false;
}
}
// 最后检查栈是否为空
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValid("()")); // true
System.out.println(isValid("()[]{}")); // true
System.out.println(isValid("(]")); // false
System.out.println(isValid("([)]")); // false
System.out.println(isValid("{[]}")); // true
}
}
这道题用栈来解决非常自然:遇到左括号就入栈,遇到右括号就检查栈顶是否匹配。最后如果栈为空,说明所有括号都正确匹配了。
第四阶段:二叉树(2周)
二叉树是面试中的重点,特别是递归遍历、层序遍历、最近公共祖先等题目。
必刷真题:
6. 二叉树的中序遍历(LeetCode 94)
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class InorderTraversal {
// 二叉树节点定义
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
// 递归解法
public static List<Integer> inorderTraversalRecursive(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderRecursive(root, result);
return result;
}
private static void inorderRecursive(TreeNode node, List<Integer> result) {
if (node == null) return;
inorderRecursive(node.left, result); // 遍历左子树
result.add(node.val); // 访问根节点
inorderRecursive(node.right, result); // 遍历右子树
}
// 迭代解法(使用栈)
public static List<Integer> inorderTraversalIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
// 先遍历到最左边的节点
while (current != null) {
stack.push(current);
current = current.left;
}
// 弹出栈顶节点并访问
current = stack.pop();
result.add(current.val);
// 转向右子树
current = current.right;
}
return result;
}
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);
System.out.println(inorderTraversalRecursive(root)); // [1, 3, 2]
System.out.println(inorderTraversalIterative(root)); // [1, 3, 2]
}
}
二叉树的遍历是基础中的基础,递归解法简单直观,迭代解法展示了你对栈的理解。面试时,如果面试官要求你手写迭代解法,一定要熟练。
7. 二叉树的最大深度(LeetCode 104)
public class MaxDepthOfBinaryTree {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public static int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 递归计算左子树和右子树的最大深度
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
// 返回较大的那个深度 + 1(当前节点)
return Math.max(leftDepth, rightDepth) + 1;
}
public static void main(String[] args) {
// 构建二叉树:
// 3
// / \
// 9 20
// / \
// 15 7
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
System.out.println(maxDepth(root)); // 输出: 3
}
}
这道题是二叉树递归的经典应用,逻辑非常清晰。记住:二叉树的问题,递归往往是最简洁的解法。
第五阶段:动态规划(2-3周)
动态规划是算法题中最难的部分,也是面试官最喜欢考察的。掌握动态规划的关键是找到状态转移方程。
必刷真题:
8. 爬楼梯(LeetCode 70)
public class ClimbingStairs {
// 动态规划解法
public static int climbStairs(int n) {
if (n <= 2) {
return n;
}
// dp[i]表示到达第i阶的方法数
// 状态转移方程: dp[i] = dp[i-1] + dp[i-2]
int prev1 = 1; // dp[i-2]
int prev2 = 2; // dp[i-1]
for (int i = 3; i <= n; i++) {
int current = prev1 + prev2;
prev1 = prev2;
prev2 = current;
}
return prev2;
}
// 备忘录递归解法(防止重复计算)
public static int climbStairsMemo(int n) {
int[] memo = new int[n + 1];
return climbStairsMemoHelper(n, memo);
}
private static int climbStairsMemoHelper(int n, int[] memo) {
if (n <= 2) {
return n;
}
if (memo[n] != 0) {
return memo[n];
}
memo[n] = climbStairsMemoHelper(n - 1, memo) + climbStairsMemoHelper(n - 2, memo);
return memo[n];
}
public static void main(String[] args) {
System.out.println(climbStairs(2)); // 2
System.out.println(climbStairs(3)); // 3
System.out.println(climbStairs(4)); // 5
System.out.println(climbStairs(5)); // 8
}
}
爬楼梯是最简单的动态规划入门题。关键在于理解:到达第n阶的方法数等于到达第n-1阶和第n-2阶的方法数之和。这就是状态转移方程。动态规划的精髓就在这里——把大问题分解成小问题,然后复用之前的计算结果。
9. 零钱兑换(LeetCode 322)
import java.util.Arrays;
public class CoinChange {
public static int coinChange(int[] coins, int amount) {
// dp[i]表示凑成金额i所需的最少硬币数
int[] dp = new int[amount + 1];
// 初始化dp数组,设置为一个特殊值(表示不可达)
Arrays.fill(dp, amount + 1);
dp[0] = 0; // 凑成金额0需要0个硬币
// 遍历每种硬币
for (int coin : coins) {
// 更新所有可能的金额
for (int i = coin; i <= amount; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
// 如果dp[amount]还是初始值,说明无法凑成该金额
return dp[amount] > amount ? -1 : dp[amount];
}
public static void main(String[] args) {
int[] coins1 = {1, 2, 5};
int amount1 = 11;
System.out.println(coinChange(coins1, amount1)); // 输出: 3 (5+5+1)
int[] coins2 = {2};
int amount2 = 3;
System.out.println(coinChange(coins2, amount2)); // 输出: -1
}
}
这道题是动态规划的典型应用。关键是定义好状态和状态转移方程:dp[i] = min(dp[i], dp[i - coin] + 1)。动态规划的难点往往在于如何定义状态,一旦定义好了,代码就很简单了。
第六阶段:排序与二分查找(1-2周)
排序和二分查找是算法的基础,很多高级算法都建立在这些基础上。
必刷真题:
10. 二分查找(LeetCode 704)
public class BinarySearch {
public static int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 未找到
}
public static void main(String[] args) {
int[] nums = {-1, 0, 3, 5, 9, 12};
int target = 9;
System.out.println(binarySearch(nums, target)); // 输出: 4
target = 2;
System.out.println(binarySearch(nums, target)); // 输出: -1
}
}
二分查找看起来简单,但细节很多。比如计算mid的时候要用left + (right - left) / 2而不是(left + right) / 2,这是为了防止溢出。面试时,面试官可能会让你手写二分查找,一定要能流畅地写出来。
第七阶段:高频综合题(2-3周)
这个阶段,我们要做一些综合性的题目,这些题目在面试中出现频率很高。
必刷真题:
11. 三数之和(LeetCode 15)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // 先排序
for (int i = 0; i < nums.length - 2; i++) {
// 跳过重复元素
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 跳过重复元素
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {-1, 0, 1, 2, -1, -4};
List<List<Integer>> result = threeSum(nums);
System.out.println(result);
// 输出: [[-1, -1, 2], [-1, 0, 1]]
}
}
这道题是双指针技术的经典应用。关键是:先排序,然后固定一个数,用双指针在剩下的数组中找另外两个数。还要注意跳过重复元素,避免结果中出现重复的组合。
12. 旋转图像(LeetCode 46)
public class RotateImage {
public static void rotate(int[][] matrix) {
int n = matrix.length;
// 第一步:沿对角线翻转
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 第二步:翻转每一行
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = temp;
}
}
}
public static void printMatrix(int[][] matrix) {
for (int[] row : matrix) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("旋转前:");
printMatrix(matrix);
rotate(matrix);
System.out.println("旋转后:");
printMatrix(matrix);
}
}
这道题的巧妙之处在于:旋转图像可以分解为两步——先沿对角线翻转,再水平翻转。如果你能想到这个分解,问题就变得很简单了。面试时,这种将复杂问题分解为简单步骤的思维非常重要。
刷题的建议和技巧
1. 不要死记硬背,要理解思路
很多学员刷题时,喜欢把代码背下来。这是大错特错!面试的时候,如果题目稍有变化,你就不会了。正确的做法是:理解思路,自己写出代码。
比如两数之和这道题,你要理解为什么用HashMap、为什么用互补的思想。这样即使题目改成”两数之和 II”或”三数之和”,你也能灵活运用。
2. 每次刷题都要复盘
刷题之后,一定要复盘:这道题考察的是什么知识点?有没有更优的解法?如果面试官追问,我该怎么回答?
建议建立一个刷题笔记,把每道题的思路、难点、易错点都记录下来。这样在面试前,你只需要看笔记就能快速复习。
3. 模拟面试环境
刷题的时候,要给自己设定时间限制。比如,一道中等难度的题,给自己30分钟。如果30分钟之内做不出来,就看答案,理解思路,然后隔几天再做一遍。
模拟面试环境非常重要,因为面试的时候是有时间压力的。如果你平时刷题都是悠闲地想,到了面试时肯定写不出来。
4. 重点刷高频题
不是所有LeetCode题都要刷。根据我的经验,以下这些题是Java面试中出现频率最高的:
- 两数之和
- 反转链表
- 有效的括号
- 合并两个有序链表
- 二叉树的最大深度
- 爬楼梯
- 二分查找
- 三数之和
- 最大子数组和
- 无重复字符的最长子串
这些题你可以重点刷,做到滚瓜烂熟。
面试中的常见问题
问题1:”你为什么选择用HashMap而不是数组?”
在两数之和这道题中,面试官可能会追问这个问题。你可以这样回答:
“如果用数组,我们需要遍历整个数组来查找互补的数,时间复杂度是O(n²)。而用HashMap,我们可以把查找的时间复杂度降到O(1),总体时间复杂度就是O(n)。虽然空间复杂度增加了O(n),但这是一个很值得的权衡,因为时间复杂度的降低更显著。”
问题2:”这道题的时间复杂度和空间复杂度分别是多少?”
面试时,面试官经常会让你说出时间复杂度和空间复杂度。这是你必须掌握的技能。
比如反转链表这道题:
- 时间复杂度:O(n),因为我们需要遍历整个链表
- 空间复杂度:O(1),因为只用了几个指针,没有额外的空间
问题3:”你能优化这道题吗?”
有些题目有多种解法,面试官可能会让你给出更优的解法。比如爬楼梯这道题:
- 朴素递归:时间复杂度O(2^n),因为有很多重复计算
- 备忘录递归:时间复杂度O(n),空间复杂度O(n)
- 动态规划(迭代):时间复杂度O(n),空间复杂度O(1)
如果你能主动说出这些优化,面试官会对你印象更深刻。
最后的话
刷算法题是一个循序渐进的过程,不要急于求成。我建议你把刷题计划分成三个阶段:
- 基础阶段(1个月):把数组、字符串、链表、栈、队列、二叉树这些基础数据结构相关的题目刷完
- 进阶阶段(1个月):重点攻克动态规划、贪心算法、回溯算法
- 冲刺阶段(1个月):刷高频真题,模拟面试,查漏补缺
记住,算法题不是一蹴而就的,需要每天坚持练习。哪怕每天只做一道题,一个月下来也能做30道,三个月就是90道,这已经足够应对大多数Java面试了。
祝你面试顺利,拿到心仪的Offer!如果有任何问题,欢迎随时来找我交流。
