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
投稿猜你喜欢
1.什么是Pillow首先我们需要了解一下PIL（Python Imaging Library）,它是Python2中非常强大的图像处理标准- 前言为了了解跟python数据分析有关行业的信息，大概地了解一下对这个行业的要求以及薪资状况，我决定从网上获取信息并进行分析。既然想要分析就
- 代码如下:<％ dim objconn,connstr Set objconn =&
- 大部分面向对象的编程语言（除了C++）都只支持单继承，而不支持多继承，为什么呢？因为多继承不仅增加编程复杂度，而且容易导致莫名其妙的错误。P
- 在某些情况下，比如自动补全（auto complete）的输入框中，需要使用keyup事件来监听键盘的输入以迅速作出回应。关键在于keyup
- 一、功能简述番茄钟即番茄工作法，番茄工作法是简单易行的时间管理工具，使用番茄工作法即一个番茄时间共30分钟，25分钟工作,5分钟休息；特点一
- DQN算法是DeepMind团队提出的一种深度强化学习算法，在许多电动游戏中达到人类玩家甚至超越人类玩家的水准，本文就带领大家了解一下这个算
- 最近小编思维发散“Visual Studio可以集成chatgpt吗？”，这样不就可以让chatgp
- Python的import包含文件功能就跟PHP的include类似，但更确切的说应该更像是PHP中的require，因为Python里的i
- 我和朋友对此的看法有分歧，我明明记得有不需要返回的时候的？你的看法是对的，例如在表中删除记录。我们来看看下面的例子——在Employee表中
- 本文实例讲述了Python队列RabbitMQ 使用方法。分享给大家供大家参考，具体如下：目前的exchange的路由策略是：每个需要队列的
- 在日常工作中，Python在办公自动化领域应用非常广泛，如批量将多个Excel中的数据进行计算并生成图表，批量将多个Excel按固定格式转换
- asp采集常用的几个FUCTION如:利用流保存文件,利用fso检测文件是否存在,利用fso检测文件夹是否存在,保存文件,取得远程数据等1.
- 我们的目标是秒杀淘宝或京东等的订单，这里面有几个关键点，首先需要登录淘宝或京东，其次你需要准备好订单，最后要在指定时间快速提交订单。这里就要
- 在你的 Django 应用中，你或许希望根据某字段的值对检索结果排序，比如说，按字母顺序。 那么，使用 order_by() 这个方法就可以
- 在网上查了部分资料但是发现粘上去的代码都存在问题，无奈只好自己修改了一下，代码如下： 如下代码能正常运行，都是网上查找资料最后拼凑总结出来的
- 前言Vue 原本有一个官方推荐的 ajax 插件 vue-resource，但是自从 Vue 更新到 2.0 之后，官方就不再更新 vue-
- 首先要注意 vue3中 v-model 默认绑定的变量名变了，从原理的 value 改成了 modelValue，如果要改变变量的值，要执行
- 前言昨天把自己的VASP文件处理库进行了打包并上传到PyPI，现在可以直接通过pip和easy_install来安装VASPy啦（同时欢迎使
- 1、用apt-get安装mysql#更新一下apt 仓库sudo apt-get update#安装mysql-servicesudo ap
