( 位运算 ) 338. 比特位计数 ——【Leetcode每日一题】
❓338. 比特位计数
难度:简单
给你一个整数 n
,对于 0 <= i <= n
中的每个 i
,计算其二进制表示中 1
的个数 ,返回一个长度为 n + 1
的数组 ans
作为答案。
示例 1:
输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
示例 2:
输入:n = 5
输出:[0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示:
- 0 < = n < = 1 0 5 0 <= n <= 10^5 0<=n<=105
进阶:
- 很容易就能实现时间复杂度为 O ( n l o g n ) O(n log n) O(nlogn) 的解决方案,你可以在线性时间复杂度 O ( n ) O(n) O(n) 内用一趟扫描解决此问题吗?
- 你能不使用任何内置函数解决此问题吗?(如,C++ 中的
__builtin_popcount
)
💡思路:位运算
基础知识必知:一篇文章搞懂位运算 !
对于数字 6(110)
,它可以看成是 4(100)
再加一个 2(10)
,因此 dp[i] = dp[i&(i-1)] + 1
;
即,使用位运算 去除最低的那一位 1
,此时的 dp[i&(i-1)]
的已经计算过,然后再加上最低为的这个 1
。
🍁代码:(Java、C++)
Java
class Solution {public int[] countBits(int n) {int[] ans = new int[n + 1];for(int i = 1; i <= n; i++){ans[i] = ans[i & (i - 1)] + 1;}return ans;}
}
C++
class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1);for(int i = 1; i <= n; i++){ans[i] = ans[i & (i - 1)] + 1;}return ans;}
};
🚀 运行结果:
🕔 复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n),对于每个整数,只需要 O ( 1 ) O(1) O(1) 的时间计算「一比特数」。
- 空间复杂度: O ( n ) O(n) O(n),除了返回的数组以外,空间复杂度为常数。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:

