Java面试黄金宝典18

1. 如何找到一条单链表的中间结点

• 定义

单链表是一种常见的数据结构，每个节点包含数据和指向下一个节点的指针。找到单链表的中间结点，即找出链表中位于中间位置的节点。可借助快慢指针法达成，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针正好处于链表中间。

• 要点

1. 初始化快慢指针，使其都指向链表的头节点。
2. 快指针移动速度为慢指针的两倍。
3. 当快指针抵达链表末尾（快指针为空或者快指针的下一个节点为空）时，慢指针所指即为中间节点。

代码示例

java

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class MiddleOfLinkedList {public ListNode middleNode(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}public static void main(String[] args) {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);MiddleOfLinkedList solution = new MiddleOfLinkedList();ListNode middle = solution.middleNode(head);System.out.println(middle.val);}
}

• 应用

1. 链表数据处理：在对链表进行分治操作时，可将链表从中间断开，分别处理左右两部分。
2. 链表对折操作：实现链表对折功能时，需要先找到中间节点。

2. 从 10 亿个数中找不重复的数

• 定义

在海量数据（如 10 亿个数）中找出不重复的数，可采用位图（BitMap）或者哈希表结合分治的方法。位图是用一个二进制位来表示一个数是否出现过；哈希表结合分治则是把大数据拆分成多个小文件，对每个小文件用哈希表统计数字出现次数，最后汇总结果。

• 要点

1. 位图：依据数据范围确定位图大小，运用位运算操作位图。
2. 哈希表结合分治：合理划分小文件，防止小文件过大导致内存不足。

代码示例（位图）

java

import java.util.BitSet;public class FindUniqueNumbers {public static void findUnique(int[] numbers) {BitSet bitSet = new BitSet();BitSet repeated = new BitSet();for (int num : numbers) {if (bitSet.get(num)) {repeated.set(num);} else {bitSet.set(num);}}for (int i = 0; i < bitSet.size(); i++) {if (bitSet.get(i) && !repeated.get(i)) {System.out.println(i);}}}public static void main(String[] args) {int[] numbers = {1, 2, 2, 3, 4, 4, 5};findUnique(numbers);}
}

• 应用

1. 数据去重：在海量数据里找出唯一的数据。
2. 数据库索引优化：去除重复的索引键，提升数据库性能。

3. 判断二叉树是否为平衡二叉树

• 定义

平衡二叉树，也叫 AVL 树，其每个节点的左右子树高度差不超过 1，并且左右子树也都是平衡二叉树。可通过递归方法计算每个节点的左右子树高度，以此判断高度差是否满足条件。

• 要点

1. 递归计算左右子树的高度。
2. 判断每个节点的左右子树高度差是否不超过 1。

代码示例

java

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}public class BalancedBinaryTree {public boolean isBalanced(TreeNode root) {return height(root) != -1;}private int height(TreeNode node) {if (node == null) {return 0;}int leftHeight = height(node.left);if (leftHeight == -1) {return -1;}int rightHeight = height(node.right);if (rightHeight == -1) {return -1;}if (Math.abs(leftHeight - rightHeight) > 1) {return -1;}return Math.max(leftHeight, rightHeight) + 1;}public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);BalancedBinaryTree solution = new BalancedBinaryTree();System.out.println(solution.isBalanced(root));}
}

• 应用

1. 数据库索引结构：维持树的平衡能够提高数据库查询效率。
2. 搜索引擎索引构建：使用平衡二叉树可快速定位数据。

4. 50.0G 文件的淘宝商品编号，只有 512M 内存，怎么判断究竟是不是合法编号（即编号是否存在）

• 定义

处理大文件（如 50.0G 的淘宝商品编号文件）且内存有限（仅 512M）时，要判断编号是否合法，可采用分治和哈希的思想。把大文件拆分成多个小文件，对每个小文件进行哈希处理，然后将小文件加载到内存中查找。还可使用布隆过滤器先进行快速过滤，减少不必要的文件读取。

• 要点

1. 合理划分小文件，保证每个小文件能加载到内存中。
2. 运用哈希函数处理编号，便于快速查找。
3. 布隆过滤器可快速判断编号是否可能存在。

• 实现步骤

1. 遍历大文件，依据编号的哈希值将编号划分到不同的小文件中。
2. 对于要查询的编号，计算其哈希值，确定对应的小文件。
3. 将小文件加载到内存中，使用哈希表或其他数据结构进行查找。
4. 可使用布隆过滤器在加载小文件之前进行快速判断。

• 应用

1. 大数据量文件查询：例如在日志文件中查找特定记录。
2. 电商平台商品编号验证：确保商品编号的合法性。

5. 假如淘宝存着一个包含 10w 个敏感词的词库，紧接着需要从多个商品标题中随机抽查 3 个有没有包含敏感词的商品

• 定义

在拥有大量敏感词（如 10w 个）的词库情况下，从多个商品标题中随机抽取部分标题，检查其中是否包含敏感词。可借助 Trie 树（字典树）存储敏感词库，通过遍历商品标题在 Trie 树中查找是否存在敏感词。

• 要点

1. 构建 Trie 树存储敏感词库。
2. 遍历商品标题，在 Trie 树中查找是否存在敏感词。

代码示例

java

