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

May 17, 2024 · View on GitHub

English Version

题目描述

给你一个下标从 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³¹

解法

方法一：贪心 + 位运算

观察题目中的操作，我们发现，每次操作实际上是把一个大于 $1 $的数拆分为两个相等的数，这意味着操作后数组的元素和不会发生变化。因此，如果数组的元素和$ s $小于$ target $，则无法通过题目描述的操作得到和为$ target $的子序列，直接返回$ -1 $即可。否则，我们一定可以通过拆分操作，使得数组某个子序列的元素和等于$ target$。

另外，拆分操作实际上会把二进制高位为 $1 $的数置为 \$ 0 $，并把低一位的数加上 \$ 2 $。因此，我们先用一个长度为 \$ 32 $的数组记录数组$ nums $所有元素的二进制表示中每个二进制位上 \$ 1$ 的出现次数。

接下来，从 $target$ 的低位开始遍历，对于 $target$ 的第 $i$ 位，如果当前位数字为 $0 $，则直接跳过，即$ i = i + 1 $。如果当前位数字为 \$ 1 $，我们需要在数组$ cnt $中，找到最小的数字$ j $（其中$ j \ge i $），使得$ cnt[j] \gt 0 $，然后我们将该位的数字 \$ 1 $往低位$ i $拆分，即把$ cnt[j] $减 \$ 1 $，而$ cnt[i..j-1] $的每一位置为 \$ 1 $，操作次数为$ j-i $。接下来，我们令$ j = i $，然后$ i = i + 1 $。重复上述操作，直到$ i $超出数组$ cnt$ 的下标范围，返回此时的操作次数。

注意，如果 $j \lt i$ ，实际上两个低位的 $1 $可以合并成一个高一位的 \$ 1 $。因此，如果$ j \lt i $，我们将$ \frac{cnt[j]}{2} $加到$ cnt[j+1] $中，并将$ cnt[j] $取模 \$ 2 $，然后令$ j = j + 1$，继续上述操作。

时间复杂度 $O(n \times \log M)$ ，空间复杂度 $O(\log M)$ 。其中 $n$ 是数组 $nums$ 的长度，而 $M$ 是数组 $nums$ 中的最大值。

Python3

class Solution:
    def minOperations(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s < target:
            return -1
        cnt = [0] * 32
        for x in nums:
            for i in range(32):
                if x >> i & 1:
                    cnt[i] += 1
        i = j = 0
        ans = 0
        while 1:
            while i < 32 and (target >> i & 1) == 0:
                i += 1
            if i == 32:
                break
            while j < i:
                cnt[j + 1] += cnt[j] // 2
                cnt[j] %= 2
                j += 1
            while cnt[j] == 0:
                cnt[j] = 1
                j += 1
            ans += j - i
            cnt[j] -= 1
            j = i
            i += 1
        return ans

Java

class Solution {
    public int minOperations(List<Integer> nums, int target) {
        long s = 0;
        int[] cnt = new int[32];
        for (int x : nums) {
            s += x;
            for (int i = 0; i < 32; ++i) {
                if ((x >> i & 1) == 1) {
                    ++cnt[i];
                }
            }
        }
        if (s < target) {
            return -1;
        }
        int i = 0, j = 0;
        int ans = 0;
        while (true) {
            while (i < 32 && (target >> i & 1) == 0) {
                ++i;
            }
            if (i == 32) {
                return ans;
            }
            while (j < i) {
                cnt[j + 1] += cnt[j] / 2;
                cnt[j] %= 2;
                ++j;
            }
            while (cnt[j] == 0) {
                cnt[j] = 1;
                ++j;
            }
            ans += j - i;
            --cnt[j];
            j = i;
            ++i;
        }
    }
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int target) {
        long long s = 0;
        int cnt[32]{};
        for (int x : nums) {
            s += x;
            for (int i = 0; i < 32; ++i) {
                if (x >> i & 1) {
                    ++cnt[i];
                }
            }
        }
        if (s < target) {
            return -1;
        }
        int i = 0, j = 0;
        int ans = 0;
        while (1) {
            while (i < 32 && (target >> i & 1) == 0) {
                ++i;
            }
            if (i == 32) {
                return ans;
            }
            while (j < i) {
                cnt[j + 1] += cnt[j] / 2;
                cnt[j] %= 2;
                ++j;
            }
            while (cnt[j] == 0) {
                cnt[j] = 1;
                ++j;
            }
            ans += j - i;
            --cnt[j];
            j = i;
            ++i;
        }
    }
};

Go

func minOperations(nums []int, target int) (ans int) {
	s := 0
	cnt := [32]int{}
	for _, x := range nums {
		s += x
		for i := 0; i < 32; i++ {
			if x>>i&1 > 0 {
				cnt[i]++
			}
		}
	}
	if s < target {
		return -1
	}
	var i, j int
	for {
		for i < 32 && target>>i&1 == 0 {
			i++
		}
		if i == 32 {
			return
		}
		for j < i {
			cnt[j+1] += cnt[j] >> 1
			cnt[j] %= 2
			j++
		}
		for cnt[j] == 0 {
			cnt[j] = 1
			j++
		}
		ans += j - i
		cnt[j]--
		j = i
		i++
	}
}

TypeScript

function minOperations(nums: number[], target: number): number {
    let s = 0;
    const cnt: number[] = Array(32).fill(0);
    for (const x of nums) {
        s += x;
        for (let i = 0; i < 32; ++i) {
            if ((x >> i) & 1) {
                ++cnt[i];
            }
        }
    }
    if (s < target) {
        return -1;
    }
    let [ans, i, j] = [0, 0, 0];
    while (1) {
        while (i < 32 && ((target >> i) & 1) === 0) {
            ++i;
        }
        if (i === 32) {
            return ans;
        }
        while (j < i) {
            cnt[j + 1] += cnt[j] >> 1;
            cnt[j] %= 2;
            ++j;
        }
        while (cnt[j] == 0) {
            cnt[j] = 1;
            j++;
        }
        ans += j - i;
        cnt[j]--;
        j = i;
        i++;
    }
}