( 位运算 ) 338. 比特位计数 ——【Leetcode每日一题】
❓338. 比特位计数 难度:简单 给你一个整数 n ,对于 0 < i < n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n 1 的数组 ans 作为答案。 示例 1: 输入:n 2 输出:[0,1,…...
Unity之新版输入系统InputSystem入门
一.前言 最近Unity版本全面升级到Unity2021了,着色器也全面使用URP,接下来毫无疑问,输入系统也要全面升级InputSystem,这也是Unity官方希望我们做的,毕竟现在都2023年了,我们的技术是需要跟上时代的步伐。 二.新老版本区别 老版本的InputSysten系统,其实就一个Input静…...

python 之 logging的使用
一、日志模块 import logginglogging.debug("调试日志") logging.info(消息日志) logging.warning("告警日志") logging.error(错误日志) logging.critical(严重错误日志)debug(调试)级别用于输出调试信息,这些信息主…...

gunicorn常用参数命令
Gunicorn 是一个 Python 的 WSGI HTTP 服务器。具有实现简单,轻量级,高性能等特点。更多介绍内容参考官网,这里介绍几个常用参数。 安装 pip3 install gunicorn通过输入gunicorn -v查看版本。 最简洁的启动。首先进入到项目目录,例如django项目和mana…...

TimerResolution.exe
TimerResolution.exe是一款常用的Windows实用程序,用于调整系统计时器的分辨率。它提供了一种简便的方法,让用户能够更精确地控制计时器的运行方式,从而改善系统的性能和响应时间。无论是进行游戏、音频处理还是其他需要精确计时的任务,TimerResolution.exe都能提供极大的帮…...
Qt魔法书:打造自定义鼠标键盘脚本
Qt魔法书:打造自定义鼠标键盘脚本 一、引言(Introduction)1.1 脚本的重要性(Importance of Scripts)1.2 Qt在脚本制作中的优势(Advantages of Qt in Script Making)1.3 文章目标与结构概述&…...

〖Python网络爬虫实战㉖〗- Selenium库和ChromeDriver驱动的安装
订阅:新手可以订阅我的其他专栏。免费阶段订阅量1000 python项目实战 Python编程基础教程系列(零基础小白搬砖逆袭) 说明:本专栏持续更新中,目前专栏免费订阅,在转为付费专栏前订阅本专栏的,可以免费订阅付…...
U8产成品入库API接口 --参照生产订单/产品检验/不良品
//第二步:构造环境上下文对象,传入login,并按需设置其它上下文参数 U8EnvContext envContext new U8EnvContext(); envContext.U8Login u8Login; //第三步:设置API地址标识(Url) …...
gdb打印的堆栈有些函数是??()是什么
当 gdb 打印的堆栈中出现 ??() 格式的函数名时,通常表示对应的函数名无法被解析,这可能是由以下几种原因导致的: 缺少符号表信息:如果程序的可执行文件没有包含符号表信息,或者 gdb 没有加载符号表信息,就…...

【Jmeter第三章】Jmeter给请求添加请求头
给请求加上请求头最常见的场景就是在请求头上添加token了,这里也拿添加token来举例 1、添加某个请求的请求头 1、选中HTTP请求,右键添加 2、添加请求头 2、添加公共的请求头信息 其实步骤和上面是一样的,只不过是选择:线程组…...
WebApi必须知道的RestFul,Swagger,OAuth2.0
什么是RestFul RestFul是一种软件架构风格,它是基于HTTP协议设计的。它是一种轻量级的、简单易懂、易于维护的架构风格,主要用于Web服务的设计。它的设计原则是面向资源,每个资源都有唯一的标识符,客户端通过HTTP协议对这些资源进…...

【网络编程】demo版UDP网络服务器实现
文章目录 一、引入二、服务端实现2.1 创建套接字socket2.2 绑定bind2.3 启动服务器2.4 IP的绑定2.5 读取数据recvfrom 三、用户端实现3.1 绑定问题3.2 发送数据sendto 四、源码 一、引入 在上一章【网络编程】socket套接字中我们讲述了TCP/UDP协议,这一篇就是简单实…...

C++的stack和queue
stack和queue 1.stackstack的模拟实现 2.queuequeue的模拟实现 3.容器适配器3.1. 什么是容器适配器3.2. STL标准库中stack和queue的底层结构3.3. deque的简单介绍3.3.1. deque原理介绍3.3.2. deque的缺陷3.3.3. 为什么选择deque作为stack和queue的底层默认容器 1.stack stack的…...
C++ RAII机制
C RAII机制 1. 介绍2. 示例2.1 示例一2.2 示例二 3. 使用 Reference: C RAII 浅析ChatGPT 相关文章: 3. C 并行编程(thread) 1. 介绍 RAII 的全称是 Resource Acquisition Is Initialization,它是一种编程技术,用于管理资源的…...

AI模型部署概述
心口如一,犹不失为光明磊落丈夫之行也。——梁启超 文章目录 :smirk:1. AI模型部署方法:blush:2. AI模型部署框架ONNXNCNNOpenVINOTensorRTMediapipe如何选择 :satisfied:3. AI模型部署平台 😏1. AI模型部署方法 在AI深度学习模型的训练中,…...
【Rust 日报】2023-05-17 pgx -- 用于在 Rust 中开发 PostgreSQL 扩展的框架
pgx -- 用于在 Rust 中开发 PostgreSQL 扩展的框架 pgx是一个用于在 Rust 中开发 PostgreSQL 扩展的框架,并力求尽可能地惯用和安全。pgx 支持 Postgres v10-v14。 主要特征: 带有 cargo-pgx 的完全托管的开发环境; # 快速创建新的扩展 cargo pgx new# 安装新的&…...

二十、Zipkin持久化链路跟踪
目录 Zipkin持久化 使用mysql数据库持久化 1、创建zipkin数据库 2、启动zipkin使用以下脚本 3、访问接口(配置了sleuth链路跟踪) 使用ElasticSearch持久化 zipkin启动脚本 Zipkin持久化 Zipkin server默认会将追踪数据信息保存在内存中࿰…...

大学毕业设计这样做可以吗
前言:相信看到这篇文章的小伙伴都或多或少有一些编程基础,懂得一些linux的基本命令了吧,本篇文章将带领大家服务器如何部署一个使用django框架开发的一个网站进行云服务器端的部署。 文章使用到的的工具 Python:一种编程语言&…...
NSUserDefaults
目录 1. 简介2. 基本使用2.1 步骤2.2 对应接口2.2 示例代码 3. 常用接口及属性3.1 存储3.2 获取 4. 注意点4.1 NSUserDefaults 存储的对象全是不可变的4.2 将自定义类型数据读写 NSUserDefaults4.3 非即时写入 5.参考链接 1. 简介 NSUserDefaults是一个单例,在整个程…...

Windows下通过cwRsync备份到服务器服务器之间使用rsync备份传输
Windows下通过cwRsync备份到服务器&服务器之间使用rsync备份传输 Linux服务器配置Rsync服务端1、安装Rsync2、配置rsyncd.conf3、创建目录、密码文件并修改权限4、启动rsync服务 Windows配置cwRsync客户端1、下载并解压cwRsync客户端2、打开cmd,执行同步命令 Wi…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...