class TrieNode {TrieNode[] children = new TrieNode[26];boolean isEndOfWord;
}class Trie {private TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {TrieNode node = root;for (char c : word.toCharArray()) {int index = c - 'a';if (node.children[index] == null) {node.children[index] = new TrieNode();}node = node.children[index];}node.isEndOfWord = true;}public boolean search(String word) {TrieNode node = root;for (char c : word.toCharArray()) {int index = c - 'a';if (node.children[index] == null) {return false;}node = node.children[index];}return node.isEndOfWord;}
}import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class SensitiveWordCheck {public static boolean checkSensitiveWords(List<String> sensitiveWords, String title) {Trie trie = new Trie();for (String word : sensitiveWords) {trie.insert(word);}for (int i = 0; i < title.length(); i++) {for (int j = i + 1; j <= title.length(); j++) {String sub = title.substring(i, j);if (trie.search(sub)) {return true;}}}return false;}public static void main(String[] args) {List<String> sensitiveWords = new ArrayList<>();sensitiveWords.add("敏感词1");sensitiveWords.add("敏感词2");List<String> titles = new ArrayList<>();titles.add("这是一个包含敏感词1的标题");titles.add("这是一个正常标题");titles.add("这是另一个包含敏感词2的标题");Random random = new Random();for (int i = 0; i < 3; i++) {int index = random.nextInt(titles.size());String title = titles.get(index);boolean hasSensitiveWord = checkSensitiveWords(sensitiveWords, title);System.out.println("标题: " + title + " 是否包含敏感词: " + hasSensitiveWord);}}
}

• 应用

1. 内容审核：像论坛、博客等平台的帖子审核。
2. 电商平台商品标题审核：保证商品标题合规。

6. 如何查找中间链表元素

• 定义

同问题 1，单链表查找中间元素可使用快慢指针法。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针处于链表中间。

• 要点

1. 初始化快慢指针，使其都指向链表的头节点。
2. 快指针移动速度为慢指针的两倍。
3. 当快指针抵达链表末尾（快指针为空或者快指针的下一个节点为空）时，慢指针所指即为中间节点。

代码示例

java

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class MiddleOfLinkedList {public ListNode middleNode(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}public static void main(String[] args) {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);MiddleOfLinkedList solution = new MiddleOfLinkedList();ListNode middle = solution.middleNode(head);System.out.println(middle.val);}
}

• 应用

1. 链表数据处理：对链表进行分治操作时，可从中间断开链表分别处理。
2. 链表对折操作：实现链表对折功能时，需先找到中间节点。

7. 什么是图算法

• 定义

图算法是用于处理图数据结构的一系列算法。图由顶点和边构成，图算法能够解决图的遍历、最短路径、连通性、拓扑排序等问题。

• 常见图算法

1. 深度优先搜索（DFS）：沿着图的深度遍历节点，尽可能深地搜索分支。
2. 广度优先搜索（BFS）：从起始节点开始，逐层地访问节点。
3. Dijkstra 算法：用于求解单源最短路径问题。
4. Floyd - Warshall 算法：用于求解所有节点对之间的最短路径问题。
5. Kruskal 算法和 Prim 算法：用于求解最小生成树问题。

• 应用

1. 社交网络分析：如好友推荐、社区发现。
2. 地图导航：如最短路径规划。
3. 电路设计：如电路连通性分析。

8. 什么是平衡树的旋转

• 定义

平衡树（如 AVL 树、红黑树）在插入或删除节点后，可能会破坏树的平衡性质。平衡树的旋转是一种调整树结构的操作，能使树重新满足平衡条件。旋转操作分为左旋和右旋。

• 左旋

1. 原理：以某个节点为支点，将其右子树提升为根节点，原根节点变为新根节点的左子树，新根节点的左子树变为原根节点的右子树。
2. 作用：调整树的高度，使树保持平衡。

• 右旋

1. 原理：以某个节点为支点，将其左子树提升为根节点，原根节点变为新根节点的右子树，新根节点的右子树变为原根节点的左子树。
2. 作用：调整树的高度，使树保持平衡。

• 应用

1. 数据库索引结构：保持树的平衡可提高数据库查询效率。
2. 搜索引擎索引构建：使用平衡树可快速定位数据。

9. 动态规划的思想

• 定义

动态规划是一种算法策略，通过把原问题分解为相对简单的子问题，并保存子问题的解来避免重复计算，从而解决复杂问题。

• 要点

1. 最优子结构：问题的最优解包含子问题的最优解。
2. 子问题重叠：求解过程中会多次遇到相同的子问题。
3. 状态转移方程：定义子问题之间的关系，通过已知子问题的解推导出当前问题的解。

• 应用

1. 背包问题：如 0 - 1 背包问题、完全背包问题。
2. 最长公共子序列问题：在字符串处理等场景有应用。
3. 最短路径问题：如 Floyd - Warshall 算法。

10. 给出一个字符数组，找出第一个出现次数最多的字符，注意是第一个

• 定义

给定一个字符数组，要找出其中第一个出现次数最多的字符。可使用哈希表记录每个字符的出现次数，同时记录最大出现次数和第一个达到最大出现次数的字符。

• 要点

1. 遍历字符数组，更新哈希表中字符的出现次数。
2. 记录最大出现次数和第一个达到最大出现次数的字符。

代码示例

java

public class FirstMaxOccurrenceChar {public static char findFirstMaxOccurrence(char[] chars) {int[] count = new int[256];int maxCount = 0;char result = '\0';for (char c : chars) {count[c]++;if (count[c] > maxCount) {maxCount = count[c];result = c;}}return result;}public static void main(String[] args) {char[] chars = {'a', 'b', 'c', 'a', 'b', 'a'};char maxChar = findFirstMaxOccurrence(chars);System.out.println("第一个出现次数最多的字符是: " + maxChar);}
}

• 应用

1. 文本分析：统计文本中出现频率最高的字符。
2. 密码学：分析字符出现频率以破解密码。

 

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

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