Java面试中常见的算法题及其优雅解法

在Java的面试中，算法题通常是考察候选人编程能力和思维逻辑的重要环节。这类题目往往看似简单，但实际操作起来却需要一定的技巧和经验。今天我们就来聊聊一些常见的Java算法题以及它们的优雅解法。

斐波那契数列：递归与迭代的较量

首先，我们从经典的斐波那契数列开始说起。它的定义很简单：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n >= 2)。这是一个典型的递归定义，但是直接使用递归会导致大量的重复计算，效率低下。因此，我们可以采用迭代的方式来提高性能。

public static int fibonacciIterative(int n) {
    if (n < 0) throw new IllegalArgumentException("Input must be non-negative");
    if (n == 0 || n == 1) return n;
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

这段代码不仅避免了递归带来的栈溢出风险，而且时间复杂度仅为O(n)，空间复杂度为O(1)。

排序算法：Arrays.sort的奥秘

在Java中，我们通常会使用Arrays.sort()来进行排序操作。它内部使用的是TimSort算法，这是一种结合了归并排序和插入排序的混合算法，在大多数情况下表现优异。然而，当我们需要自己实现排序时，可以选择快速排序或者归并排序。

快速排序是一种分而治之的算法，其核心思想是对数组进行分区操作。下面是一个简单的快速排序实现：

private void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

这段代码展示了快速排序的基本步骤：选择一个基准值，然后将数组分为两部分，一部分小于基准值，另一部分大于基准值。

字符串匹配：KMP算法的魅力

在字符串处理方面，KMP算法无疑是最具代表性的例子之一。它解决了传统的暴力匹配方法效率低下的问题，通过预处理模式串，使得匹配过程中能够跳过不必要的比较步骤。

public static int kmpSearch(String haystack, String needle) {
    int m = haystack.length();
    int n = needle.length();
    int[] lps = computeLPSArray(needle);
    int i = 0, j = 0;
    while (i < m) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            i++;
            j++;
        }
        if (j == n) {
            return i - j;
        } else if (i < m && haystack.charAt(i) != needle.charAt(j)) {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
    return -1;
}

private static int[] computeLPSArray(String pat) {
    int n = pat.length();
    int[] lps = new int[n];
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < n) {
        if (pat.charAt(i) == pat.charAt(len)) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

这段代码实现了KMP算法的核心功能——通过计算最长前缀后缀数组（LPS数组）来指导匹配过程，从而达到高效的字符串搜索效果。

总结

以上就是一些常见的Java面试算法题及其优雅解法。当然，Java世界里还有很多其他的算法等待我们去探索。希望这篇文章能给大家带来启发，在未来的面试中游刃有余！记住，无论多么复杂的算法，最终的目标都是为了更好地理解和解决问题。