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

剑指 Offer:003 前 n 个数字二进制中 1 的个数

题目:

给定一个非负整数 n,请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数,并输出一个数组

示例:

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

解题思路:

  1. 先把从 0 到 n 的非负整数,放到数组里
  2. 把这些非负整数都转换为二进制
  3. 判断他们当中 1 的个数
  4. 把二进制中的 0 和 1 相加,然后输出成数组
  5. 数组中数的和就是这些数当中 1 的个数

 

 

 

 

部分编程语言有相应的内置函数用于计算给定的整数的二进制表示中的 111 的数目,例如 Java\texttt{Java}Java 的 Integer.bitCount\texttt{Integer.bitCount}Integer.bitCount,C++\texttt{C++}C++ 的 __builtin_popcount\texttt{\_\_builtin\_popcount}__builtin_popcount,Go\texttt{Go}Go 的 bits.OnesCount\texttt{bits.OnesCount}bits.OnesCount 等,

方法一:Brian Kcrnighan 算法

最直观的做法是对从 0 到 n 的每个整数直接计算【一比特数】。每个 int 型的数都可以用 32 位二进制数表示,只有遍历其二进制表示的每一位即可得到 1 的数目。

利用 Brian Kcrnighan 算法,可以在一定程度上进一步提升计算速度。

Brian Kcrnighan算法的原理:

对于任意整数 x,令 x = x&(x - 1),该运算将 x 的二进制表示的最后一个 1 变成 0。因此,对 x 重复该操作,直到 x 变成 0,则操作次数即为 x 的【一比特数】

 

func onesCount(x int) (ones int) {for ; x > 0; x &= x - 1 {ones++}return
}func countBits(n int) []int {bits := make([]int, n+1)for i := range bits {bits[i] = onesCount(i)}return bits
}

 

方法二:动态规划 —— 最高有效位

func countBits(n int) []int {bits := make([]int, n+1)highBit := 0for i := 1, i <= n; i++ {if i&(i-1) == 0 {highBit = i}bits[i] = bits[i-highBit] + 1}return bits
}

 

 

 

方法三:动态规划 —— 最低有效位

 

 

func countBits(n int) []int {bits := make([]int, n+1)for i := 1; i <= n; i++ {bit[i] = bits[i>>1] + i&1}return bits
}

 

方法四:动态规划 —— 最低设置位

func countBits(n int) []int {bits := make([]int, n+1)for i := 1; i <= n; i++ {bits[i] = bits[i&(i-1)] + 1}return bits
}

 

相关文章:

剑指 Offer:003 前 n 个数字二进制中 1 的个数

题目&#xff1a; 给定一个非负整数 n&#xff0c;请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数&#xff0c;并输出一个数组 示例&#xff1a; 1、 输入: n 2 输出: [0,1,1] 解释: 0 --> 0 1 --> 1 2 --> 10 2、 输入: n 5 输出: [0,1,1,2,1,2] 解释: 0 …...

DDD系列:二、应用架构设计演变

作用: ​ 通过规定一个固定的架构设计&#xff0c;可以让团队内有一个统一的开发规范&#xff0c;降低沟通成本&#xff0c;提升效率和代码质量。 目标&#xff1a; ​ 在做架构设计时&#xff0c;一个好的架构应该需要实现以下几个目标&#xff1a; 独立于UI&#xff1a;前…...

Spring-IOC

IOC概念和原理 什么是IOC 控制反转&#xff0c;为了将系统的耦合度降低&#xff0c;把对象的创建和对象直接的调用过程权限交给Spring进行管理。 IOC底层原理 XML解析 ​ 通过Java代码解析XML配置文件或者注解得到对应的类的全路径&#xff0c;获取对应的Class类 Class clazz …...

基于Java语言开发B/S架构实现的云HIS

一、云HIS系统框架简介 1、技术框架 &#xff08;1&#xff09;总体框架&#xff1a; SaaS应用&#xff0c;全浏览器访问 前后端分离&#xff0c;多服务协同 服务可拆分&#xff0c;功能易扩展 &#xff08;2&#xff09;技术细节&#xff1a; 前端&#xff1a;AngularNg…...

清洁赛道新势力,米博凭“减法”突围?

在五四青年节这个特殊的日子&#xff0c;方太旗下的高端智能清洁品牌“米博”发布了新一代无滚布洗地机7系列。 5月4日晚&#xff0c;米博以“减法生活&#xff0c;净请7代”为主题&#xff0c;举办了新品发布会。在发布会上&#xff0c;从小红书翻红的董洁作为方太集团米博产…...

代码随想录训练营Day6| 242、349、202、1

242. 有效的字母异位词 给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意&#xff1a;若 s 和 t 中每个字符出现的次数都相同&#xff0c;则称 s 和 t 互为字母异位词。 class Solution {public boolean isAnagram(String s, String t)…...

IP-GUARD如何通过网络控制策略禁止应用程序联网?

如何通过网络控制策略禁止应用程序联网? 可以在控制台-高级-网络控制中,添加以下策略: 动作:“禁止” 应用程序:填写要禁止的程序(以QQ示例) 如何禁止没有安装客户端的电脑访问客户端电脑? 可以给所有客户端设置只允许客户端电脑访问的网络控制策略; 在控制台左边的…...

