3043. 最长公共前缀的长度 - 力扣（LeetCode）
3043. 最长公共前缀的长度 - 给你两个 正整数 数组 arr1 和 arr2 。 正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。 设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 和 5655，而 1223 和 43456 没有 公共前缀。 你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y...
思路
先遍历arr1存储所有前缀，然后遍历arr2找出与arr1的共同前缀的最大值，返回最大值的长度。
本来想用int[]存储前缀的，结果内存超过限制了。
代码
class Solution {
public int longestCommonPrefix(int[] arr1, int[] arr2) {
// 存储前缀
// int[] hash = new int[100000001];
HashSet<Integer> hashSet = new HashSet<>();
// 记录 arr1 出现的所有前缀
for (int num : arr1) {
while (num > 0) {
// hash[num]++;
hashSet.add(num);
num /= 10;
}
}
// 找出 arr2 与 arr1 的共同前缀中的最大值
int max = 0;
for (int num : arr2) {
while (num > 0) {
// if (hash[num] > 0) {
if (hashSet.contains(num)) {
max = Math.max(max, num);
break;
}
num /= 10;
}
}
return max == 0 ? 0 : String.valueOf(max).length();
}
}
2 个帖子 - 2 位参与者
来源: LinuxDo 最新话题查看原文