怎么查看网站点击量,太原网站优化培训,建设部中国建造师网查询,如何免费弄一个网站Leetcode 3444. Minimum Increments for Target Multiples in an Array 1. 解题思路2. 代码实现 题目链接#xff1a;3444. Minimum Increments for Target Multiples in an Array
1. 解题思路
这一题我的思路上就是一个深度优先遍历#xff0c;考察target数组当中的每一个…Leetcode 3444. Minimum Increments for Target Multiples in an Array 1. 解题思路2. 代码实现 题目链接3444. Minimum Increments for Target Multiples in an Array
1. 解题思路
这一题我的思路上就是一个深度优先遍历考察target数组当中的每一个元素的全部倍数被出现的情况下最少需要多少次操作以及同时能够满足多少剩余的target数组中的数字然后持续迭代考察取其中的最小值。
同时考虑到时间复杂度的因素我们将结果用一个全局变量存下来一旦某一步的结果超过了已知可行的最大操作数就直接退出递归从而进行剪枝。
2. 代码实现
给出最终的python代码实现如下
class Solution:def minimumIncrements(self, nums: List[int], target: List[int]) - int:nums, target sorted(nums), sorted(target, reverseTrue)n, m len(nums), len(target)status [0 for _ in range(m)]ans math.infdef dfs(idx, nums, status):nonlocal ansif idx m:return 0elif status[idx] 1:return dfs(idx1, nums, status)need math.inftgt 0while tgt nums[-1]:tgt target[idx]old_status deepcopy(status)for i, x in enumerate(target):if status[i] 1 or tgt % x 0:status[i] 1i bisect.bisect_right(nums, tgt)if i 0:num nums.pop(i-1)if abs(num-tgt) ans:need min(need, abs(num-tgt) dfs(idx1, nums, status))nums.insert(i-1, num)status old_statusif need ans:return math.infif idx 0:ans needreturn needdfs(0, nums, status)return ans 提交代码评测得到耗时12ms占用内存21.3MB。
