leetcode2859-计算K置位下标对应元素的和

题目链接

2859. 计算 K 置位下标对应元素的和 - 力扣（LeetCode）

解题思路

1. 枚举nums的每一个下标i；
2. 统计i的二进制数的1的个数；
3. 累加满足bit_count(i) == k的nums[i];

难点，如何统计二进制中1的个数？

例题

2859. 计算 K 置位下标对应元素的和 - 力扣（LeetCode）

位运算

我们可以通过位运算：

• 通过&i：获取最低位的值；
• 通过>>i：每次右移一位来更新最低位

这样的复杂度为O（C），C为数字的数据类型的位数。

位运算优化

我们可以用 n = n & (n - 1)代替n = n >> 1进行n的更新。这样做的好处是什么？

可以看到每一次 n = n & (n - 1)都会把当前n的最低为1一处掉，直到最后所有1都被消除，n变成0。

这样的时间复杂度为O（K），K为数字中的1的个数。

class Solution:
    def hammingWeight(self, n: int) -> int:
        c = 0
        while n != 0:
            n &= (n-1)
            c += 1
        return  c
        

综上

解题代码

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        #统计位1的个数
        def bit_count(num:int) -> int:
            c = 0
            while num > 0:
                num &= num - 1
                c += 1
            return  c
        sum_ = 0
        #枚举每一个下标，如果下标位置等于k,累计对应的数值
        for i,num in enumerate(nums):
            if bit_count(i) == k:
                sum_ += num
        return sum_