题目链接
2859. 计算 K 置位下标对应元素的和 - 力扣(LeetCode)
解题思路
- 枚举nums的每一个下标i;
- 统计i的二进制数的1的个数;
- 累加满足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_