要在数组中选择一些数字，使得这些数字的乘积末尾的零尽可能多，并且不能选相邻的数字，我们可以通过以下步骤来实现：
理解问题：一个数字末尾有多少个零，取决于它的因子中有多少对 2 和 5。因为每一对 2 和 5 可以组成一个 10，所以我们需要计算我们所选择的数字中 2 和 5 的数量。
动态规划：我们可以使用动态规划来解决这个问题。创建两个状态数组，
dp_2[i]和dp_5[i]分别表示到第 i 个元素为止可以获得的最多的 2 的个数和 5 的个数。迭代选取：对于每个元素，如果选择它，则不能选择它前面的元素（即
i-1），而可以选择i-2或者更早的位置。计算最终结果：最后，对于每个位置，我们比较不选择该元素和选择该元素所能获得的最大末尾零数量。
下面是用 Go 实现这个算法的一种方式：
package main
import (
"fmt"
)
// Function to count the number of factors of a given number
func countFactors(n, factor int) int {
count := 0
for n > 0 && n%factor == 0 {
n /= factor
count++
}
return count
}
// Function to find the maximum number of trailing zeros in the product
func maxTrailingZeros(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
dp2 := make([]int, n)
dp5 := make([]int, n)
for i := range nums {
factorsOf2 := countFactors(nums[i], 2)
factorsOf5 := countFactors(nums[i], 5)
if i == 0 {
dp2[i] = factorsOf2
dp5[i] = factorsOf5
} else if i == 1 {
dp2[i] = max(dp2[i-1], factorsOf2)
dp5[i] = max(dp5[i-1], factorsOf5)
} else {
dp2[i] = max(dp2[i-1], dp2[i-2]+factorsOf2)
dp5[i] = max(dp5[i-1], dp5[i-2]+factorsOf5)
}
}
return min(dp2[n-1], dp5[n-1])
}
// Utility function to get maximum of two integers
func max(a, b int) int {
if a > b {
return a
}
return b
}
// Utility function to get minimum of two integers
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
nums := []int{10, 20, 15, 30} // Example input array
result := maxTrailingZeros(nums)
fmt.Println("Maximum trailing zeros:", result)
}
解题思路总结：
- 利用动态规划记录可选数字中因子的数量。
- 遍历整个数组，考虑是否选择当前元素并更新状态。
- 最后返回最小的因子数作为结果，代表乘积末尾零的数量。
你可以根据需要调整输入数组以测试不同场景！
内容由零声教学AI助手提供，问题来源于学员提问
![make[5]: Entering directory `/home/onvif/gsoap_2.8.116/gsoap-2.8/gsoap/wsdl'
g++ -DWSDL2H_IMPORT_PATH=](https://linuxcpp.0voice.com/zb_users/upload/2023/05/202305162234068218239.png)
![0 ? data :[{}]":scrol1l="{x:'max-content'}
:pagination="{
pageSize: pageSize,
showSizeChanger: true,
onShowSiz...](https://linuxcpp.0voice.com/zb_users/upload/2023/05/202305162214216277121.png)
![make[5]: Entering directory `/home/onvif/gsoap_2.8.116/gsoap-2.8/gsoap/wsdl'
g++ -I/usr/lib64/include -DWITH_OPENSSL -DWITH_GZIP -DWSDL2H_IMPORT_PATH=](https://linuxcpp.0voice.com/zb_users/upload/2023/05/202305162217459776743.png)