Java RSA密钥转换,从RSAPrivateKey得到RSAPublicKey

概述&#xff1a; 在Java编程中&#xff0c;我们经常用到如下一段代码来生成RSA公私钥&#xff0c;分别拿到公私钥然后加解密计算&#xff1a; KeyPairGenerator keyPairGen; keyPairGen KeyPairGenerator.getInstance("RSA"); keyPairGen.initialize(2048, new S…...

Android 12.0 Launcher3仿ios长按app图标实现抖动动画开始拖拽停止动画

1.概述 在12.0的系统rom定制化开发中,在对系统原生Launcher3的定制需求中,也有好多功能定制的,在ios等电子产品中 的一些好用的功能,也是可以被拿来借用的,所以在最近的产品开发需求中,需求要求模仿ios的 功能实现长按app图标实现抖动动画,接下来看如何分析该功能的实现…...

【五一创作】50道Java面试题

Java中的四种访问权限控制符分别是什么&#xff1f; 答&#xff1a;Java中的四种访问权限控制符分别是public、protected、default和private。 Java中的反射是什么&#xff1f;有什么作用&#xff1f; 答&#xff1a;Java中的反射是指在程序运行时动态获取类的信息和调用对象…...

4。计算机组成原理(3)指令系统

嵌入式软件开发&#xff0c;非科班专业必须掌握的基本计算机知识 核心知识点&#xff1a;数据表示和运算、存储系统、指令系统、总线系统、中央处理器、输入输出系统 指令系统&#xff08;Instruction Set&#xff09;是计算机体系结构的关键组成部分之一&#xff0c;它定义了处…...

【Elasticsearch】NLP简单应用

文章目录 NLP简介ES中的自然语言处理(NLP)NLP演示将opennlp插件放在ESplugins路径中下载NER模型配置opennlp重启ES、验证 NLP简介 NLP代表自然语言处理&#xff0c;是计算机科学和人工智能领域的一个分支。它涉及使用计算机来处理、分析和生成自然语言&#xff0c;例如英语、中…...

3. 云计算的落地实践(下)

本章讲解知识点 云计算如何落地实践ISO镜像文件创建虚拟机入门创建数据节点配置VMWare创建虚拟机三种网络模式1. 云计算的落地实践 上一章我们讲了云计算的业界实践,即:搭建IaaS后,用于创建虚拟机,在虚拟机上部署PaaS,用于管理同时部署在虚拟机上的容器,这就是业界普遍的…...

javaEE+mysql学生竞赛管理系统

本系统是基于JAVA平台开发的一套学生竞赛信息管理的系统。系统采用JSP为编程语言。数据库采用Mysql建立数据之间的转换。论文主要介绍了本课题的开发背景&#xff0c;所要完成的功能和开发的过程。重点的说明了系统设计的重点、设计思想、难点技术和解决方案。 本课题的目的是使…...

车辆出险记录查询API接口

车辆出险记录接口可以帮助车主、保险公司、交通管理部门等各方快速查询车辆的出险记录&#xff0c;了解车辆风险情况、核算保险费用等。这篇文章将探讨车辆出险记录接口的作用、应用场景、使用方式以及一些注意事项。 作用&#xff1a; 车辆出险记录接口主要解决了快速获取车…...

MySQL的概念,编译及安装

一.数据库的基本概念 1、数据&#xff08;Data&#xff09; • 描述事物的符号记录 • 包括数字&#xff0c;文字&#xff0c;图形&#xff0c;图像&#xff0c;声音&#xff0c;档案记录等 • 以“记录”形式按统一的格式进行存储 2、表 • 将不同的记录组织在一起 • …...

系统性能压力测试

系统性能压力测试 一、压力测试 压力测试是给软件不断加压&#xff0c;强制其在极限的情况下运行&#xff0c;观察它可以运行到何种程度&#xff0c;从而发现性能缺陷&#xff0c;是通过搭建与实际环境相似的测试环境&#xff0c;通过测试程序在同一时间内或某一段时间内&…...

从零开始学习Linux运维,成为IT领域翘楚(三)

文章目录 &#x1f525;Linux超级用户与伪用户&#x1f525;Linux文件基本属性&#x1f525;Linux权限字与权限操作 &#x1f525;Linux超级用户与伪用户 Linux下用户分为三类&#xff1a;超级用户、普通用户、伪用户 ⭐ 超级用户&#xff1a;用户名为root&#xff0c;具有一切…...

轻松搭建自己的ChatGPT聊天机器人,让AI陪你聊天!

随着人工智能技术的发展&#xff0c;聊天机器人已经成为了我们生活中的一部分。无论是在客服机器人上还是智能助手上&#xff0c;聊天机器人都能够给我们带来真正的便利和快乐。现在&#xff0c;你也可以轻松搭建自己的ChatGPT聊天机器人&#xff0c;和它天马行空地聊天&#x…...

CompletableFutrue异步处理

异步处理 一、线程的实现方式 1. 线程的实现方式 1.1 继承Thread class ThreadDemo01 extends Thread{Overridepublic void run() {System.out.println("当前线程:" Thread.currentThread().getName());} }1.2 实现Runnable接口 class ThreadDemo02 implements …...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...