高难度题
这一章包含各种高难度的综合题目，需要综合运用多种数据结构和算法知识。
面试题 17.01. 不用加号的加法
题目描述
设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。
示例：
输入: a = 1, b = 1
输出: 2
解题思路
使用位运算。异或运算得到无进位加法结果，与运算后左移一位得到进位。循环直到进位为 0。
Java 代码实现
class Solution {
public int add(int a, int b) {
while (b != 0) {
int carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}
}
面试题 17.04. 消失的数字
题目描述
数组 nums 包含从 0 到 n 的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。
示例 1：
输入：[3,0,1]
输出：2
解题思路
方法一：异或
将所有数字与 0 到 n 的所有数字异或，最后剩下的就是缺失的数字。
方法二：求和
计算 0 到 n 的和，减去数组中所有数字的和。
Java 代码实现
异或法：
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int result = n;
for (int i = 0; i < n; i++) {
result ^= i ^ nums[i];
}
return result;
}
}
面试题 17.05. 字母与数字
题目描述
给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
示例：
输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]
输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]
解题思路
使用前缀和。将字母视为 +1，数字视为 -1，找到前缀和相同的两个位置，中间的子数组满足条件。
Java 代码实现
class Solution {
public String[] findLongestSubarray(String[] array) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0;
int maxLen = 0;
int start = -1;
for (int i = 0; i < array.length; i++) {
char c = array[i].charAt(0);
if (Character.isLetter(c)) {
sum++;
} else {
sum--;
}
if (map.containsKey(sum)) {
int prevIndex = map.get(sum);
if (i - prevIndex > maxLen) {
maxLen = i - prevIndex;
start = prevIndex + 1;
}
} else {
map.put(sum, i);
}
}
if (maxLen == 0) {
return new String[]{};
}
return Arrays.copyOfRange(array, start, start + maxLen);
}
}
面试题 17.06. 2出现的次数
题目描述
编写一个方法，计算从 0 到 n（含 n）中数字 2 出现的次数。
示例：
输入: 25
输出: 9
解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)
解题思路
按位计算每一位上 2 出现的次数。对于某一位，根据高位、当前位和低位来计算。
Java 代码实现
class Solution {
public int numberOf2sInRange(int n) {
int count = 0;
for (long i = 1; i <= n; i *= 10) {
long high = n / (i * 10);
long cur = (n / i) % 10;
long low = n % i;
if (cur < 2) {
count += high * i;
} else if (cur == 2) {
count += high * i + low + 1;
} else {
count += (high + 1) * i;
}
}
return count;
}
}
面试题 17.07. 婴儿名字
题目描述
每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率。现在给定两个列表，一个是名字及对应的频率，另一个是名字对（表示两个名字是等价的），找出等价名字的真实频率。
示例：
输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)","Kris(4)"]
解题思路
使用并查集将等价的名字合并，然后统计每个集合的频率总和。
Java 代码实现
class Solution {
public String[] trulyMostPopular(String[] names, String[] synonyms) {
Map<String, Integer> freq = new HashMap<>();
Map<String, String> parent = new HashMap<>();
for (String name : names) {
int idx = name.indexOf('(');
String n = name.substring(0, idx);
int f = Integer.parseInt(name.substring(idx + 1, name.length() - 1));
freq.put(n, f);
parent.put(n, n);
}
for (String syn : synonyms) {
String[] pair = syn.substring(1, syn.length() - 1).split(",");
String a = pair[0], b = pair[1];
if (!parent.containsKey(a)) parent.put(a, a);
if (!parent.containsKey(b)) parent.put(b, b);
union(parent, a, b);
}
Map<String, Integer> result = new HashMap<>();
for (String name : freq.keySet()) {
String root = find(parent, name);
result.put(root, result.getOrDefault(root, 0) + freq.get(name));
}
String[] ans = new String[result.size()];
int i = 0;
for (Map.Entry<String, Integer> entry : result.entrySet()) {
ans[i++] = entry.getKey() + "(" + entry.getValue() + ")";
}
return ans;
}
private String find(Map<String, String> parent, String x) {
if (!parent.get(x).equals(x)) {
parent.put(x, find(parent, parent.get(x)));
}
return parent.get(x);
}
private void union(Map<String, String> parent, String a, String b) {
String rootA = find(parent, a);
String rootB = find(parent, b);
if (rootA.compareTo(rootB) < 0) {
parent.put(rootB, rootA);
} else {
parent.put(rootA, rootB);
}
}
}
面试题 17.08. 马戏团人塔
题目描述
有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
示例：
输入：height = [65,70,56,75,60,68], weight = [100,150,90,190,95,110]
输出：6
解题思路
先按身高升序排序（身高相同时按体重降序），然后对体重求最长递增子序列。
Java 代码实现
class Solution {
public int bestSeqAtIndex(int[] height, int[] weight) {
int n = height.length;
int[][] persons = new int[n][2];
for (int i = 0; i < n; i++) {
persons[i] = new int[]{height[i], weight[i]};
}
Arrays.sort(persons, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int[] dp = new int[n];
int len = 0;
for (int[] person : persons) {
int i = Arrays.binarySearch(dp, 0, len, person[1]);
if (i < 0) i = -(i + 1);
dp[i] = person[1];
if (i == len) len++;
}
return len;
}
}
面试题 17.09. 第 k 个数
题目描述
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。
示例：
输入: k = 5
输出: 9
解题思路
使用三指针，类似丑数问题。维护三个指针分别指向乘以 3、5、7 的位置。
Java 代码实现
class Solution {
public int getKthMagicNumber(int k) {
int[] dp = new int[k];
dp[0] = 1;
int p3 = 0, p5 = 0, p7 = 0;
for (int i = 1; i < k; i++) {
int n3 = dp[p3] * 3;
int n5 = dp[p5] * 5;
int n7 = dp[p7] * 7;
dp[i] = Math.min(n3, Math.min(n5, n7));
if (dp[i] == n3) p3++;
if (dp[i] == n5) p5++;
if (dp[i] == n7) p7++;
}
return dp[k - 1];
}
}
面试题 17.10. 主要元素
题目描述
如果数组中多一半的数都是同一个，则称之为主要元素。给定一个整数数组，找到主要元素。如果没有，返回 -1。
示例 1：
输入：[1,2,5,9,5,9,5,5,5]
输出：5
解题思路
使用 Boyer-Moore 投票算法。遍历数组，维护候选元素和计数。
Java 代码实现
class Solution {
public int majorityElement(int[] nums) {
int candidate = 0, count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
count = 0;
for (int num : nums) {
if (num == candidate) count++;
}
return count > nums.length / 2 ? candidate : -1;
}
}
面试题 17.11. 单词距离
题目描述
有个内含单词的超大文本文件，给定任意两个不同的单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?
示例：
输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
输出：1
解题思路
遍历数组，记录两个单词最近出现的位置，计算最小距离。
Java 代码实现
class Solution {
public int findClosest(String[] words, String word1, String word2) {
int index1 = -1, index2 = -1;
int minDist = Integer.MAX_VALUE;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
index1 = i;
} else if (words[i].equals(word2)) {
index2 = i;
}
if (index1 != -1 && index2 != -1) {
minDist = Math.min(minDist, Math.abs(index1 - index2));
}
}
return minDist;
}
}
面试题 17.12. BiNode
题目描述
二叉树数据结构 TreeNode 可用来表示单向链表（其中 left 置空，right 为下一个节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质。
示例：
输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
解题思路
中序遍历，修改节点指针。
Java 代码实现
class Solution {
private TreeNode prev = null;
private TreeNode head = null;
public TreeNode convertBiNode(TreeNode root) {
inorder(root);
return head;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
if (prev == null) {
head = node;
} else {
prev.right = node;
}
node.left = null;
prev = node;
inorder(node.right);
}
}
面试题 17.13. 恢复空格
题目描述
哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子 "I reset the computer. It still didn't boot!" 已经变成了 "iresetthecomputeritstilldidntboot"。在处理前这个句子是于一本词典中的，你现在需要一个算法来识别出最原始的句子。
示例 1：
输入：dictionary = ["looked","just","like","her","brother"], sentence = "jesslookedjustliketimherbrother"
输出：7
解题思路
使用动态规划。dp[i] 表示前 i 个字符中未识别的字符数。使用 Trie 树优化查找。
Java 代码实现
class Solution {
public int respace(String[] dictionary, String sentence) {
Set<String> dict = new HashSet<>(Arrays.asList(dictionary));
int n = sentence.length();
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
for (int j = 0; j < i; j++) {
if (dict.contains(sentence.substring(j, i))) {
dp[i] = Math.min(dp[i], dp[j]);
}
}
}
return dp[n];
}
}
面试题 17.14. 最小K个数
题目描述
设计一个算法，找出数组中最小的 k 个数，以任意顺序返回这 k 个数均可。
示例：
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
解题思路
使用快速选择算法或堆排序。
Java 代码实现
class Solution {
public int[] smallestK(int[] arr, int k) {
if (k == 0) return new int[0];
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
for (int num : arr) {
if (heap.size() < k) {
heap.offer(num);
} else if (num < heap.peek()) {
heap.poll();
heap.offer(num);
}
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = heap.poll();
}
return result;
}
}
面试题 17.15. 最长单词
题目描述
给定一组单词 words，请找出其中最长的一个单词，该单词由 words 中其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
示例：
输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
输出： "dogwalker"
解题思路
将单词按长度降序排序，然后检查每个单词是否可以由其他单词组成。
Java 代码实现
class Solution {
public String longestWord(String[] words) {
Arrays.sort(words, (a, b) -> a.length() == b.length() ? a.compareTo(b) : b.length() - a.length());
Set<String> set = new HashSet<>(Arrays.asList(words));
for (String word : words) {
set.remove(word);
if (canForm(word, set)) {
return word;
}
set.add(word);
}
return "";
}
private boolean canForm(String word, Set<String> set) {
if (word.length() == 0) return true;
for (int i = 1; i <= word.length(); i++) {
if (set.contains(word.substring(0, i)) && canForm(word.substring(i), set)) {
return true;
}
}
return false;
}
}
面试题 17.16. 按摩师
题目描述
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，为按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
示例 1：
输入： [1,2,3,1]
输出： 4
解题思路
动态规划。dp[i] 表示前 i 个预约的最大时间。
Java 代码实现
class Solution {
public int massage(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}
面试题 17.17. 多次搜索
题目描述
给定一个较长字符串 big 和一个包含较短字符串的数组 smalls，设计一个方法，根据 smalls 中的每一个较短字符串，对 big 进行搜索。
示例：
输入：big = "mississippi", smalls = ["is","ppi","hi","sis","i","ssippi"]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]
解题思路
使用 Trie 树存储所有小字符串，然后遍历大字符串进行匹配。
Java 代码实现
class Solution {
public int[][] multiSearch(String big, String[] smalls) {
Map<String, List<Integer>> map = new HashMap<>();
for (String small : smalls) {
map.put(small, new ArrayList<>());
}
for (int i = 0; i < big.length(); i++) {
for (int j = i + 1; j <= big.length(); j++) {
String sub = big.substring(i, j);
if (map.containsKey(sub)) {
map.get(sub).add(i);
}
}
}
int[][] result = new int[smalls.length][];
for (int i = 0; i < smalls.length; i++) {
List<Integer> list = map.get(smalls[i]);
result[i] = list.stream().mapToInt(Integer::intValue).toArray();
}
return result;
}
}
面试题 17.18. 最短超串
题目描述
假设你有两个数组（长、短），短的数组中的元素各不相同，找到短数组在长数组中最短连续子数组，使其包含短数组中所有元素。
示例：
输入：big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7], small = [1,5,9]
输出：[7,10]
解题思路
使用滑动窗口，维护窗口中短数组元素的出现次数。
Java 代码实现
class Solution {
public int[] shortestSeq(int[] big, int[] small) {
Map<Integer, Integer> need = new HashMap<>();
Map<Integer, Integer> have = new HashMap<>();
for (int num : small) {
need.put(num, need.getOrDefault(num, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
int minLen = Integer.MAX_VALUE;
int[] result = new int[0];
while (right < big.length) {
int num = big[right];
right++;
if (need.containsKey(num)) {
have.put(num, have.getOrDefault(num, 0) + 1);
if (have.get(num).equals(need.get(num))) {
valid++;
}
}
while (valid == need.size()) {
if (right - left < minLen) {
minLen = right - left;
result = new int[]{left, right - 1};
}
int leftNum = big[left];
left++;
if (need.containsKey(leftNum)) {
if (have.get(leftNum).equals(need.get(leftNum))) {
valid--;
}
have.put(leftNum, have.get(leftNum) - 1);
}
}
}
return result;
}
}
面试题 17.19. 消失的两个数字
题目描述
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
示例：
输入: [1]
输出: [2,3]
解题思路
计算所有数字的和与平方和，然后解方程组找出缺失的两个数字。
Java 代码实现
class Solution {
public int[] missingTwo(int[] nums) {
int n = nums.length + 2;
long sum = (long) n * (n + 1) / 2;
long squareSum = (long) n * (n + 1) * (2L * n + 1) / 6;
for (int num : nums) {
sum -= num;
squareSum -= (long) num * num;
}
int aPlusB = (int) sum;
int a2PlusB2 = (int) squareSum;
int aMinusB = (int) Math.sqrt(2L * a2PlusB2 - (long) aPlusB * aPlusB);
int a = (aPlusB + aMinusB) / 2;
int b = aPlusB - a;
return new int[]{a, b};
}
}
面试题 17.20. 连续中值
题目描述
随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值并保存。
示例：
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);
medianFinder.addNum(2);
medianFinder.findMedian(); // 返回 1.5
medianFinder.addNum(3);
medianFinder.findMedian(); // 返回 2.0
解题思路
使用两个堆：一个大顶堆存储较小的一半，一个小顶堆存储较大的一半。
Java 代码实现
class MedianFinder {
private PriorityQueue<Integer> maxHeap;
private PriorityQueue<Integer> minHeap;
public MedianFinder() {
maxHeap = new PriorityQueue<>((a, b) -> b - a);
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.offer(num);
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.offer(maxHeap.poll());
}
} else {
minHeap.offer(num);
if (minHeap.size() > maxHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
}
public double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
}
return maxHeap.peek();
}
}
面试题 17.21. 直方图的水量
题目描述
给定一个直方图（也称柱状图），假设有人从上面源源不断地倒水，最后直方图能存多少水量？
示例：
输入：[0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解题思路
对于每个位置，能接的水量等于左右两边最大高度的较小值减去当前高度。
Java 代码实现
class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0) return 0;
int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int water = 0;
for (int i = 0; i < n; i++) {
water += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return water;
}
}
面试题 17.22. 单词转换
题目描述
给定字典及起始单词和结束单词，找出从起始单词到结束单词的最短转换序列，每次转换只能改变一个字母。
示例：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：["hit","hot","dot","lot","log","cog"]
解题思路
使用 BFS 找最短路径。
Java 代码实现
class Solution {
public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(endWord)) return new ArrayList<>();
Map<String, String> parent = new HashMap<>();
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
parent.put(beginWord, null);
while (!queue.isEmpty()) {
String word = queue.poll();
if (word.equals(endWord)) {
List<String> path = new ArrayList<>();
while (word != null) {
path.add(word);
word = parent.get(word);
}
Collections.reverse(path);
return path;
}
for (int i = 0; i < word.length(); i++) {
char[] chars = word.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
chars[i] = c;
String next = new String(chars);
if (dict.contains(next) && !parent.containsKey(next)) {
parent.put(next, word);
queue.offer(next);
}
}
}
}
return new ArrayList<>();
}
}
面试题 17.23. 最大黑方阵
题目描述
给定一个方阵，其中每个单元非黑即白，设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
示例：
输入:
[
[1,0,1],
[0,0,1],
[0,0,1]
]
输出: [1,0,2]
解题思路
预处理每个位置向右和向下的连续黑色像素数量，然后检查每个可能的方阵。
Java 代码实现
class Solution {
public int[] findSquare(int[][] matrix) {
int n = matrix.length;
if (n == 0) return new int[]{};
int[][] right = new int[n][n];
int[][] down = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (matrix[i][j] == 0) {
right[i][j] = (j + 1 < n ? right[i][j + 1] : 0) + 1;
down[i][j] = (i + 1 < n ? down[i + 1][j] : 0) + 1;
}
}
}
int maxSize = 0;
int[] result = new int[]{};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int size = Math.min(right[i][j], down[i][j]);
while (size > maxSize) {
if (down[i][j + size - 1] >= size && right[i + size - 1][j] >= size) {
maxSize = size;
result = new int[]{i, j, size};
break;
}
size--;
}
}
}
return result;
}
}
面试题 17.24. 最大子矩阵
题目描述
给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
示例：
输入：
[
[-1,0],
[0,-1]
]
输出：[0,1,0,1]
解题思路
将二维问题转化为一维，使用 Kadane 算法。
Java 代码实现
class Solution {
public int[] getMaxMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int maxSum = Integer.MIN_VALUE;
int[] result = new int[4];
for (int top = 0; top < m; top++) {
int[] colSum = new int[n];
for (int bottom = top; bottom < m; bottom++) {
for (int j = 0; j < n; j++) {
colSum[j] += matrix[bottom][j];
}
int sum = 0, start = 0;
for (int j = 0; j < n; j++) {
if (sum < 0) {
sum = colSum[j];
start = j;
} else {
sum += colSum[j];
}
if (sum > maxSum) {
maxSum = sum;
result = new int[]{top, start, bottom, j};
}
}
}
}
return result;
}
}
面试题 17.25. 单词矩阵
题目描述
给定一份单词列表，请找出其中最长的单词，使得该单词由单词列表中的其他单词组成。
解题思路
使用 Trie 树和回溯法构建单词矩阵。
Java 代码实现
class Solution {
public String[] maxRectangle(String[] words) {
Map<Integer, List<String>> map = new HashMap<>();
int maxLen = 0;
for (String word : words) {
int len = word.length();
map.computeIfAbsent(len, k -> new ArrayList<>()).add(word);
maxLen = Math.max(maxLen, len);
}
for (int len = maxLen; len > 0; len--) {
if (!map.containsKey(len)) continue;
List<String> list = map.get(len);
Trie trie = new Trie();
for (String word : list) {
trie.insert(word);
}
List<String> path = new ArrayList<>();
if (dfs(trie, list, len, path)) {
return path.toArray(new String[0]);
}
}
return new String[]{};
}
private boolean dfs(Trie trie, List<String> words, int len, List<String> path) {
if (path.size() == len) {
return true;
}
for (String word : words) {
path.add(word);
if (isValid(trie, path, len) && dfs(trie, words, len, path)) {
return true;
}
path.remove(path.size() - 1);
}
return false;
}
private boolean isValid(Trie trie, List<String> path, int len) {
for (int i = 0; i < len; i++) {
StringBuilder sb = new StringBuilder();
for (String word : path) {
sb.append(word.charAt(i));
}
if (!trie.startsWith(sb.toString())) {
return false;
}
}
return true;
}
class Trie {
TrieNode root = new TrieNode();
void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.isEnd = true;
}
boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (node.children[c - 'a'] == null) return false;
node = node.children[c - 'a'];
}
return true;
}
}
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd;
}
}
面试题 17.26. 稀疏相似度
题目描述
两个（具有不同单词的）文档的交集(intersection)中元素的个数除以并集(union)中元素的个数，就是这两个文档的相似度。
示例：
输入：docs = [["14","15","100","9","3"],["32","1","9","3","5"],["15","29","2","6","8","7"],["7","10"]]
输出：["0,1: 0.250","0,2: 0.100","1,2: 0.143"]
解题思路
计算每对文档的交集和并集大小，然后计算相似度。
Java 代码实现
class Solution {
public List<String> computeSimilarities(int[][] docs) {
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < docs.length; i++) {
for (int num : docs[i]) {
map.computeIfAbsent(num, k -> new ArrayList<>()).add(i);
}
}
int[][] overlap = new int[docs.length][docs.length];
for (List<Integer> list : map.values()) {
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
overlap[list.get(i)][list.get(j)]++;
}
}
}
List<String> result = new ArrayList<>();
for (int i = 0; i < docs.length; i++) {
for (int j = i + 1; j < docs.length; j++) {
if (overlap[i][j] > 0) {
double sim = (double) overlap[i][j] / (docs[i].length + docs[j].length - overlap[i][j]);
result.add(String.format("%d,%d: %.4f", i, j, sim));
}
}
}
return result;
}
}