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完整代码如下：
代码语言：javascript复制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{
return0
}
returnlen(strconv.Itoa(mx))
}
func main(){
arr1 :=[]int{1,10,100}
arr2 :=[]int{1000}
fmt.Println(longestCommonPrefix(arr1, arr2))
}
Python完整代码如下：
代码语言：javascript复制# -*-coding:utf-8-*-
deflongest_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 >0and v notin has:
v //=10
mx =max(mx, v)
if mx ==0:
return0
returnlen(str(mx))
if __name__ =="__main__":
arr1 =[1,10,100]
arr2 =[1000]
print(longest_common_prefix(arr1, arr2))
