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))