Java 常见面试算法题汇总与解析

Java 常见面试算法题汇总与解析

算法题是程序员面试中常见的一部分，也是提升编程能力的核心手段。本文将汇总一些 Java 中常见的算法题，并提供详细的解析和实现代码，帮助开发者更好地理解和掌握算法。

---

一、字符串相关算法

1.1 字符串反转

问题描述：

给定一个字符串，返回反转后的结果。

实现代码：

public class StringReverse {public static String reverse(String str) {return new StringBuilder(str).reverse().toString();}public static void main(String[] args) {System.out.println(reverse("hello")); // 输出：olleh}
}

---

1.2 判断回文字符串

问题描述：

判断一个字符串是否为回文字符串。

实现代码：

public class PalindromeCheck {public static boolean isPalindrome(String str) {int left = 0, right = str.length() - 1;while (left < right) {if (str.charAt(left) != str.charAt(right)) {return false;}left++;right--;}return true;}public static void main(String[] args) {System.out.println(isPalindrome("level")); // 输出：trueSystem.out.println(isPalindrome("hello")); // 输出：false}
}

---

二、数组相关算法

2.1 两数之和

问题描述：

给定一个数组和一个目标值，找到两个数的索引，使它们的和等于目标值。

实现代码：

import java.util.HashMap;public class TwoSum {public static int[] twoSum(int[] nums, int target) {HashMap<Integer, Integer> map = new HashMap<>();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 solution found");}public static void main(String[] args) {int[] result = twoSum(new int[]{2, 7, 11, 15}, 9);System.out.println("Indices: " + result[0] + ", " + result[1]);}
}

---

2.2 移动零

问题描述：

将数组中的所有 0 移动到末尾，同时保持其他元素的相对顺序。

实现代码：

public class MoveZeroes {public static void moveZeroes(int[] nums) {int index = 0;for (int num : nums) {if (num != 0) {nums[index++] = num;}}while (index < nums.length) {nums[index++] = 0;}}public static void main(String[] args) {int[] nums = {0, 1, 0, 3, 12};moveZeroes(nums);for (int num : nums) {System.out.print(num + " "); // 输出：1 3 12 0 0}}
}

---

三、动态规划相关算法

3.1 斐波那契数列

问题描述：

计算斐波那契数列的第 n 项。

实现代码：

public class Fibonacci {public static int fib(int n) {if (n <= 1) return n;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}public static void main(String[] args) {System.out.println(fib(10)); // 输出：55}
}

---

3.2 最大子序和

问题描述：

找到一个数组中连续子数组的最大和。

实现代码：

public class MaxSubArray {public static int maxSubArray(int[] nums) {int currentSum = nums[0];int maxSum = nums[0];for (int i = 1; i < nums.length; i++) {currentSum = Math.max(nums[i], currentSum + nums[i]);maxSum = Math.max(maxSum, currentSum);}return maxSum;}public static void main(String[] args) {System.out.println(maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4})); // 输出：6}
}

---

四、树相关算法

4.1 二叉树的最大深度

问题描述：

计算二叉树的最大深度。

实现代码：

public class MaxDepth {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}public static int maxDepth(TreeNode root) {if (root == null) return 0;return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);System.out.println(maxDepth(root)); // 输出：3}
}

---

4.2 验证二叉搜索树

问题描述：

判断一棵树是否为二叉搜索树。

实现代码：

public class ValidateBST {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}public static boolean isValidBST(TreeNode root) {return validate(root, null, null);}private static boolean validate(TreeNode node, Integer lower, Integer upper) {if (node == null) return true;if (lower != null && node.val <= lower) return false;if (upper != null && node.val >= upper) return false;return validate(node.left, lower, node.val) && validate(node.right, node.val, upper);}public static void main(String[] args) {TreeNode root = new TreeNode(2);root.left = new TreeNode(1);root.right = new TreeNode(3);System.out.println(isValidBST(root)); // 输出：true}
}

---

通过本文的学习，相信你对 Java 中常见的算法题有了更清晰的认识和理解。这些算法涵盖了字符串、数组、动态规划和树的经典问题，适用于面试和实际开发。如果你有其他问题，欢迎在评论区讨论！