电脑搭建网站,wordpress嵌入外部网页,xampp wordpress主题,wordpress对接公众号开发者给你两个数组 nums 和 target 。
在一次操作中#xff0c;你可以将 nums 中的任意一个元素递增 1 。
返回要使 target 中的每个元素在 nums 中 至少 存在一个倍数所需的 最少操作次数 。
示例 1#xff1a;
输入#xff1a;nums [1,2,3], target [4]
输出#xff1a…给你两个数组 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(vectorint nums, vectorint target) {int m target.size();// 一共有2^m个target的非空子集vectorlong long lcms(1 m, 1);// 计算每个非空子集的lcmfor (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(), vectorlong 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_limitslong 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变为0for (; 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] 1for i, v : range target {j : 1 ifor 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) intdfs 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 : jfor ; 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)
}如果nums的长度为mtarget的长度为n那么计算所有lcm的过程的时间复杂度为O(2 m ^m m)而dfs的过程中展开看相当于n次循环每次循环了target子集的子集次时间复杂度为O(n3 m ^m m)因此总的时间复杂度为O(n3 m ^m m)。
