【HC】比特位计数
一、338. 比特位计数1.1、题目描述http://cdn.u1.huluxia.com/g3/M03/38/FE/wKgBOV3JQvCAUSsTAADgAIHUhFA174.jpg
1.2.1、直接法： 根据191. 位1的个数（也被称为汉明重量）class Solution: def countBits(self, num: int) -> List: ans = * (num+1) for i in range(num+1): ans = self.popCount(i) return ans def popCount(self, num: int) -> int: count = 0 while num != 0: num = num & (num - 1) count += 1 return count1.2.2、根据奇偶性http://cdn.u1.huluxia.com/g3/M03/38/FE/wKgBOV3JQvGAOtUyAADQAMXD-As195.jpg
class Solution: def countBits(self, num: int) -> List: ans = * (num+1) for i in range(1, num+1): if i&1 == 0:# 偶数 ans = ans else: # 奇数 ans = ans + 1 return ans123456789101.2.3、优化： 右移+最低位(推荐)class Solution: def countBits(self, num: int) -> List: ans = * (num+1) for i in range(1, num+1): tmp = i&1 ans = ans + tmp return ans1.2.4、动态规划 + 最后设置位http://cdn.u1.huluxia.com/g3/M03/38/FE/wKgBOV3JQvGAEGzbAABMAM7o64w674.jpg
class Solution: def countBits(self, num: int) -> List: ans = * (num+1) for i in range(1, num+1): ans = ans + 1 return ans
页:
[1]