Java面试黄金宝典22

1. 树的中序遍历，除了递归和栈还有什么实现方式

• 定义

Morris 遍历是一种用于二叉树遍历的算法，它利用树中大量空闲的空指针，在不使用额外栈空间和递归的情况下，完成树的遍历。通过建立临时的线索连接，使得可以按照中序遍历的顺序访问节点，访问完后再将这些线索连接恢复。

• 要点

1. 线索连接构建：寻找当前节点左子树的最右节点，将其右指针指向当前节点，以便在遍历完左子树后能回到当前节点。
2. 节点访问时机：若当前节点的左子树为空，或者左子树的最右节点的右指针已经指向当前节点，说明左子树已经遍历完，此时访问当前节点，并继续遍历右子树。
3. 复杂度分析：时间复杂度为 O(n)，空间复杂度为 O(1)，非常适合处理大规模数据的二叉树遍历。

• 应用

1. 数据库索引遍历：在数据库的 B - 树索引中，使用 Morris 遍历可以高效地访问数据，减少额外空间开销，提高数据检索效率。
2. 嵌入式系统开发：嵌入式系统内存资源有限，Morris 遍历能在不占用过多内存的情况下完成二叉树操作，如文件系统的目录树遍历。

java

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}public class MorrisInorderTraversal {public void inorderTraversal(TreeNode root) {TreeNode current = root;while (current != null) {if (current.left == null) {System.out.print(current.val + " ");current = current.right;} else {TreeNode pre = current.left;while (pre.right != null && pre.right != current) {pre = pre.right;}if (pre.right == null) {pre.right = current;current = current.left;} else {pre.right = null;System.out.print(current.val + " ");current = current.right;}}}}
}

2. BFS 和 DFS 的区别

• 定义

1. BFS（广度优先搜索）：从起始节点开始，逐层地访问节点，先访问距离起始节点最近的所有节点，然后再依次访问距离更远的节点。通常使用队列来实现，将起始节点入队，然后不断从队列中取出节点，将其未访问的邻接节点入队。
2. DFS（深度优先搜索）：从起始节点开始，沿着一条路径尽可能深地访问节点，直到无法继续，然后回溯到上一个节点，继续探索其他路径。可以使用递归或栈来实现，递归时函数调用栈起到栈的作用。

• 要点

1. 访问顺序：BFS 是逐层访问，能保证找到的路径是最短路径；DFS 是沿着一条路径深入访问，更适合探索连通性。
2. 数据结构：BFS 使用队列，先进先出；DFS 可以使用递归或栈，后进先出。
3. 空间复杂度：BFS 的空间复杂度取决于树的最大宽度，DFS 的空间复杂度取决于树的最大深度。

• 应用
• BFS 应用
  1. 地图导航：在地图中寻找两点之间的最短路径，BFS 可以快速找到最优解。
  2. 社交网络分析：查找某个用户的一度、二度好友等。
• DFS 应用
  1. 迷宫求解：可以快速找到一条可行路径。
  2. 编译器的语法分析：分析代码的语法结构，检查代码的正确性。

3. 给定 n 个数，寻找第 k 小的数

• 定义

快速选择算法是基于快速排序思想的一种选择算法，用于在未排序的数组中找到第 k 小（或第 k 大）的元素。通过选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素，然后根据基准元素的位置与 k 的关系，决定在左边或右边部分继续查找。

• 要点

1. 基准元素选择：可以选择数组的第一个元素、最后一个元素或随机选择一个元素作为基准元素。
2. 分区操作：将数组分为两部分，左边部分小于等于基准元素，右边部分大于等于基准元素。
3. 复杂度分析：时间复杂度平均为 O(n)，最坏情况下为 O(n2)。

• 应用

1. 数据分析：在大量数据中找出中位数或其他分位数。
2. 游戏开发：在游戏排行榜中找出排名第 k 的玩家。

java

