当前位置: 首页 > news >正文

( 位运算 ) 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. 比特位计数 难度&#xff1a;简单 给你一个整数 n &#xff0c;对于 0 < i < n 中的每个 i &#xff0c;计算其二进制表示中 1 的个数 &#xff0c;返回一个长度为 n 1 的数组 ans 作为答案。 示例 1&#xff1a; 输入&#xff1a;n 2 输出&#xff1a;[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&#xff08;调试&#xff09;级别用于输出调试信息&#xff0c;这些信息主…...

gunicorn常用参数命令

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

TimerResolution.exe

TimerResolution.exe是一款常用的Windows实用程序,用于调整系统计时器的分辨率。它提供了一种简便的方法,让用户能够更精确地控制计时器的运行方式,从而改善系统的性能和响应时间。无论是进行游戏、音频处理还是其他需要精确计时的任务,TimerResolution.exe都能提供极大的帮…...

Qt魔法书:打造自定义鼠标键盘脚本

Qt魔法书&#xff1a;打造自定义鼠标键盘脚本 一、引言&#xff08;Introduction&#xff09;1.1 脚本的重要性&#xff08;Importance of Scripts&#xff09;1.2 Qt在脚本制作中的优势&#xff08;Advantages of Qt in Script Making&#xff09;1.3 文章目标与结构概述&…...

〖Python网络爬虫实战㉖〗- Selenium库和ChromeDriver驱动的安装

订阅&#xff1a;新手可以订阅我的其他专栏。免费阶段订阅量1000 python项目实战 Python编程基础教程系列&#xff08;零基础小白搬砖逆袭) 说明&#xff1a;本专栏持续更新中&#xff0c;目前专栏免费订阅&#xff0c;在转为付费专栏前订阅本专栏的&#xff0c;可以免费订阅付…...

U8产成品入库API接口 --参照生产订单/产品检验/不良品

//第二步&#xff1a;构造环境上下文对象&#xff0c;传入login&#xff0c;并按需设置其它上下文参数 U8EnvContext envContext new U8EnvContext(); envContext.U8Login u8Login; //第三步&#xff1a;设置API地址标识(Url) …...

gdb打印的堆栈有些函数是??()是什么

当 gdb 打印的堆栈中出现 ??() 格式的函数名时&#xff0c;通常表示对应的函数名无法被解析&#xff0c;这可能是由以下几种原因导致的&#xff1a; 缺少符号表信息&#xff1a;如果程序的可执行文件没有包含符号表信息&#xff0c;或者 gdb 没有加载符号表信息&#xff0c;就…...

【Jmeter第三章】Jmeter给请求添加请求头

给请求加上请求头最常见的场景就是在请求头上添加token了&#xff0c;这里也拿添加token来举例 1、添加某个请求的请求头 1、选中HTTP请求&#xff0c;右键添加 2、添加请求头 2、添加公共的请求头信息 其实步骤和上面是一样的&#xff0c;只不过是选择&#xff1a;线程组…...

WebApi必须知道的RestFul,Swagger,OAuth2.0

什么是RestFul RestFul是一种软件架构风格&#xff0c;它是基于HTTP协议设计的。它是一种轻量级的、简单易懂、易于维护的架构风格&#xff0c;主要用于Web服务的设计。它的设计原则是面向资源&#xff0c;每个资源都有唯一的标识符&#xff0c;客户端通过HTTP协议对这些资源进…...

【网络编程】demo版UDP网络服务器实现

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

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&#xff1a; C RAII 浅析ChatGPT 相关文章&#xff1a; 3. C 并行编程(thread) 1. 介绍 RAII 的全称是 Resource Acquisition Is Initialization&#xff0c;它是一种编程技术&#xff0c;用于管理资源的…...

AI模型部署概述

心口如一&#xff0c;犹不失为光明磊落丈夫之行也。——梁启超 文章目录 :smirk:1. AI模型部署方法:blush:2. AI模型部署框架ONNXNCNNOpenVINOTensorRTMediapipe如何选择 :satisfied:3. AI模型部署平台 &#x1f60f;1. AI模型部署方法 在AI深度学习模型的训练中&#xff0c;…...

【Rust 日报】2023-05-17 pgx -- 用于在 Rust 中开发 PostgreSQL 扩展的框架

pgx -- 用于在 Rust 中开发 PostgreSQL 扩展的框架 pgx是一个用于在 Rust 中开发 PostgreSQL 扩展的框架&#xff0c;并力求尽可能地惯用和安全。pgx 支持 Postgres v10-v14。 主要特征: 带有 cargo-pgx 的完全托管的开发环境; # 快速创建新的扩展 cargo pgx new# 安装新的&…...

二十、Zipkin持久化链路跟踪

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

大学毕业设计这样做可以吗

前言&#xff1a;相信看到这篇文章的小伙伴都或多或少有一些编程基础&#xff0c;懂得一些linux的基本命令了吧&#xff0c;本篇文章将带领大家服务器如何部署一个使用django框架开发的一个网站进行云服务器端的部署。 文章使用到的的工具 Python&#xff1a;一种编程语言&…...

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是一个单例&#xff0c;在整个程…...

Windows下通过cwRsync备份到服务器服务器之间使用rsync备份传输

Windows下通过cwRsync备份到服务器&服务器之间使用rsync备份传输 Linux服务器配置Rsync服务端1、安装Rsync2、配置rsyncd.conf3、创建目录、密码文件并修改权限4、启动rsync服务 Windows配置cwRsync客户端1、下载并解压cwRsync客户端2、打开cmd&#xff0c;执行同步命令 Wi…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...