1. 面试算法题解析与实战指南作为一名经历过上百场技术面试的Java开发者我深知算法和数据结构在面试中的重要性。本文将深入解析20道经典的Java算法面试题涵盖排序、二叉树、链表、栈队列等核心知识点。每道题我都会提供详细的解题思路、代码实现以及常见陷阱分析帮助大家从零基础到精通掌握面试必备算法技能。2. 数组与字符串处理2.1 数组拼接最小数字问题问题描述输入一个正整数数组把数组里所有数字拼接起来排成一个数打印能拼接出的所有数字中最小的一个。例如输入数组{332321}则打印出这三个数字能排成的最小数字为321323。解题思路这个问题本质上是自定义排序问题我们需要定义一种比较规则对于两个数字a和b如果ab ba则认为a应该排在b前面使用Java的Collections.sort()方法配合自定义Comparator实现代码实现import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; public class MinNumberCombination { public String printMinNumber(int[] numbers) { ArrayListString list new ArrayList(); for (int num : numbers) { list.add(String.valueOf(num)); } Collections.sort(list, new ComparatorString() { Override public int compare(String a, String b) { String order1 a b; String order2 b a; return order1.compareTo(order2); } }); StringBuilder result new StringBuilder(); for (String str : list) { result.append(str); } return result.toString(); } }注意事项注意处理数组为空或长度为0的特殊情况大数问题当数组长度很大时直接拼接字符串比较可能会超出整数范围所以使用字符串比较更安全时间复杂度O(nlogn)主要来自排序操作2.2 最大子数组和问题问题描述计算连续子向量的最大和当向量全为正数的时候问题很好解决。但是如果向量中包含负数是否应该包含某个负数并期望旁边的正数会弥补它呢例如{6,-3,-2,7,-15,1,2,2}连续子向量的最大和为8(从第0个开始到第3个为止)。解题思路Kadane算法维护两个变量当前子数组和、最大子数组和遍历数组对于每个元素如果当前子数组和为负则重置为当前元素值否则将当前元素加入子数组和更新最大子数组和代码实现public class MaxSubarray { public int findGreatestSum(int[] array) { if (array null || array.length 0) return 0; int currentSum array[0]; int maxSum array[0]; for (int i 1; i array.length; i) { currentSum Math.max(array[i], currentSum array[i]); maxSum Math.max(maxSum, currentSum); } return maxSum; } }常见问题全负数数组算法仍然有效会返回最大的那个负数空数组处理需要特别判断返回0或抛出异常视需求而定如果需要知道子数组的起止位置可以扩展算法记录索引3. 二叉树相关问题3.1 重建二叉树问题描述输入某二叉树的前序遍历和中序遍历的结果请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。解题思路前序遍历的第一个元素是根节点在中序遍历中找到根节点左边是左子树右边是右子树递归构建左右子树代码实现public class RebuildBinaryTree { public TreeNode buildTree(int[] preorder, int[] inorder) { return helper(0, 0, inorder.length - 1, preorder, inorder); } private TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) { if (preStart preorder.length - 1 || inStart inEnd) { return null; } TreeNode root new TreeNode(preorder[preStart]); int inIndex 0; // Index of current root in inorder for (int i inStart; i inEnd; i) { if (inorder[i] root.val) { inIndex i; break; } } root.left helper(preStart 1, inStart, inIndex - 1, preorder, inorder); root.right helper(preStart inIndex - inStart 1, inIndex 1, inEnd, preorder, inorder); return root; } }注意事项假设输入数据有效无重复元素且能构成二叉树时间复杂度O(n)每个节点都会被访问一次空间复杂度O(n)递归调用栈的深度3.2 二叉搜索树的第k大节点问题描述给定一颗二叉搜索树请找出其中的第k大的结点。解题思路二叉搜索树的中序遍历是升序序列中序遍历的倒序就是降序序列可以方便地找到第k大元素使用递归或迭代方式实现中序遍历代码实现public class KthLargestInBST { private int count 0; private int result 0; public int kthLargest(TreeNode root, int k) { this.count k; reverseInorder(root); return result; } private void reverseInorder(TreeNode node) { if (node null || count 0) return; reverseInorder(node.right); if (--count 0) { result node.val; return; } reverseInorder(node.left); } }优化技巧提前终止找到第k大元素后立即停止遍历迭代实现可以避免递归栈溢出的风险对于频繁查询的场景可以为每个节点维护子树节点数量4. 链表相关问题4.1 反转链表问题描述输入一个链表反转链表后输出链表的所有元素。解题思路迭代法使用三个指针(pre, cur, next)逐步反转递归法递归到链表末端然后逐层反转迭代实现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; }性能比较迭代法O(n)时间O(1)空间递归法O(n)时间O(n)空间栈空间4.2 链表中倒数第k个节点问题描述输入一个链表输出该链表中倒数第k个结点。解题思路快慢指针法快指针先走k步然后快慢指针一起走当快指针到达末尾时慢指针就是倒数第k个节点代码实现public class KthFromEnd { public ListNode findKthToTail(ListNode head, int k) { if (head null || k 0) return null; ListNode fast head; ListNode slow head; for (int i 0; i k; i) { if (fast null) return null; // k大于链表长度 fast fast.next; } while (fast ! null) { fast fast.next; slow slow.next; } return slow; } }边界条件链表为空k为0或负数k大于链表长度5. 栈与队列问题5.1 用两个栈实现队列问题描述用两个栈来实现一个队列完成队列的Push和Pop操作。解题思路入队操作直接压入栈A出队操作如果栈B为空将栈A的所有元素弹出并压入栈B然后弹出栈B的栈顶代码实现import java.util.Stack; public class QueueWithTwoStacks { private StackInteger stack1 new Stack(); private StackInteger stack2 new Stack(); public void push(int node) { stack1.push(node); } public int pop() { if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } }复杂度分析入队O(1)出队摊还时间复杂度O(1)每个元素最多被压入和弹出各两次5.2 栈的排序问题描述按升序对栈进行排序最大元素位于栈顶要求最多只能使用一个额外的栈存放临时数据。解题思路使用辅助栈作为已排序部分从原栈弹出元素与辅助栈栈顶比较保持辅助栈从栈底到栈顶递减代码实现import java.util.Stack; public class StackSorter { public static void sortStack(StackInteger stack) { StackInteger tempStack new Stack(); while (!stack.isEmpty()) { int temp stack.pop(); while (!tempStack.isEmpty() tempStack.peek() temp) { stack.push(tempStack.pop()); } tempStack.push(temp); } // 将元素从tempStack移回stack while (!tempStack.isEmpty()) { stack.push(tempStack.pop()); } } }注意事项只能使用栈的标准操作push、pop、peek、isEmpty时间复杂度O(n²)空间复杂度O(n)额外使用一个栈6. 数学与位运算问题6.1 阶乘尾随零问题问题描述计算n的阶乘有多少个尾随零。解题思路尾随零由因子10产生102×5在阶乘中2的因子比5多所以零的个数等于5的因子个数计算从1到n中所有数字包含的5的因子总数代码实现public class TrailingZeros { public int countTrailingZeros(int n) { int count 0; while (n 0) { n / 5; count n; } return count; } }优化分析时间复杂度O(logn)因为每次n都除以5不需要计算完整的阶乘避免大数问题6.2 素因子只有3、5、7的第k个数问题描述设计一个算法找出素因子只有3、5、7的第k个数。解题思路动态规划使用三个指针分别跟踪下一个应该乘以3、5、7的数每次选择三个乘积中的最小值作为下一个数更新对应指针代码实现public class KthMagicNumber { public int getKthMagicNumber(int k) { if (k 0) return 0; int[] dp new int[k]; dp[0] 1; int p3 0, p5 0, p7 0; for (int i 1; i k; i) { int next Math.min(dp[p3] * 3, Math.min(dp[p5] * 5, dp[p7] * 7)); dp[i] next; if (next dp[p3] * 3) p3; if (next dp[p5] * 5) p5; if (next dp[p7] * 7) p7; } return dp[k - 1]; } }复杂度分析时间复杂度O(n)空间复杂度O(n)7. 高级数据结构问题7.1 检查二叉树是否平衡问题描述实现一个函数检查二叉树是否平衡平衡的定义如下对于树中的任意一个结点其两颗子树的高度差不超过1。解题思路递归计算每个节点的左右子树高度检查高度差是否超过1优化在计算高度的同时检查平衡性避免重复计算代码实现public class BalancedBinaryTree { public boolean isBalanced(TreeNode root) { return checkHeight(root) ! -1; } private int checkHeight(TreeNode node) { if (node null) return 0; int leftHeight checkHeight(node.left); if (leftHeight -1) return -1; int rightHeight checkHeight(node.right); if (rightHeight -1) return -1; if (Math.abs(leftHeight - rightHeight) 1) { return -1; } return Math.max(leftHeight, rightHeight) 1; } }优化点时间复杂度O(n)每个节点只访问一次空间复杂度O(h)递归栈深度为树高7.2 二叉查找树验证问题描述实现一个函数检查一棵二叉树是否为二叉查找树。解题思路二叉查找树定义左子树所有节点小于根节点右子树所有节点大于根节点中序遍历应为升序序列递归检查每个节点是否在合法范围内代码实现public class BSTValidator { public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long min, long max) { if (node null) return true; if (node.val min || node.val max) { return false; } return validate(node.left, min, node.val) validate(node.right, node.val, max); } }注意事项使用Long类型避免整数边界值问题也可以使用中序遍历验证序列是否升序8. 面试技巧与总结8.1 算法面试准备策略分类练习将算法题按数据结构分类数组、字符串、链表、树等每类集中练习模板记忆掌握常见算法模板DFS、BFS、二分查找、动态规划等白板编程练习在白板或纸上写代码注意格式和边界条件复杂度分析对每个解法都能准确分析时间和空间复杂度测试用例设计各种边界测试用例验证代码正确性8.2 面试中的常见错误不沟通思路直接写代码而不解释思考过程忽略边界条件没有考虑空输入、极端值等情况过早优化一开始就追求最优解而忽略基本解法不测试代码写完代码后不通过示例验证时间管理不当在简单问题上花费太多时间8.3 推荐学习资源书籍《剑指Offer》《算法导论》《编程珠玑》在线平台LeetCode牛客网HackerRank视频课程算法与数据结构基础课程系统设计面试指南在实际面试中除了写出正确的代码外清晰的沟通、良好的代码风格和全面的测试同样重要。建议在平时练习中就养成这些好习惯这样在面试时才能自然展现。