public class KthSmallestElement {public int findKthSmallest(int[] nums, int k) {return quickSelect(nums, 0, nums.length - 1, k - 1);}private int quickSelect(int[] nums, int left, int right, int k) {if (left == right) {return nums[left];}int pivotIndex = partition(nums, left, right);if (k == pivotIndex) {return nums[k];} else if (k < pivotIndex) {return quickSelect(nums, left, pivotIndex - 1, k);} else {return quickSelect(nums, pivotIndex + 1, right, k);}}private int partition(int[] nums, int left, int right) {int pivot = nums[right];int i = left - 1;for (int j = left; j < right; j++) {if (nums[j] <= pivot) {i++;swap(nums, i, j);}}swap(nums, i + 1, right);return i + 1;}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

4. 求 1000 以内的素数

• 定义

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种用于找出一定范围内所有素数的算法。其基本思想是从 2 开始，将每个素数的倍数标记为合数，直到遍历完所有小于等于根号n的数，剩下未被标记的数即为素数。

• 要点

1. 初始化标记数组：创建一个布尔数组，用于标记每个数是否为素数。
2. 标记合数：从 2 开始，将每个素数的倍数标记为合数。
3. 复杂度分析：时间复杂度为 O(nloglogn)。

• 应用

1. 密码学：在生成大素数时，可以使用该算法的思想进行初步筛选。
2. 数论研究：研究素数分布规律时，可使用该算法生成一定范围内的素数进行分析。

java

import java.util.ArrayList;
import java.util.List;public class PrimeNumbers {public List<Integer> findPrimes(int n) {boolean[] isPrime = new boolean[n + 1];for (int i = 2; i <= n; i++) {isPrime[i] = true;}for (int p = 2; p * p <= n; p++) {if (isPrime[p]) {for (int i = p * p; i <= n; i += p) {isPrime[i] = false;}}}List<Integer> primes = new ArrayList<>();for (int i = 2; i <= n; i++) {if (isPrime[i]) {primes.add(i);}}return primes;}
}

5. 手写希尔排序

• 定义

希尔排序是一种改进的插入排序算法，也称为缩小增量排序。它通过将原始数据分成多个子序列来改善插入排序的性能，先比较距离较远的元素，而不是像插入排序那样比较相邻元素，这样可以使元素更快地移动到它们应该在的位置附近。然后逐渐缩小间隔，直到间隔为 1，此时就是普通的插入排序。

• 要点

1. 间隔序列选择：通常初始间隔为数组长度的一半，然后每次缩小一半，直到间隔为 1。不同的间隔序列会影响算法的性能。
2. 子序列插入排序：对每个间隔进行插入排序。
3. 复杂度分析：时间复杂度取决于间隔序列的选择，平均情况下为 O(n^1.3)。

• 应用

1. 数据库排序：在数据库中对大规模数据进行排序时，希尔排序可以在一定程度上提高排序效率。
2. 游戏开发中的资源排序：对游戏中的各种资源进行排序，如角色属性、关卡难度等。

java

public class ShellSort {public void shellSort(int[] arr) {int n = arr.length;for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}}
}

6. 利用数组，实现一个循环队列类

• 定义

循环队列是一种线性数据结构，它使用数组来存储元素，并通过两个指针（front 和 rear）来表示队列的头部和尾部。当队列的尾部指针到达数组的末尾时，可以通过取模运算将其重新指向数组的开头，从而实现循环利用数组空间。

• 要点

1. 初始化操作：初始化数组、队列容量、头部指针和尾部指针。
2. 入队和出队操作：入队操作时，将元素插入到尾部指针的位置，并更新尾部指针；出队操作时，取出头部指针位置的元素，并更新头部指针。
3. 队列状态判断：队列满的条件是 (rear + 1) % capacity == front，队列为空的条件是 front == rear。

• 应用

1. 操作系统中的任务调度：使用循环队列来管理待执行的任务，提高系统资源利用率。
2. 网络数据包处理：在网络设备中，使用循环队列来缓存数据包，确保数据的有序处理。

java

class CircularQueue {private int[] queue;private int front;private int rear;private int capacity;public CircularQueue(int capacity) {this.capacity = capacity;this.queue = new int[capacity];this.front = 0;this.rear = 0;}public boolean isFull() {return (rear + 1) % capacity == front;}public boolean isEmpty() {return front == rear;}public void enqueue(int item) {if (isFull()) {System.out.println("Queue is full");return;}queue[rear] = item;rear = (rear + 1) % capacity;}public int dequeue() {if (isEmpty()) {System.out.println("Queue is empty");return -1;}int item = queue[front];front = (front + 1) % capacity;return item;}
}

7. 写一个汉诺塔问题，打印出转移路径

• 定义

汉诺塔问题是一个经典的递归问题。假设有三根柱子 A、B、C，要将 n 个盘子从柱子 A 移动到柱子 C，可以将问题分解为以下三个步骤：先将 n - 1 个盘子从柱子 A 移动到柱子 B，再将第 n 个盘子从柱子 A 移动到柱子 C，最后将 n - 1 个盘子从柱子 B 移动到柱子 C。

