使子序列的和等于目标的最少操作次数

难度: Hard

给你一个下标从 0 开始的数组 nums ，它包含非负整数，且全部为 2 的幂，同时给你一个整数 target 。

一次操作中，你必须对数组做以下修改：

选择数组中一个元素 nums[i] ，满足 nums[i] > 1 。
将 nums[i] 从数组中删除。
在 nums 的末尾添加两个数，值都为 nums[i] / 2 。

你的目标是让 nums 的一个 子序列 的元素和等于 target ，请你返回达成这一目标的 最少操作次数 。如果无法得到这样的子序列，请你返回 -1 。

数组中一个 子序列 是通过删除原数组中一些元素，并且不改变剩余元素顺序得到的剩余数组。

示例 1：

输入：nums = [1,2,8], target = 7
输出：1
解释：第一次操作中，我们选择元素 nums[2] 。数组变为 nums = [1,2,4,4] 。
这时候，nums 包含子序列 [1,2,4] ，和为 7 。
无法通过更少的操作得到和为 7 的子序列。

示例 2：

输入：nums = [1,32,1,2], target = 12
输出：2
解释：第一次操作中，我们选择元素 nums[1] 。数组变为 nums = [1,1,2,16,16] 。
第二次操作中，我们选择元素 nums[3] 。数组变为 nums = [1,1,2,16,8,8] 。
这时候，nums 包含子序列 [1,1,2,8] ，和为 12 。
无法通过更少的操作得到和为 12 的子序列。

示例 3：

输入：nums = [1,32,1], target = 35
输出：-1
解释：无法得到和为 35 的子序列。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 2³⁰
nums 只包含非负整数，且均为 2 的幂。
1 <= target < 2³¹

Submission

运行时间: 31 ms

内存: 16.1 MB

class Solution:
    def minOperations(self, nums: List[int], target: int) -> int:
        if sum(nums) < target:
            return -1
        cnt = Counter(nums)
        i = acc = res = 0
        while 1 << i <= target:
            acc += cnt[1 << i] * (1 << i)
            if target & 1 << i:
                if acc >= 1 << i:
                    acc -= 1 << i
                    i += 1
                    continue
                j = i + 1
                while cnt[1 << j] == 0: j += 1
                cnt[1 << j] -= 1
                for k in range(i + 1, j):
                    cnt[1 << k] += 1
                res += j - i
            i += 1
        return res

Explain

这道题目要求找到最少的操作次数，使得数组的一个子序列的和等于给定的target。首先，若nums数组中所有元素的和小于target，则直接返回-1，因为无论如何都无法达到target。接下来使用计数器cnt来统计nums中每个元素的出现次数。这里采用贪心的策略来尽量使用大的数。通过位运算来判断target的每个位是否需要当前的2的幂次元素。若需要而当前累积的和（acc）不足以提供该位的元素，则必须从更高位的元素中分裂出所需的更小元素，同时计数操作数。这个过程使用了两个循环：外层循环遍历可能的位数，内层循环处理分裂操作，直到找到可用的更大元素。最后，返回执行的总操作次数。

时间复杂度: O(30) 或 O(log(target))

空间复杂度: O(1)

class Solution:
    def minOperations(self, nums: List[int], target: int) -> int:
        if sum(nums) < target:
            return -1  # 如果nums的和小于目标，直接返回-1
        cnt = Counter(nums)  # 使用Counter来计数nums中各元素的出现次数
        i = acc = res = 0
        while 1 << i <= target:  # 对于每个2的幂次方
            acc += cnt[1 << i] * (1 << i)  # 累计当前幂次方元素的总和
            if target & 1 << i:  # 如果target的当前位是1
                if acc >= 1 << i:
                    acc -= 1 << i  # 如果当前累积和足够，则减去所需量
                    i += 1
                    continue
                j = i + 1
                while cnt[1 << j] == 0: j += 1  # 找到下一个可用的更大元素
                cnt[1 << j] -= 1
                for k in range(i + 1, j):
                    cnt[1 << k] += 1  # 分裂元素，进行操作计数
                res += j - i  # 增加操作次数
            i += 1
        return res

Explore

使用大数的贪心策略是基于一个简单的观察：较大的数可以通过分裂变为多个较小的数，而较小的数不能组合为一个较大的数，所以尽早使用较大的数可以直接达到目标和的较高位，从而减少需要的操作次数。这种策略通常有效，但并不总是能保证最少的操作次数。在某些特定情况下，可能存在通过不同的分裂顺序或组合，使用较小数值资源达到更优的操作次数的情况。但在大多数情况下，使用较大的数能够有效减少操作次数。

算法通过从最大可用元素开始分裂到所需的较小元素，以确保每次分裂都能尽可能多地解决紧迫的需求（即当前位的需求）。这种方法通常有效，但不一定总是最优的。确实存在特定的情况，分裂顺序的不同可能导致更少的操作次数。例如，在某些情况下，多次小范围的分裂可能比一次大范围的分裂导致较少的总操作次数。

外层循环遍历所有可能的2的幂次元素，直到超过目标值`target`。选择`1 << i <= target`作为循环结束条件是因为，一旦2的幂次超过`target`，那么这个幂次的元素不可能对达到`target`有贡献。因此，以此为终止条件可以有效缩减不必要的计算和检查，专注于可能对满足目标值有直接贡献的元素。

内层循环中跳过cnt[1 << j]为0的元素，是因为这些元素在当前数组中不存在，因此不能用于当前的分裂操作。这种跳过方法并不会忽略潜在的最优解，因为无论如何，不存在的元素是无法参与到当前操作中的。此策略确保我们只关注实际可用的元素，从而在实际情况下达到最快解决问题的目的。