剑指 Offer:003 前 n 个数字二进制中 1 的个数
题目:
给定一个非负整数 n,请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数,并输出一个数组
示例:
1、
输入: n = 2 输出: [0,1,1] 解释: 0 --> 0 1 --> 1 2 --> 102、
输入: n = 5 输出:[0,1,1,2,1,2]解释: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101
解题思路:
- 先把从 0 到 n 的非负整数,放到数组里
- 把这些非负整数都转换为二进制
- 判断他们当中 1 的个数
- 把二进制中的 0 和 1 相加,然后输出成数组
- 数组中数的和就是这些数当中 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 的个数
题目: 给定一个非负整数 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 …...
DDD系列:二、应用架构设计演变
作用: 通过规定一个固定的架构设计,可以让团队内有一个统一的开发规范,降低沟通成本,提升效率和代码质量。 目标: 在做架构设计时,一个好的架构应该需要实现以下几个目标: 独立于UI:前…...
Spring-IOC
IOC概念和原理 什么是IOC 控制反转,为了将系统的耦合度降低,把对象的创建和对象直接的调用过程权限交给Spring进行管理。 IOC底层原理 XML解析 通过Java代码解析XML配置文件或者注解得到对应的类的全路径,获取对应的Class类 Class clazz …...
基于Java语言开发B/S架构实现的云HIS
一、云HIS系统框架简介 1、技术框架 (1)总体框架: SaaS应用,全浏览器访问 前后端分离,多服务协同 服务可拆分,功能易扩展 (2)技术细节: 前端:AngularNg…...
清洁赛道新势力,米博凭“减法”突围?
在五四青年节这个特殊的日子,方太旗下的高端智能清洁品牌“米博”发布了新一代无滚布洗地机7系列。 5月4日晚,米博以“减法生活,净请7代”为主题,举办了新品发布会。在发布会上,从小红书翻红的董洁作为方太集团米博产…...
代码随想录训练营Day6| 242、349、202、1
242. 有效的字母异位词 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。 class Solution {public boolean isAnagram(String s, String t)…...
IP-GUARD如何通过网络控制策略禁止应用程序联网?
如何通过网络控制策略禁止应用程序联网? 可以在控制台-高级-网络控制中,添加以下策略: 动作:“禁止” 应用程序:填写要禁止的程序(以QQ示例) 如何禁止没有安装客户端的电脑访问客户端电脑? 可以给所有客户端设置只允许客户端电脑访问的网络控制策略; 在控制台左边的…...
Java RSA密钥转换,从RSAPrivateKey得到RSAPublicKey
概述: 在Java编程中,我们经常用到如下一段代码来生成RSA公私钥,分别拿到公私钥然后加解密计算: 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中的四种访问权限控制符分别是什么? 答:Java中的四种访问权限控制符分别是public、protected、default和private。 Java中的反射是什么?有什么作用? 答:Java中的反射是指在程序运行时动态获取类的信息和调用对象…...
4。计算机组成原理(3)指令系统
嵌入式软件开发,非科班专业必须掌握的基本计算机知识 核心知识点:数据表示和运算、存储系统、指令系统、总线系统、中央处理器、输入输出系统 指令系统(Instruction Set)是计算机体系结构的关键组成部分之一,它定义了处…...
【Elasticsearch】NLP简单应用
文章目录 NLP简介ES中的自然语言处理(NLP)NLP演示将opennlp插件放在ESplugins路径中下载NER模型配置opennlp重启ES、验证 NLP简介 NLP代表自然语言处理,是计算机科学和人工智能领域的一个分支。它涉及使用计算机来处理、分析和生成自然语言,例如英语、中…...
3. 云计算的落地实践(下)
本章讲解知识点 云计算如何落地实践ISO镜像文件创建虚拟机入门创建数据节点配置VMWare创建虚拟机三种网络模式1. 云计算的落地实践 上一章我们讲了云计算的业界实践,即:搭建IaaS后,用于创建虚拟机,在虚拟机上部署PaaS,用于管理同时部署在虚拟机上的容器,这就是业界普遍的…...
javaEE+mysql学生竞赛管理系统
本系统是基于JAVA平台开发的一套学生竞赛信息管理的系统。系统采用JSP为编程语言。数据库采用Mysql建立数据之间的转换。论文主要介绍了本课题的开发背景,所要完成的功能和开发的过程。重点的说明了系统设计的重点、设计思想、难点技术和解决方案。 本课题的目的是使…...
车辆出险记录查询API接口
车辆出险记录接口可以帮助车主、保险公司、交通管理部门等各方快速查询车辆的出险记录,了解车辆风险情况、核算保险费用等。这篇文章将探讨车辆出险记录接口的作用、应用场景、使用方式以及一些注意事项。 作用: 车辆出险记录接口主要解决了快速获取车…...
MySQL的概念,编译及安装
一.数据库的基本概念 1、数据(Data) • 描述事物的符号记录 • 包括数字,文字,图形,图像,声音,档案记录等 • 以“记录”形式按统一的格式进行存储 2、表 • 将不同的记录组织在一起 • …...
系统性能压力测试
系统性能压力测试 一、压力测试 压力测试是给软件不断加压,强制其在极限的情况下运行,观察它可以运行到何种程度,从而发现性能缺陷,是通过搭建与实际环境相似的测试环境,通过测试程序在同一时间内或某一段时间内&…...
从零开始学习Linux运维,成为IT领域翘楚(三)
文章目录 🔥Linux超级用户与伪用户🔥Linux文件基本属性🔥Linux权限字与权限操作 🔥Linux超级用户与伪用户 Linux下用户分为三类:超级用户、普通用户、伪用户 ⭐ 超级用户:用户名为root,具有一切…...
轻松搭建自己的ChatGPT聊天机器人,让AI陪你聊天!
随着人工智能技术的发展,聊天机器人已经成为了我们生活中的一部分。无论是在客服机器人上还是智能助手上,聊天机器人都能够给我们带来真正的便利和快乐。现在,你也可以轻松搭建自己的ChatGPT聊天机器人,和它天马行空地聊天&#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 …...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
