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<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 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<Integer> inorderTraversalRecursive(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    
    private void helper(TreeNode root, List<Integer> res) {
        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<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new 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<Integer> result = solution.inorderTraversal(root);
        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<List<Integer>> adj = new ArrayList<>();
        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<Integer> queue = new LinkedList<>();
        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 面试策略建议

1. 先理解问题：确保完全理解题目要求，可以举例说明
2. 提出暴力解法：先给出简单解法，再考虑优化
3. 分析复杂度：说明当前解法的时间空间复杂度
4. 优化思路：考虑是否有更优的数据结构或算法
5. 编写代码：注意代码规范、边界条件和异常处理
6. 测试用例：用多个测试用例验证代码正确性

结语

掌握算法不仅是为了通过面试，更是提升编程能力的必经之路。建议平时多练习LeetCode、牛客网等平台的题目，分类刷题，总结规律。记住，算法能力的提升没有捷径，只有不断练习和思考。希望本文能帮助你在Java算法面试中取得好成绩！