2024-07-31：用 go 语言，给定两个正整数数组 arr1 和 arr2，我们要找到属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对(x, y)中，具有最长公共前缀的长度。

公共前缀是指两个数的最左边的一位或多位数字相同的部分。例如，对于整数 5655359 和 56554 来说，它们的公共前缀是 565，而对于 1223 和 43456 来说，它们没有公共前缀。

我们需要找出所有数对(x, y)中具有最长公共前缀的长度是多少，如果没有公共前缀则返回 0。

输入：arr1 = [1,10,100], arr2 = [1000]

输出：3

解释：存在 3 个数对 (arr1[i], arr2[j]) ：

(1, 1000) 的最长公共前缀是 1 。(10, 1000) 的最长公共前缀是 10 。(100, 1000) 的最长公共前缀是 100 。

最长的公共前缀是 100 ，长度为 3 。

答案 2024-07-31：

chatgpt

题目来自 leetcode3043。

大体步骤如下：

要解决给定问题，主要分为以下大体步骤：

1. 初始化一个集合：创建一个映射（集合）has，用于存储arr1中所有整数的前缀。这个集合将用于后续查找整数是否在arr1中的某个前缀。

2. 提取前缀：遍历arr1中的每个整数，对于每个整数，计算其每个可能的前缀（即数字逐位除以 10，直到数字为 0），并将每个前缀存入has集合中。这将使得has含有arr1中所有数字的所有前缀。

3. 初始化一个最大值：设置一个变量mx，用于记录在arr2中找到的最大公共前缀。

4. 查找公共前缀：遍历arr2中的每个整数，对于每个整数，计算其每个可能的前缀（同样逐位除以 10），并在集合has中检查该前缀是否存在。如果存在，则更新mx为当前整数的前缀值，与当前存储的mx进行比较，保留较大的值。

5. 计算结果：检查mx的值，如果mx为 0，表示没有找到公共前缀，返回 0。若mx不为 0，计算其对应的长度，即将mx转为字符串并取其长度，然后返回这个长度作为结果。

6. 输出结果：通过主函数调用longestCommonPrefix函数，传递两个整数数组，然后打印返回的最长公共前缀的长度。

时间复杂度：

• 遍历数组arr1和arr2的时间复杂度是 O(n * k)，其中 n 是arr2的长度，k 是数字的位数（前缀寻找的迭代次数）。但是由于数字的位数是有限的，我们可以认为 k 是一个常数。因此主要复杂度由遍历造成，即 O(n)。

额外空间复杂度：

• 使用集合has存储前缀，每个整数的前缀数量最多为其位数，因此在最坏情况下，空间复杂度是 O(m * k)，其中 m 是arr1的长度，k 是数字的位数（符合前缀数量）。但是由于 k 是常数，所以可以简化为 O(m)。总体来说，这个算法在空间上的额外消耗是 O(m)。

Go 完整代码如下：

package main
import (  "fmt"  "strconv")
func longestCommonPrefix(arr1, arr2 []int) int {  has := map[int]bool{}  for _, v := range arr1 {    for ; v > 0; v /= 10 {      has[v] = true    }  }
  mx := 0  for _, v := range arr2 {    for ; v > 0 && !has[v]; v /= 10 {    }    mx = max(mx, v)  }  if mx == 0 {    return 0  }  return len(strconv.Itoa(mx))}
func main() {  arr1 := []int{1, 10, 100}  arr2 := []int{1000}  fmt.Println(longestCommonPrefix(arr1, arr2))}

Python 完整代码如下：

# -*-coding:utf-8-*-
def longest_common_prefix(arr1, arr2):    has = set()        # 将 arr1 中的所有数字的每个前缀加入集合    for v in arr1:        while v > 0:            has.add(v)            v //= 10        mx = 0        # 在 arr2 中找到最大的与 arr1 前缀相同的数字    for v in arr2:        while v > 0 and v not in has:            v //= 10        mx = max(mx, v)        if mx == 0:        return 0        return len(str(mx))
if __name__ == "__main__":    arr1 = [1, 10, 100]    arr2 = [1000]    print(longest_common_prefix(arr1, arr2))