2025-08-13:使数组包含目标值倍数的最少增量。用go语言，给出两
2025-08-13：使数组包含目标值倍数的最少增量。用go语言，给出两个整数数组 nums 和 target。每一步可以把 nums 中的任意一个元素加 1。问至少需要多少次这样的加法操作，才能使得对 target 中的每一个值 t，最终的 nums 中都有至少一个数能够被 t 整除（即是 t 的倍数）。
1 <= nums.length <= 5 * 10000。
1 <= target.length <= 4。
target.length <= nums.length。
1 <= nums[i], target[i] <= 10000。
输入：nums = [8,4], target = [10,5]。
输出：2。
解释：
满足题目条件的最少操作次数是 2 。
将 8 增加到 10 ，需要 2 次操作，10 是目标值 5 和 10 的倍数。
题目来自力扣3444。
步骤描述
1. 预处理所有子集的最小公倍数（LCM）
o 使用掩码表示 target 数组的子集（长度为 m，掩码范围 0 到 (1<<m)-1）。
o 初始化 lcms[0] = 1（空集的 LCM 为 1）。
o 遍历每个 target 元素 t（索引 i）：
- 对于每个已处理的掩码 mask，计算新掩码 mask | (1<<i) 的 LCM = lcm(t, lcms[mask])。
o 计算 lcm(a, b) 时，先求最大公约数（GCD），再用公式 a * b / GCD(a, b)（实际代码中为避免溢出，调整为 a / GCD(a, b) * b）。
o 时间复杂度：O(2^m * m)，由于 m <= 4，最多 16 个子集，常数时间。
2. 确定最大 LCM 阈值
o 计算 maxLcm = max(max(nums) * m, max(target))。
o 理由：任何元素最多增加 m 次（最坏情况），且目标值最大为 max(target)，超过此阈值的 LCM 无法通过增量达到，故后续可忽略。
3. 收集候选索引
o 初始化候选索引集合 candidateIndices（空集合）。
o 遍历每个非空子集掩码（从 1 到 (1<<m)-1）：
- 若当前子集的 LCM > maxLcm，跳过。
- 否则，维护一个大小为 m 的最大堆（堆顶为最大增量）：
- 遍历 nums 中每个元素 x：
- 计算增量：(lcm - x % lcm) % lcm（若 x 已是 lcm 的倍数，增量为 0）。
- 若堆未满，将 (增量, 索引) 加入堆；否则，若当前增量小于堆顶增量，替换堆顶。
- 遍历结束后，将堆中所有索引加入 candidateIndices（自动去重）。
o 时间复杂度：O(2^m * n)，其中 2^m 为子集数（最多 15），n 为 nums 长度。
4. 动态规划求解最小操作次数
o 状态定义：f[mask] 表示满足掩码 mask 对应的子集（mask 的二进制位表示 target 元素是否被满足）所需的最小操作次数。
o 初始化：
- f[0] = 0（空集无需操作）。
- 其他 f[mask] = 大数（如 math.MaxInt/2）。
o 状态转移：
- 遍历每个候选索引 i（来自 candidateIndices）：
- 从大到小遍历状态 j（从 (1<<m)-1 到 1）：
- 枚举 j 的非空子集 sub（通过 sub = (sub-1) & j 迭代）：
- 计算增量：(lcms[sub] - nums[i] % lcms[sub]) % lcms[sub]。
- 更新：f[j] = min(f[j], f[j^sub] + 增量)。
o 目标：f[(1<<m)-1]（所有 target 元素均被满足）。
o 时间复杂度：O(|C| * 2^m * 2^m)，其中 |C| 为候选索引数（最多 64），2^m 为状态数（最多 16），子集枚举最多 2^m 次（常数）。
5. 返回结果
o 输出 f[(1<<m)-1] 作为最小操作次数。
复杂度分析
o 总时间复杂度：
- 预处理 LCM：O(2^m * m) = O(16 * 4) = O(1)。
- 收集候选索引：O(2^m * n) = O(15 * n) ≈ O(n)。
- 动态规划：O(|C| * 2^{2m}) = O(64 * 256) = O(1)。
- 整体：O(n)（线性）。
o 总额外空间复杂度：
- LCM 数组：O(2^m) = O(16)。
- 候选索引集合：O(2^m * m) = O(64)。
- 堆：O(m) = O(4)。
- 动态规划数组：O(2^m) = O(16)。
- 整体：O(1)（常数空间，不依赖输入规模）。
示例说明
o 输入：nums = [8, 4], target = [10, 5]。
o 处理：
1. 子集 LCM：{}:1, {10}:10, {5}:5, {10,5}:10。
2. maxLcm = max(8*2, 10) = 16（全部保留）。
3. 候选索引：
- LCM=10：堆中索引 0（增量 2）、1（增量 6）。
- LCM=5：堆中索引 0（增量 2）、1（增量 1）→ 加入索引 0,1。
4. 动态规划：
- 初始 f[00]=0, 其他无穷大。
- 索引 0（元素 8）：
- j=11：子集 11 → f[11]=min(∞, f[00]+2)=2。
- j=10：子集 10 → f[10]=min(∞, f[00]+2)=2。
- j=01：子集 01 → f[01]=min(∞, f[00]+2)=2。
- 索引 1（元素 4）：
- j=11：子集 11 → f[11]=min(2, f[00]+6)=2（不变）。
- j=10：子集 10 → f[10]=min(2, f[00]+1)=1。
- j=01：子集 01 → f[01]=min(2, f[00]+6)=2（不变）。
- 最终 f[11]=2。
o 输出：2。
Go完整代码如下：
.
package main
import (
"container/heap"
"fmt"
"math"
"slices"
)
func minimumIncrements(nums []int, target []int)int {
m := len(target)
lcms := make([]int, 1<<m)
lcms[0] = 1
for i, t := range target {
bit := 1 << i
for mask, l := range lcms[:bit] {
lcms[bit|mask] = lcm(t, l)
}
}
maxLcm := max(slices.Max(nums)*m, slices.Max(target))
candidateIndices := map[int]struct{}{}
for _, l := range lcms[1:] {
if l > maxLcm {
continue
}
h := hp{}
for i, x := range nums {
p := pair{(l - x%l) % l, i}
iflen(h) < m {
heap.Push(&h, p)
} else {
h.update(p)
}
}
for _, p := range h {
candidateIndices[p.i] = struct{}{}
}
}
f := make([]int, 1<<m)
for j := 1; j < 1<<m; j++ {
f[j] = math.MaxInt / 2
}
for i := range candidateIndices {
x := nums[i]
for j := 1<<m - 1; j > 0; j-- {
for sub := j; sub > 0; sub = (sub - 1) & j {
l := lcms[sub]
f[j] = min(f[j], f[j^sub]+(l-x%l)%l)
}
}
}
return f[1<<m-1]
}
func gcd(a, b int)int {
for a != 0 {
a, b = b%a, a
}
return b
}
func lcm(a, b int)int { return a / gcd(a, b) * b }
type pair struct{ op, i int }
type hp []pair
func (h hp) Len() int { returnlen(h) }
func (h hp) Less(i, j int) bool { return h[i].op > h[j].op }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (hp) Pop() (_ any) { return }
func (h *hp) update(p pair) {
if p.op < (*h)[0].op {
(*h)[0] = p
heap.Fix(h, 0)
}
}
func main() {
nums := []int{8, 4}
target := []int{10, 5}
result := minimumIncrements(nums, target)
fmt.Println(result)
}
Python完整代码如下：
.
# -*-coding:utf-8-*-
import heapq
import math
from math import gcd
from typing import List
def lcm(a: int, b: int) -> int:
return a * b // gcd(a, b)
def minimum_increments(nums: List[int], target: List[int]) -> int:
m = len(target)
n = len(nums)
total_mask = 1 << m
# 计算所有子集的最小公倍数
lcms = [1] * total_mask
for i in range(m):
bit = 1 << i
for mask in range(bit):
new_mask = mask | bit
lcms[new_mask] = lcm(lcms[mask], target[i])
# 计算最大LCM用于过滤
max_lcm_val = max(max(nums) * m, max(target))
# 收集候选索引
candidate_set = set()
for mask in range(1, total_mask):
l_val = lcms[mask]
if l_val > max_lcm_val:
continue
heap = []
for idx, x in enumerate(nums):
cost = (l_val - x % l_val) % l_val
iflen(heap) < m:
heapq.heappush(heap, (-cost, idx))
else:
if cost < -heap[0][0]:
heapq.heapreplace(heap, (-cost, idx))
for neg_cost, idx in heap:
candidate_set.add(idx)
# 动态规划
f = [10**18] * total_mask
f[0] = 0
for idx in candidate_set:
x = nums[idx]
# 倒序遍历所有状态
for j in range(total_mask - 1, 0, -1):
# 枚举所有非空子集
sub = j
while sub > 0:
l_val = lcms[sub]
cost = (l_val - x % l_val) % l_val
prev_state = j ^ sub
if f[prev_state] + cost < f[j]:
f[j] = f[prev_state] + cost
sub = (sub - 1) & j
return f[total_mask - 1]
# 测试用例
if __name__ == "__main__":
nums = [8, 4]
target = [10, 5]
print(minimum_increments(nums, target)) # 输出: 3·
我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展
·