Java秋招面试之第13章 高频算法题解
第13章 高频算法题解
面试重要程度:⭐⭐⭐⭐⭐
常见提问方式:手写代码、分析时间复杂度、优化算法
预计阅读时间:50分钟
开场白
兄弟,算法题绝对是Java面试的必考内容!不管是大厂还是小公司,基本都会让你现场手写代码。我见过太多技术不错的同学,就是在算法这关败下阵来。
今天我们就把面试中最高频的算法题型彻底搞定,不仅要会做,还要能优化,更要能清晰地讲解思路。
🔢 13.1 数组与字符串
两数之和系列
面试必考:
面试官:"给定一个整数数组和目标值,找出数组中和为目标值的两个数的索引。"
解题思路与代码:
// 1. 两数之和 - LeetCode 1 public class TwoSum { // 方法1:暴力解法 - O(n²) public int[] twoSumBruteForce(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[0]; } // 方法2:哈希表 - O(n) ⭐推荐 public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; // 如果complement存在于map中,说明找到了答案 if (map.containsKey(complement)) { return new int[]{map.get(complement), i}; } // 将当前数字和索引存入map map.put(nums[i], i); } return new int[0]; } // 面试技巧:主动提出优化方案 public void explainOptimization() { System.out.println("优化思路:"); System.out.println("1. 暴力解法需要两层循环,时间复杂度O(n²)"); System.out.println("2. 使用哈希表可以将查找时间降到O(1)"); System.out.println("3. 一次遍历即可完成,时间复杂度O(n),空间复杂度O(n)"); System.out.println("4. 这是典型的用空间换时间的优化策略"); } } // 2. 三数之和 - LeetCode 15 public class ThreeSum { public 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; int target = -nums[i]; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { 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 < target) { left++; } else { right--; } } } return result; } // 面试要点:解释去重逻辑 public void explainDeduplication() { System.out.println("去重策略:"); System.out.println("1. 对数组排序,相同元素会相邻"); System.out.println("2. 在外层循环中跳过重复的nums[i]"); System.out.println("3. 在找到答案后,跳过重复的left和right指针值"); System.out.println("4. 这样可以避免产生重复的三元组"); } } // 3. 最长无重复字符子串 - LeetCode 3 public class LongestSubstring { // 滑动窗口解法 - O(n) public int lengthOfLongestSubstring(String s) { if (s == null || s.length() == 0) { return 0; } Map<Character, Integer> charIndexMap = new HashMap<>(); int maxLength = 0; int left = 0; // 滑动窗口左边界 for (int right = 0; right < s.length(); right++) { char currentChar = s.charAt(right); // 如果字符已存在且在当前窗口内 if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= left) { // 移动左边界到重复字符的下一位 left = charIndexMap.get(currentChar) + 1; } // 更新字符的最新位置 charIndexMap.put(currentChar, right); // 更新最大长度 maxLength = Math.max(maxLength, right - left + 1); } return maxLength; } // 面试技巧:画图解释滑动窗口 public void explainSlidingWindow() { System.out.println("滑动窗口解法:"); System.out.println("例如:s = \"abcabcbb\""); System.out.println("窗口变化过程:"); System.out.println("[a]bcabcbb -> left=0, right=0, length=1"); System.out.println("[ab]cabcbb -> left=0, right=1, length=2"); System.out.println("[abc]abcbb -> left=0, right=2, length=3"); System.out.println("abc[a]bcbb -> left=1, right=3, length=3 (遇到重复a)"); System.out.println("abca[b]cbb -> left=2, right=4, length=3 (遇到重复b)"); System.out.println("核心思想:维护一个无重复字符的滑动窗口"); } }
数组操作经典题
高频考题:
// 4. 合并两个有序数组 - LeetCode 88 public class MergeSortedArray { // 从后往前合并 - O(m+n) public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1; // nums1的最后一个有效元素 int j = n - 1; // nums2的最后一个元素 int k = m + n - 1; // 合并后数组的最后一个位置 // 从后往前比较并放置元素 while (i >= 0 && j >= 0) { if (nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } // 如果nums2还有剩余元素 while (j >= 0) { nums1[k--] = nums2[j--]; } // nums1的剩余元素已经在正确位置,无需处理 } // 面试要点:解释为什么从后往前 public void explainApproach() { System.out.println("从后往前合并的优势:"); System.out.println("1. 避免覆盖nums1中未处理的元素"); System.out.println("2. 不需要额外的存储空间"); System.out.println("3. 时间复杂度O(m+n),空间复杂度O(1)"); } } // 5. 旋转数组 - LeetCode 189 public class RotateArray { // 方法1:使用额外数组 - O(n)空间 public void rotateWithExtraSpace(int[] nums, int k) { int n = nums.length; k = k % n; // 处理k大于数组长度的情况 int[] temp = new int[n]; // 将元素放到新位置 for (int i = 0; i < n; i++) { temp[(i + k) % n] = nums[i]; } // 复制回原数组 System.arraycopy(temp, 0, nums, 0, n); } // 方法2:三次反转 - O(1)空间 ⭐推荐 public void rotate(int[] nums, int k) { int n = nums.length; k = k % n; // 反转整个数组 reverse(nums, 0, n - 1); // 反转前k个元素 reverse(nums, 0, k - 1); // 反转后n-k个元素 reverse(nums, k, n - 1); } private void reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } } // 面试技巧:举例说明三次反转 public void explainThreeReverse() { System.out.println("三次反转法示例:"); System.out.println("原数组:[1,2,3,4,5,6,7], k=3"); System.out.println("第一次反转整个数组:[7,6,5,4,3,2,1]"); System.out.println("第二次反转前k个:[5,6,7,4,3,2,1]"); System.out.println("第三次反转后n-k个:[5,6,7,1,2,3,4]"); System.out.println("核心思想:通过反转操作实现元素位置调整"); } } // 6. 买卖股票的最佳时机 - LeetCode 121 public class BestTimeToBuyStock { // 一次遍历解法 - O(n) public int maxProfit(int[] prices) { if (prices == null || prices.length < 2) { return 0; } int minPrice = prices[0]; // 记录到目前为止的最低价格 int maxProfit = 0; // 记录最大利润 for (int i = 1; i < prices.length; i++) { // 更新最低价格 minPrice = Math.min(minPrice, prices[i]); // 计算当前价格卖出的利润,并更新最大利润 maxProfit = Math.max(maxProfit, prices[i] - minPrice); } return maxProfit; } // 面试要点:解释贪心思想 public void explainGreedyApproach() { System.out.println("贪心策略:"); System.out.println("1. 我们想要在最低点买入,最高点卖出"); System.out.println("2. 遍历过程中记录到目前为止的最低价格"); System.out.println("3. 对于每个价格,计算如果今天卖出能获得的最大利润"); System.out.println("4. 这样保证了我们总是在最优的买入点进行交易"); } }
🔗 13.2 链表操作
链表基础操作
面试高频:
// 链表节点定义 class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } // 7. 反转链表 - LeetCode 206 public class ReverseLinkedList { // 迭代解法 - O(n)时间,O(1)空间 public 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; // prev成为新的头节点 } // 递归解法 - O(n)时间,O(n)空间 public 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 void explainProcess() { System.out.println("反转链表过程:"); System.out.println("原链表:1 -> 2 -> 3 -> null"); System.out.println("步骤1:null <- 1 2 -> 3 -> null"); System.out.println("步骤2:null <- 1 <- 2 3 -> null"); System.out.println("步骤3:null <- 1 <- 2 <- 3"); System.out.println("关键:用三个指针prev、current、next维护状态"); } } // 8. 合并两个有序链表 - LeetCode 21 public class MergeTwoSortedLists { // 迭代解法 public 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; } // 连接剩余的节点 current.next = (list1 != null) ? list1 : list2; return dummy.next; } // 递归解法 public ListNode mergeTwoListsRecursive(ListNode list1, ListNode list2) { // 递归终止条件 if (list1 == null) return list2; if (list2 == null) return list1; // 选择较小的节点作为当前节点 if (list1.val <= list2.val) { list1.next = mergeTwoListsRecursive(list1.next, list2); return list1; } else { list2.next = mergeTwoListsRecursive(list1, list2.next); return list2; } } // 面试要点:虚拟头节点的作用 public void explainDummyNode() { System.out.println("虚拟头节点的优势:"); System.out.println("1. 避免特殊处理第一个节点"); System.out.println("2. 简化代码逻辑,减少边界判断"); System.out.println("3. 统一处理所有节点的插入操作"); System.out.println("4. 最后返回dummy.next即为真正的头节点"); } } // 9. 环形链表检测 - LeetCode 141 public class LinkedListCycle { // 快慢指针法(Floyd判圈算法) public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; // 慢指针,每次移动一步 ListNode fast = head.next; // 快指针,每次移动两步 while (slow != fast) { // 如果快指针到达末尾,说明无环 if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; // 快慢指针相遇,说明有环 } // 进阶:找到环的起始节点 - LeetCode 142 public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } // 第一步:判断是否有环 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // 第二步:找到环的起始节点 ListNode start = head; while (start != slow) { start = start.next; slow = slow.next; } return start; } } return null; } // 面试要点:解释数学原理 public void explainMathPrinciple() { System.out.println("Floyd判圈算法原理:"); System.out.println("设链表头到环起点距离为a,环长度为b"); System.out.println("快慢指针相遇时:"); System.out.println("- 慢指针走了:a + x(x为环内距离)"); System.out.println("- 快指针走了:a + x + nb(多走了n圈)"); System.out.println("- 由于快指针速度是慢指针2倍:2(a+x) = a+x+nb"); System.out.println("- 解得:a = nb - x"); System.out.println("- 所以从头节点和相遇点同时出发,会在环起点相遇"); } }
🌳 13.3 二叉树遍历
树的遍历算法
面试必考:
// 二叉树节点定义 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } // 10. 二叉树的前序遍历 - LeetCode 144 public class BinaryTreeTraversal { // 前序遍历 - 递归版本 public List<Integer> preorderTraversalRecursive(TreeNode root) { List<Integer> result = new ArrayList<>(); preorderHelper(root, result); return result; } private void preorderHelper(TreeNode node, List<Integer> result) { if (node == null) return; result.add(node.val); // 访问根节点 preorderHelper(node.left, result); // 遍历左子树 preorderHelper(node.right, result); // 遍历右子树 } // 前序遍历 - 迭代版本(使用栈) public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); // 注意:先压入右子树,再压入左子树 // 这样出栈时就是先左后右 if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return result; } // 中序遍历 - 迭代版本 public List<Integer> inorderTraversal(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 List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Stack<TreeNode> stack = new Stack<>(); TreeNode lastVisited = null; TreeNode current = root; while (current != null || !stack.isEmpty()) { if (current != null) { stack.push(current); current = current.left; } else { TreeNode peekNode = stack.peek(); // 如果右子树存在且未被访问过 if (peekNode.right != null && lastVisited != peekNode.right) { current = peekNode.right; } else { // 访问节点 result.add(peekNode.val); lastVisited = stack.pop(); } } } return result; } // 层序遍历 - LeetCode 102 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(); // 处理当前层的所有节点 for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); currentLevel.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(currentLevel); } return result; } // 面试技巧:总结遍历方法 public void summarizeTraversals() { System.out.println("二叉树遍历总结:"); System.out.println("前序遍历:根 -> 左 -> 右(递归/栈)"); System.out.println("中序遍历:左 -> 根 -> 右(递归/栈)"); System.out.println("后序遍历:左 -> 右 -> 根(递归/栈+标记)"); System.out.println("层序遍历:逐层访问(队列)"); System.out.println("递归版本简洁,迭代版本节省栈空间"); } }
🔍 13.4 动态规划入门
经典DP问题
面试重点:
// 11. 爬楼梯 - LeetCode 70 public class ClimbingStairs { // 方法1:递归(会超时) public int climbStairsRecursive(int n) { if (n <= 2) return n; return climbStairsRecursive(n - 1) + climbStairsRecursive(n - 2); } // 方法2:记忆化递归 public int climbStairsMemo(int n) { int[] memo = new int[n + 1]; return climbStairsHelper(n, memo); } private int climbStairsHelper(int n, int[] memo) { if (n <= 2) return n; if (memo[n] != 0) return memo[n]; memo[n] = climbStairsHelper(n - 1, memo) + climbStairsHelper(n - 2, memo); return memo[n]; } // 方法3:动态规划 - O(n)时间,O(n)空间 public int climbStairsDP(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]; } // 方法4:空间优化 - O(n)时间,O(1)空间 ⭐推荐 public int climbStairs(int n) { if (n <= 2) return n; int prev2 = 1; // dp[i-2] int prev1 = 2; // dp[i-1] for (int i = 3; i <= n; i++) { int current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; } // 面试要点:解释DP思路 public void explainDPThinking() { System.out.println("动态规划解题步骤:"); System.out.println("1. 定义状态:dp[i]表示到达第i阶的方法数"); System.out.println("2. 状态转移:dp[i] = dp[i-1] + dp[i-2]"); System.out.println("3. 初始状态:dp[1] = 1, dp[2] = 2"); System.out.println("4. 空间优化:只需要前两个状态"); System.out.println("本质:斐波那契数列问题"); } } // 12. 最大子数组和 - LeetCode 53(Kadane算法) public class MaximumSubarray { // 动态规划解法 public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int maxSoFar = nums[0]; // 全局最大值 int maxEndingHere = nums[0]; // 以当前位置结尾的最大子数组和 for (int i = 1; i < nums.length; i++) { // 状态转移:要么扩展前面的子数组,要么重新开始 maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]); // 更新全局最大值 maxSoFar = Math.max(maxSoFar, maxEndingHere); } return maxSoFar; } // 进阶:返回最大子数组的起始和结束位置 public int[] maxSubArrayWithIndices(int[] nums) { int maxSum = nums[0]; int currentSum = nums[0]; int start = 0, end = 0, tempStart = 0; for (int i = 1; i < nums.length; i++) { if (currentSum < 0) { currentSum = nums[i]; tempStart = i; } else { currentSum += nums[i]; } if (currentSum > maxSum) { maxSum = currentSum; start = tempStart; end = i; } } return new int[]{maxSum, start, end}; } // 面试技巧:解释Kadane算法思想 public void explainKadaneAlgorithm() { System.out.println("Kadane算法核心思想:"); System.out.println("对于每个位置,考虑两种选择:"); System.out.println("1. 将当前元素加入前面的子数组"); System.out.println("2. 从当前元素重新开始一个新的子数组"); System.out.println("选择能产生更大和的方案"); System.out.println("时间复杂度O(n),空间复杂度O(1)"); } } // 13. 打家劫舍 - LeetCode 198 public class HouseRobber { // 动态规划解法 public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < nums.length; i++) { // 状态转移:偷当前房子 vs 不偷当前房子 dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[nums.length - 1]; } // 空间优化版本 public int robOptimized(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int prev2 = 0; // dp[i-2] int prev1 = 0; // dp[i-1] for (int num : nums) { int current = Math.max(prev1, prev2 + num); prev2 = prev1; prev1 = current; } return prev1; } // 面试要点:状态定义 public void explainStateDefinition() { System.out.println("状态定义:"); System.out.println("dp[i] = 从前i+1个房子中能偷到的最大金额"); System.out.println("状态转移方程:"); System.out.println("dp[i] = max(dp[i-1], dp[i-2] + nums[i])"); System.out.println("含义:不偷第i个房子 vs 偷第i个房子"); } }
💡 面试解题框架
通用解题思路:
public class InterviewFramework { // 面试解题四步法 public void solveProblemFramework() { System.out.println("=== 面试解题框架 ==="); // 第一步:理解题意 System.out.println("1. 理解题意(5分钟)"); System.out.println(" - 仔细阅读题目,确认输入输出"); System.out.println(" - 询问边界条件和特殊情况"); System.out.println(" - 举例验证理解是否正确"); // 第二步:分析思路 System.out.println("2. 分析思路(10分钟)"); System.out.println(" - 从暴力解法开始思考"); System.out.println(" - 分析时间空间复杂度"); System.out.println(" - 考虑优化方案"); // 第三步:编码实现 System.out.println("3. 编码实现(15分钟)"); System.out.println(" - 先写主要逻辑框架"); System.out.println(" - 处理边界条件"); System.out.println(" - 添加注释说明关键步骤"); // 第四步:测试验证 System.out.println("4. 测试验证(5分钟)"); System.out.println(" - 用示例数据验证"); System.out.println(" - 考虑边界情况"); System.out.println(" - 分析复杂度"); } // 常见数据结构选择 public void dataStructureSelection() { System.out.println("=== 数据结构选择指南 ==="); System.out.println("数组:随机访问,固定大小"); System.out.println("链表:动态大小,插入删除方便"); System.out.println("栈:LIFO,递归模拟,括号匹配"); System.out.println("队列:FIFO,BFS,滑动窗口"); System.out.println("哈希表:快速查找,去重,计数"); System.out.println("堆:优先级,TopK问题"); System.out.println("树:层次结构,搜索,遍历"); } // 算法模式识别 public void algorithmPatterns() { System.out.println("=== 算法模式识别 ==="); System.out.println("双指针:有序数组,链表操作"); System.out.println("滑动窗口:子数组/子串问题"); System.out.println("快慢指针:链表环检测,中点查找"); System.out.println("分治:归并排序,快速排序"); System.out.println("动态规划:最优子结构,重叠子问题"); System.out.println("贪心:局部最优,证明全局最优"); System.out.println("回溯:排列组合,N皇后"); System.out.println("BFS/DFS:图遍历,树遍历"); } }
总结
算法题是Java面试的重要组成部分,需要大量练习才能熟练掌握。面试中算法题的考察重点:
核心要点回顾:
- 基础数据结构:数组、链表、栈、队列的熟练操作
- 经典算法:排序、搜索、遍历算法的实现
- 解题思路:双指针、滑动窗口、动态规划等常见模式
- 代码质量:边界处理、异常情况、代码可读性
- 复杂度分析:时间复杂度和空间复杂度的准确分析
面试建议:
- 多练习LeetCode高频题目,形成肌肉记忆
- 掌握常见算法模式,能够快速识别题型
- 注重代码质量,写出清晰易懂的代码
- 学会分析复杂度,能够优化算法
- 面试时要边写边解释思路
本章核心要点:
- ✅ 数组和字符串的高频操作题
- ✅ 链表的基础操作和进阶技巧
- ✅ 二叉树的各种遍历方法
- ✅ 动态规划的入门经典题目
- ✅ 面试解题框架和模式识别
下一章预告: 系统设计算法题 - 设计数据结构、LRU缓存、一致性哈希等系统设计相关算法
#java##互联网行业现在还值得去吗##毕业论文怎么查AI率#Java面试圣经 文章被收录于专栏
Java面试圣经