当前位置：首页 > article >正文

LeetCode 3444.使数组包含目标值倍数的最小增量

article 2025/2/11 2:11:32

给你两个数组 nums 和 target 。

在一次操作中，你可以将 nums 中的任意一个元素递增 1 。

返回要使 target 中的每个元素在 nums 中至少存在一个倍数所需的最少操作次数。

示例 1：

输入：nums = [1,2,3], target = [4]

输出：1

解释：

满足题目条件的最少操作次数是 1 。

将 3 增加到 4 ，需要 1 次操作，4 是目标值 4 的倍数。
示例 2：

输入：nums = [8,4], target = [10,5]

输出：2

解释：

满足题目条件的最少操作次数是 2 。

将 8 增加到 10 ，需要 2 次操作，10 是目标值 5 和 10 的倍数。
示例 3：

输入：nums = [7,9,10], target = [7]

输出：0

解释：

数组中已经包含目标值 7 的一个倍数，不需要执行任何额外操作。

提示：

1 <= nums.length <= 5 * 10^4
1 <= target.length <= 4
target.length <= nums.length
1 <= nums[i], target[i] <= 10^4

题目想要让target中每个数都能在nums中找到一个倍数，比如target中有两个数3、5，那么需要nums中有一个数是3、5的最小公倍数的倍数，即15的倍数，如果target中的数是5、10，那么需要nums中有一个数是10的倍数，因此我们可以先计算出target中所有非空子集的最小公倍数，然后用暴力法dp，我们可以遍历nums中的所有数字，当前数字可以进行增加操作，也可以不进行增加操作，如果不对当前数字进行增加操作，就相当于nums中少了一个数字，问题变成了规模更小的同样问题；如果对当前数字进行增加操作，就找到target的每个非空子集使当前数字的增量，然后从target中去掉对应的非空子集，从num中去掉当前数字，问题又变成了规模更小的同样问题。

C++解法：

class Solution {
public:
    int minimumIncrements(vector<int>& nums, vector<int>& target) {
        int m = target.size();
        // 一共有2^m个target的非空子集
        vector<long long> lcms(1 << m, 1);
        // 计算每个非空子集的lcm
        for (int i = 0; i < m; ++i) {
            int curBit = 1 << i;
            for (int j = 0; j < curBit; ++j) {
                lcms[j | curBit] = lcm(target[i], lcms[j]);
            }
        }

        // tmp保存中间结果，防止dfs溢出
        vector tmp(nums.size(), vector<long long>(1 << m, -1));
        // i是当前遍历到的nums数组位置，倒序遍历
        // j是target的子集，j的第n位的二进制为1表示第n个数字在集合中
        auto dfs = [&](this auto &&dfs, int i, int j) -> long long {
            // 如果没有子集了，返回0，表示不再需要增量
            if (j == 0) {
                return 0;
            }
            // 如果nums遍历完了，但还有target子集，则此次dfs作废，返回一个大数即可
            if (i < 0) {
                // 除2防止溢出
                return numeric_limits<long long>::max() / 2;
            }

            // res是引用
            long long &res = tmp[i][j];
            if (res != -1) {
                return res;
            }
            
            // 不修改当前遍历到的数字
            res = dfs(i - 1, j);
            int jBak = j;
            // 每次jBak & (j - 1)，可以让j的二进制位中最右边的1变为0
            for (; j; j = jBak & (j - 1)) {
                // 选中每个子集，并修改当前数字，然后删去选中的数字和当前数字，继续dfs
                // jBak ^ j相当于二进制差集
                // (lcms[j] - nums[i] % lcms[j]) % lcms[j]作用是找出
                // nums[i]变为lcms[j]的倍数所需要的增量
                res = min(res, 
                  dfs(i - 1, jBak ^ j) + (lcms[j] - nums[i] % lcms[j]) % lcms[j]); 
            }
            return res;
        };

        return dfs(nums.size() - 1, (1 << m) - 1);
    }
};

go解法：

func minimumIncrements(nums []int, target []int) int {
    n := len(nums)
    m := len(target)
    lcms := make([]int, 1 << m)
    lcms[0] = 1
    for i, v := range target {
        j := 1 << i
        for k := 0; k < j; k++ {
            lcms[k | j] = lcm(v, lcms[k])
        } 
    }

    tmp := make([][]int, n)
    for i := range tmp {
        tmp[i] = make([]int, 1 << m)
        for j := range tmp[i] {
            tmp[i][j] = -1
        }
    }

    var dfs func(int, int) int
    dfs = func(i, j int) (res int) {
        if (j == 0) {
            return 0
        }
        if (i < 0) {
            return math.MaxInt / 2
        }

        p := &tmp[i][j]
        if (*p != -1) {
            return *p
        }
        defer func() { *p = res }()

        res = dfs(i - 1, j)
        jBak := j
        for ; j != 0; j = (j - 1) & jBak {
            res = min(res, dfs(i - 1, j ^ jBak) + (lcms[j] - nums[i] % lcms[j]) % lcms[j])
        }
        return res
    }

    return dfs(n - 1, (1 << m) - 1)
}

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

func lcm(a, b int) int {
    return a * b / gcd(a, b)
}