• 要点

1. 递归函数设计：使用递归函数来解决问题，递归函数的参数包括盘子的数量、起始柱子、辅助柱子和目标柱子。
2. 递归终止条件：递归的终止条件是盘子数量为 1，此时直接将盘子从起始柱子移动到目标柱子。

• 应用

1. 算法教学：作为递归算法的经典案例，帮助学生理解递归的思想和实现方法。
2. 人工智能中的搜索算法：汉诺塔问题的求解过程可以类比为搜索算法中的状态转移，用于研究搜索策略。

java

public class HanoiTower {public void hanoi(int n, char source, char auxiliary, char target) {if (n == 1) {System.out.println("Move disk 1 from " + source + " to " + target);return;}hanoi(n - 1, source, target, auxiliary);System.out.println("Move disk " + n + " from " + source + " to " + target);hanoi(n - 1, auxiliary, source, target);}
}

8. 写一个二叉树前序遍历的代码

• 定义

前序遍历是一种二叉树的遍历方式，按照根节点 -> 左子树 -> 右子树的顺序访问节点。可以使用递归或栈来实现。递归实现是先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树；栈实现是将根节点入栈，然后不断从栈中取出节点，访问该节点，将其右子节点和左子节点依次入栈（注意顺序，先右后左）。

• 要点

1. 递归实现要点：递归函数的设计和递归终止条件的判断。
2. 栈实现要点：栈的操作，包括入栈和出栈，以及节点入栈的顺序。

• 应用

1. 文件系统遍历：在文件系统中，使用前序遍历可以快速访问根目录下的所有文件和子目录。
2. XML 文档解析：解析 XML 文档时，前序遍历可以按照文档的层次结构依次访问节点。

java

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}import java.util.Stack;public class PreorderTraversal {// 递归实现public void preorderRecursive(TreeNode root) {if (root != null) {System.out.print(root.val + " ");preorderRecursive(root.left);preorderRecursive(root.right);}}// 栈实现public void preorderIterative(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();System.out.print(node.val + " ");if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}}
}

9. 写一个多叉树实现，并层次遍历的代码

• 定义

多叉树是一种每个节点可以有多个子节点的树结构。层次遍历是按照树的层次依次访问节点，通常使用队列来实现。将根节点入队，然后不断从队列中取出节点，访问该节点，并将其所有子节点入队。

• 要点

1. 多叉树节点定义：定义多叉树节点类，包含节点值和子节点列表。
2. 层次遍历实现：使用队列进行层次遍历，确保按层次顺序访问节点。

• 应用

1. 文件系统目录结构表示：文件系统的目录结构可以用多叉树表示，层次遍历可以用于查看目录下的所有文件和子目录。
2. 组织架构图表示：企业的组织架构可以用多叉树表示，层次遍历可以用于查看各个部门和员工的信息。

java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;class TreeNode {int val;List<TreeNode> children;TreeNode(int val) {this.val = val;this.children = new ArrayList<>();}
}public class NaryTreeLevelOrderTraversal {public void levelOrderTraversal(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.val + " ");for (TreeNode child : node.children) {queue.offer(child);}}}
}

10. 从一堆字符串中，去除重复的字符，并输出

• 定义

可以使用哈希集合（HashSet）来去除字符串中重复的字符。遍历字符串中的每个字符，将其添加到哈希集合中，由于哈希集合不允许重复元素，重复的字符会自动被过滤掉。最后将哈希集合中的字符拼接成字符串输出。

• 要点

1. 哈希集合的使用：利用哈希集合不允许重复元素的特性来过滤重复字符。
2. 字符串拼接：将哈希集合中的字符按顺序拼接成字符串。
3. 复杂度分析：时间复杂度为 O(n)，其中 n 是字符串的长度。

• 应用

1. 数据清洗：在处理文本数据时，去除重复字符可以减少数据冗余，提高数据质量。
2. 信息检索：在构建索引时，去除重复字符可以减少索引的大小，提高检索效率。

java

import java.util.HashSet;
import java.util.Set;public class RemoveDuplicateCharacters {public String removeDuplicates(String str) {Set<Character> set = new HashSet<>();StringBuilder result = new StringBuilder();for (char c : str.toCharArray()) {if (set.add(c)) {result.append(c);}}return result.toString();}
}

友情提示：本文已经整理成文档，可以到如下链接免积分下载阅读

https://download.csdn.net/download/ylfhpy/90546476