精选文章 leetcode 338. 比特位计数

leetcode 338. 比特位计数

作者:路漫途远 时间: 2021-02-05 09:43:16
路漫途远 2021-02-05 09:43:16
【摘要】给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。 

示例 1: 
输入: 2 输出: [0,1,1] 示例 2: 
输入: 5 输出: [0,1,1,2,1,2] 进阶: 
给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗? 要求算法的空间...

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 ,计算其二进制数中的 1 的数目并将它们作为数组返回。


示例 1:

输入: 2
输出: [0,1,1]
示例 2:

输入: 5
输出: [0,1,1,2,1,2]
进阶:

给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗?
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗?要求在C++或任何其他语言中不使用任何内置函数(如 C++ 中的 __builtin_popcount)来执行此操作。


暴力法

class Solution(object): def countBits(self, num): """ :type num: int :rtype: List[int] """ def countB(num): count = 0 while num: if num & 0x1 : count += 1 num = num >> 1 return count res = [] for i in range(num+1): count = countB(i) res.append(count) return res

对每个数进行移位判断。判断一个二进制数有多少个1,只需要不断将二进制数右移并且判断其末位是否为1就行,判断其末位是否为1需要用到&运算符,任何数与1的二进制的与的结果可以得出其末位是否为1。

改进版

class Solution(object): def countBits(self, num): """ :type num: int :rtype: List[int] """ def countB(num): count = 0 while num: count += 1 num &= num-1 return count res = [] for i in range(num+1): count = countB(i) res.append(count) return res

对二进制中1的个数的判断方法我们进行了进一步的改进。考虑一个非0的二进制数10100,我们可以看到其末尾是两个0,然后一共有两个位是1。当我们对其减1时,会发现它最后一位的1变成了0,整个数变成了10011,然后进行&操作,后面都会变成0,只剩下前面的部分,10100 & 10011 = 10 000。所以最后的时间复杂度和1的位数有关,而不需要sizeof(integer)的操作次数了。

动态规划

class Solution: def countBits(self, num): dp=[0]*(num+1) for i in range(1,num+1): if(i%2==1): dp[i]=dp[i-1]+1 else: dp[i]=dp[i//2] return dp

可以根据奇偶性来判断其位为1的个数。

如果一个数是奇数,那么它的末位是1,它的1总个数是和前一个偶数有关的,比前一个偶数多一。例如3 (11),前一个偶数是2 (10),可以很直观的发现奇数就比比他小的偶数多一个1。

如果是一个偶数,那么它的末位是0,那么将它右移一位得到的数应该是和原数有一样的1的个数。所以偶数的1位个数和它除以2之后得到的数是一样的。例如 4(100)和2(10)。

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:使用spring cloud alibaba-网关(gateway)+安全认证(springsecurity+jwt)

下一篇:python 使用配置文件

您可能感兴趣

  • 利用SQL语句完成位操作

    在我们的数据库中,有些字段其值是按位表示的,即不同的位有不同的含义,比如用不同的位代表用户的不同权限或属性,该位为1时,表示用户有此权限或属性,为0则无此权限或属性等。相信有很多数据库为了效率也有类似的设计。       在C语言中提供了&, |, ~以及>>,<<等丰富的位操作符,如何通过sql语句实现对值的类似操作呢?下面给出我们常用的两个函数(其中执行&操作的函数不是吹的,比oracl...

  • 浅谈引用计数

    浅谈引用计数 前言 作为Delphi程序员,您可以不用看这节内容,但是如果您想更多的了解一些COM内部技术,或是在对象模型与引用模型之间可以进行很好的控制的话,笔者更希望你可以抽出些许时间来看这一切的内容,而益处提体的将很明显,您可以自由的用一些技巧来解决让您头疼的问题。好了,继续我们今天的交流; 在组件技术必备知识二中,我们对接口(Interface)进行了一些介绍,当我们并没有深入的对接...

  • [转]C#位运算讲解与示例 (位运算没学好,恶补ing。。。)

    在C#中可以对整型运算对象按位进行逻辑运算。按位进行逻辑运算的意义是:依次取被运算对象的每个位,进行逻辑运算,每个位的逻辑运算结果是结果值的每个位。C#支持的位逻辑运算符如表2.9所示。 运算符号 意义 运算对象类型 运算结果类型 对象数 实例 ~ 位逻辑非运算 整型,字符型 整型 1 ~a & 位逻辑与运算 2 a &...

  • as3.0位操作学习技巧

    百度百科中,取一个二进制末K位的操作是:取末k位 | (1101101->1101,k=5) | x and (1 shl k-1)其中and = &    shl = <<在ActionScript3中,取末k位的操作这样是不行的,需要重新写。那么仔细考虑一下,取末N位的操作应该如何取呢?先来看看,位操作中&(and)操作符的应用:1&0=00&0=0所以呢:001&000=000100&...

  • 密钥长度在 Internet Explorer 中显示为 0 位

    密钥长度在 Internet Explorer 中显示为 0 位 症状:         1.当您单击帮助菜单上的关于 Internet Explorer 时,密钥长度值显示为“0 位”。          2.无法连接到安全 SSL Web 站点上的 Web 页并查看这些 Web 页。原因:        如果 Schannel.dll、Rsabase.dll 或 Rsaenh.dll 文...

  • 第三次学车-侧位停车

    1、停位 右后方车框挡住前杆时,向右打方向盘两转,左方后视镜中看到前杆时,向左回方向盘两转,右后视镜和前杆成一条直线时,向左打方向盘两转,左前方车尖进入前杆里面时,向右回方向盘两转。 2、出位 车启动后向左快速打方向盘两转,右前方车尖到达前杆时,向右回方向盘两转,根据车右侧距前杆的距离,向右打方向盘1~1.5转,待车回正后回方向盘到原位。 ...

  • Windows Server 2003 Service Pack 2(32 位 x86)

    Windows Server 2003 Service Pack 2(32 位 x86) 简体中文升级包下载地址: 文件名: WindowsServer2003-KB914961-SP2-x86-CHS.exe 版本: 914961 知识库 (KB) 文章: KB914961   发布日期: 2007/3/26 语言: 简体中文 下载大小: 359.7 MB 下载:http://w...

  • java字符串各个字符计数_用任意字符集计数

    java字符串各个字符计数 本周,当我们研究一种简单而灵活的技术来对任意字符集进行计数时,这是一件很小且毫无争议的事情。 您可能不会经常需要它。 但是当您这样做时,您会发现JavaScript的内置函数都没有专门设计来处理它。 JavaScript确实具有用于在不同数字基之间解析和转换数字的内置函数。 例如, parseInt方法可以使用2到36任何基数 (数字基),通常用于数字...

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
leetcode 338. 比特位计数介绍:华为云为您免费提供leetcode 338. 比特位计数在博客、论坛、帮助中心等栏目的相关文章,同时还可以通过 站内搜索 查询更多leetcode 338. 比特位计数的相关内容。| 移动地址: leetcode 338. 比特位计数 | 写博客