python数据结构leetcode338比特位计数算法
作者：悲恋花丶无心之人 发布时间：2023-05-06 21:24:33
标签：python,数据结构,比特位计数,算法,leetcode
一、题目内容
给定一个非负整数 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)内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
二、解题思路
动态规划，i>>1指的是i右移一位，这样的话i的最低位会被去掉，因此i与i>>1相当于比较最后一位是否为1；
当 i 的最低位为0，则 i 和i >> 1中1的个数是一样的，因为0不算进计算1的个数；
否则，最低位为1，1相当于被抹掉了，因此 i >> 1中1的个数加1就是i 中1的个数；
三、代码
class Solution:
def countBits(self, num: int) -> list:
dp = [0 for _ in range(num + 1)]
for i in range(num + 1):
i_last_num = i & 1 # 得到i的末位数字
if i_last_num == 0:
dp[i] = dp[i >> 1]
else:
dp[i] = dp[i >> 1] + i_last_num
return dp
if __name__ == '__main__':
s = Solution()
num = 5
ans = s.countBits(num)
print(ans)
来源：https://nickhuang1996.blog.csdn.net/article/details/114300259
0
投稿猜你喜欢
- <style> #L { position:absolute; color:
- 批量修改： EXEC sp_MSforeachtable 'exec sp_changeob
- Google以其简洁的搜索框引领着互联网，搜索系统似乎成了每个网站必备品，甚至于是那些本身几乎是由静态页面组成的企业网站都要来个搜索功能，这
安装SDK：pip install baidu-aip如果在pycharm里也可以在setting----Project Interpret- 类：定义一件事物的抽象特点。对象：类的 实例。成员变量 − 定义在类内部的变量。该变量的值对外是不可见的，但是可以通过成
- $ cat checkserver.py#!/usr/bin/python# -*- coding: utf-8 -*- impo
- 这个弹出层的登录界面挺好看，很清爽所以转了过来给大家分享，要实现这个功能很简单：首先设计一个登录界面，使用css中的display=&quo
- 本文主要给大家介绍了关于 Python中的字符串操作和编码Unicode的一些知识，下面话不多说，需要的朋友们下面来一起学习吧。字
- centos7之Python3.74安装安装版本：Python3.74系统版本：centos7系统默认安装Python2.7，保留。安装/u
- 在《数据库原理》里面，对聚簇索引的解释是:聚簇索引的顺序就是数据的物理存储顺序，而对非聚簇索引的解释是:索引顺序与数据物理排列顺序无关。正式
- 前言今天在编码中，看到了一个非常经典的接口用法如下，于是查阅了相关资料，发现此种写法为接口型函数，本文对此做了细致的阐述。// A Gett
- 本文实例讲述了php递归删除目录与文件的方法。分享给大家供大家参考。具体实现方法如下：<?phpfunction deldir($pa
- SQL中的单记录函数 1.ASCII 返回与指定的字符对应的十进制数; SQL> select ascii('A')
- 古巴比伦王颁布了汉摩拉比法典，刻在黑色的玄武岩，距今已经三千七百多年，你在橱窗前…熟悉吧？没错，这就是周董的爱在西元前歌词。前不久工作不是很
- 前言在Python中已经内置了一个smtp邮件发送模块，Django在此基础上进行了简单地封装，让我们在Django环境中可以更方便更灵活的
- 一、激活函数1.Sigmoid函数函数图像以及表达式如下：通过该函数，可以将输入的负无穷到正无穷的输入压缩到0-1之间。在x=0的时候，输出
- 1.安装pymysql进入cmd，输入 pip install pymysql: 2.数据库建表在数据库中，建立一个简单的表，如图： 3.简
- 视图视图是一个虚拟表（非真实存在），其本质是根据SQL语句获取动态的数据集，并为其命名，用户使用时只需使用名称即可获取结果集，并可以将其当作
- 因为评论有很多人说爬取不到，我强调几点kv的格式应该是这样的：kv = {‘cookie':‘你复制的一长串cookie',
- fso对象CreateTextFile方法调用时可能会报“无效的过程调用或参数”错误，在使用ASP生成静态页面时，如果传入的字符串参数编码为
