Back to Leetcode

Readme

Greedy/2835.Minimum-Operations-to-Form-Subsequence-With-Target-Sum/Readme.md

latest1.7 KB
Original Source

2835.Minimum-Operations-to-Form-Subsequence-With-Target-Sum

显然我们会将nums里的元素做二进制分解,每个二进制位上会有若干个1,我们将其记录在count数组里。count[i]表示第i个bit位上我们有多少个1.

同理,我们会将target做二进制分解,每个bit位上的1表示我们需要从count里得到的“支持”。比如说,如果target上的每个需要1的二进制位i上,count[i]都大于零的话,那么意味着nums已经可以拼凑出target了。

我们从低到高逐个考虑target所需要的二进制位. 假设我们需要第i个bit位上的1,那么我们该如何考察count能否支持呢?

  1. 首先我们考虑比i低的二进制位上,count是否能够通过现有的低位上的“1”的sum来实现第i位上的1(注意,因为nums里每个元素只有一个bit 1,所以低位上1的sum必然对应着nums里某些元素的sum). 我们可以将所有低位的1都加起来,通过逐次进位的形式,看看能否传播到第i位。比如说count[0]=5,i=2, 那么我们可以对count做如下变化
step 1: count[0]=1, count[1]=2
step 2: count[0]=1, count[1]=0, count[2]=1

基本思想就是:能进位则进位。最终每个count[]上不是0就是1. 上面的例子里,count[0]=5 确实可以给target的第i位提供1的支持。

  1. 其次,如果以上方法不能实现,那么就意味着我们需要将高位上的1进行“拆解”以满足第i位上的1。显然,我们会贪心地在count里找到最接近i且count>0的位置j,将其拆解j-i次,就可以将第j位上的1传播到j-1,j-2,...i各个位上。这样我们就满足了taget在第i位上的需求。

通过以上方法,就是实现本题的最优方案。