Java面试中常见的算法题型

各位小伙伴们，今天咱们来聊聊Java面试中那些让人“脑细胞爆炸”的算法题！这些题目看似简单，但如果你没做好准备，它们可能会像一条条调皮的小泥鳅一样从你的指缝中溜走。不过别担心，我今天就来带大家捋一捋Java面试中常见的算法题型，让你在面试官面前游刃有余。

一、排序算法

首先登场的是排序算法，这是面试官最喜欢考的点之一。排序算法就像你整理书架的过程，把一堆乱七八糟的东西按照一定的规则排好序。Java中常用的排序算法有冒泡排序、快速排序、归并排序和堆排序等。

冒泡排序就像是一个懒惰的图书管理员，它会一遍又一遍地比较相邻的两个元素，如果顺序不对就交换位置，直到整个数组有序。虽然它的效率不高，但在面试中常常用来测试基础。

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

接下来是快速排序，它是大神级别的存在。它采用分治法策略，通过一个基准值将数组分成两部分，一部分比基准值小，另一部分比基准值大，然后递归地对这两部分进行排序。

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 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++;
            // 交换元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将基准值放到正确的位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

二、查找算法

查找算法就像是你在茫茫人海中寻找自己的朋友。Java中最常见的查找算法有线性查找和二分查找。

线性查找就像你一个一个地问路，直到找到你要找的人。它的效率不高，但在数据量较小时还是可以接受的。

public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

而二分查找则是你先确定中间那个人，如果比目标大就往左找，比目标小就往右找，大大提高了查找效率。

public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

三、动态规划

动态规划就像是你在规划一次旅行，你需要考虑各种因素来选择最佳路线。它通常用于解决最优解问题，比如背包问题、最长公共子序列等。

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][capacity];
}

四、字符串操作

字符串操作就像是你在处理一封封信件，你需要拼接、分割、替换等。Java中常用的字符串操作有反转字符串、判断回文串等。

public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

五、树与图

树与图就像是复杂的社会关系网，你需要遍历它们来找到你需要的信息。常见的树遍历有前序遍历、中序遍历、后序遍历，图的遍历有深度优先搜索和广度优先搜索。

public void preOrder(Node root) {
    if (root != null) {
        System.out.print(root.value + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

以上就是Java面试中常见的算法题型啦，希望这些内容能帮你在面试中取得好成绩。记住，练习是王道，多做题才能在关键时刻发挥出色哦！