Java 面试总结四

2025-03-07

这部分主要是跟算法相关，包括加密、排序、遍历等。

加密

（1）下列哪些算法是对称加密？
A. MD5
B. RSA
C. DES
D. SHA

排序

（2）实现冒泡排序。

（3）实现快速排序。

遍历

（4）实现二叉树的先序、中序、后序遍历。

（5）编写一个方法，找出字符串中所有重复的字符。

问答

（6）B+ 树的原理是什么？

（7）红黑树的原理是什么？

参考答案

（1）C

常见的加密算法：
（一）单向加密：只能对明文进行加密，而不能逆向通过密文得到明文，比如：
MD5：基于消息摘要算法，使用时加盐，但存在‌哈希碰撞（不同的消息可产生相同的哈希值）；
SHA：基于消息摘要算法，比 MD5 更安全，常用的是 SHA-256。
（二）对称加密：使用同一个密钥进行加密和解密，比如：
DES：密钥长度较短（56 位），存在安全漏洞；
AES：比 DES 更安全，安全性最高的为 AES-256。
（三）非对称加密：使用两个不同的密钥进行加密和解密，公钥用于加密，私钥用于解密，比如：
RSA：安全性高，适用于对大量数据的加解密，因此也需要较高的计算资源，可能在某些资源有限的场景下不太适用。加密和解密过程都是使用相同的算法，只是密钥的使用顺序不同，一般步骤为：公钥加密 -> 私钥解密 -> 私钥签名 -> 公钥验签（加密是为了防止信息被泄露，签名是为了防止信息被篡改，证书是为了防止公钥 / 身份被假冒）。

（2）冒泡排序的思想是重复地遍历待排序数列，每次比较两个相邻的元素，如果顺序错误就交换，直到没有再需要交换的。实现代码如下：

public class BubbleSort {
    public static void sort(int[] arr) {
        int temp = 0;
        // 外层循环控制遍历次数
        for (int i = 0; i < arr.length - 1; i++) {
            // 内层循环控制每一轮的比较和交换
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}

内层循环的范围会逐渐缩小，因为每一次遍历完后，最大的元素会「浮」到数组的末尾，所以在下一次遍历时，末尾的元素就不需要再比较了。优化点：添加一个布尔值标识遍历时是否发生交换，如果没有，说明数组已经有序，可以提前结束。

（3）快速排序采用分而治之的策略，其基本思想是先从待排序数组中选一个元素作为基准值，然后对数组分区，即将数组重新排列为两个子数组，一个子数组的元素都比基准值小，另一个子数组的元素都比基准值大，基准值处于中间位置，然后递归地对这两个子数组进行快速排序，从而使整个数组有序。实现代码如下：

public class QuickSort {
    /**
     * arr: 待排序数组
     * low: 数组的开始索引
     * high: 数组的结束索引
     */
    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            // pivotIndex 是分区后的基准位置
            int pivotIndex = partition(arr, low, high);
            // 递归基准左侧的子数组
            sort(arr, low, pivotIndex - 1);
            // 递归基准右侧的子数组
            sort(arr, pivotIndex + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];// 选择最后一个元素作为基准
        int smallerIndex = (low - 1);// 假设把比基准值小的元素放在左侧，记录其位置
        for (int i = low; i < high; i++) {
            if (arr[i] < pivot) {
                smallerIndex++;// 增加较小元素的位置
                // 交换，将较小元素移到左侧
                int temp = arr[smallerIndex];
                arr[smallerIndex] = arr[i];
                arr[i] = temp;
            }
        }
        // 交换，将基准元素移到中间位置
        int temp = arr[smallerIndex + 1];
        arr[smallerIndex + 1] = arr[high];
        arr[high] = temp;
        return smallerIndex + 1;// 返回基准的正确位置
    }
    
    public static void main(String[] args) {
        int[] arr = {9, 2, 3, 1, 8, 5, 7, 6, 4, 0};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

基准元素可以选择数组的第一个元素、最后一个元素、中间元素、随机元素或者三数取中等，选择合适的基准策略可以减少最坏情况的出现概率，从而提高算法的效率和性能。

（4）先序、中序、后序遍历是遍历二叉树的基本方法。
先序遍历的顺序是：根节点 -> 左子树 -> 右子树；
中序遍历的顺序是：左子树 -> 根节点 -> 右子树；
后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
实现代码如下：

// 定义二叉树的节点类
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
    // remaining omitted...
}

// 遍历算法类
public class TreeTraversal {
    
    // 先序遍历
    public static void preOrder(TreeNode root) {
        if (root == null) {return;}
        System.out.print(root.getVal() + " ");// 访问根节点
        preOrder(root.getLeft());// 递归访问左子树
        preOrder(root.getRight());// 递归访问右子树
    }
    
    // 中序遍历
    public static void inOrder(TreeNode root) {
        if (root == null) {return;}
        inOrder(root.getLeft());   // 递归访问左子树
        System.out.print(root.getVal() + " ");// 访问根节点
        inOrder(root.getRight());  // 递归访问右子树
    }
    
    // 后序遍历
    public static void postOrder(TreeNode root) {
        if (root == null) {return;}
        postOrder(root.getLeft());// 递归访问左子树
        postOrder(root.getRight());// 递归访问右子树
        System.out.print(root.getVal() + " ");// 访问根节点
    }
}

（5）方法如下：

public static void removeDuplicateChar(String str) {
    char[] charArr = str.toCharArray();
    Set set = new HashSet();
    for (char c : charArr) {
        if (!set.add(c)) {
            System.out.println("重复: " + c);
        }
    }
    System.out.println(set.toString());
}

（6）B+ 树是多路平衡树，所有数据存储在叶子节点并形成链表，内部节点仅用于路由‌。适合磁盘存储，广泛应用于数据库索引和文件系统‌，其核心设计目标是减少磁盘 I/O 次数并支持高效的范围查询。

（7）红黑树是二叉平衡树，数据分布在所有节点，通过颜色标记和旋转规则保持平衡‌。适合内存操作，