LeetCode 338. 比特位计数
给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1:
输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
提示:
0 <= n <= 105
进阶:
很容易就能实现时间复杂度为 O(n log n) 的解决方案,你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗?
你能不使用任何内置函数解决此问题吗?(如,C++ 中的 __builtin_popcount )
解法一:动态规划,如3的比特位为1的位数等于将3右移一位(即1)的比特位为1的位数加上3&1:
class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);for (int i = 1; i <= n; ++i) {ans[i] = ans[i >> 1] + (i & 1);} return ans;}
};
此算法时间复杂度为O(n),空间复杂度为O(1)。
解法二:每个数字都计算一遍位数:
class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);for (int i = 1; i <= n; ++i) {int ibak = i;while (ibak) {ans[i] += ibak & 1;ibak >>= 1;}} return ans;}
};
此算法时间复杂度为O(nlgn),空间复杂度为O(1)。
解法三:使用库函数:
class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);for (int i = 1; i <= n; ++i) {ans[i] = __builtin_popcount(i);} return ans;}
};
此算法时间复杂度为O(nlgn),空间复杂度为O(1)。__builtin_popcount函数的时间复杂度为O(lgn)。
解法四:利用x&(x-1)的结果是x的最低的比特位从1变成0:
class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);for (int i = 1; i <= n; ++i) {int ibak = i;while (ibak) {ibak = ibak & (ibak - 1);ans[i] += 1;}} return ans;}
};
此算法时间复杂度为O(nlgn),空间复杂度为O(1)。
解法五:动态规划,最高位一定为1,x的比特位为1的计数等于去掉最高位后的数字的比特位为1的计数加上最高位的1:
class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);int highestBit = 0;for (int i = 1; i <= n; ++i) {// 当i是2的幂时,更新最高位if ((i & (i - 1)) == 0) {highestBit = i;}ans[i] = ans[i - highestBit] + 1;} return ans;}
};
此算法时间复杂度为O(n),空间复杂度为O(1)。
解法六:动态规划,x的比特位为1的计数等于把x的最低位的1改为0后的数的比特位为1的计数加上最低位的1:
class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);for (int i = 1; i <= n; ++i) {ans[i] = ans[i & (i - 1)] + 1;} return ans;}
};
此算法时间复杂度为O(n),空间复杂度为O(1)。
相关文章:
LeetCode 338. 比特位计数
给你一个整数 n ,对于 0 < i < n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n 1 的数组 ans 作为答案。 示例 1: 输入:n 2 输出:[0,1,1] 解释: 0 --> 0 1 --> …...
排序评估指标——NDCG和MAP
在搜索和推荐任务中,系统常返回一个item列表。如何衡量这个返回的列表是否优秀呢? 例如,当我们检索【推荐排序】,网页返回了与推荐排序相关的链接列表。列表可能会是[A,B,C,G,D,E,F],也可能是[C,F,A,E,D],现在问题来了…...
[Android Studio] Android Studio Virtual Device(AVD)虚拟机的功能试用
🟧🟨🟩🟦🟪 Android Debug🟧🟨🟩🟦🟪 Topic 发布安卓学习过程中遇到问题解决过程,希望我的解决方案可以对小伙伴们有帮助。 🚀write…...
kafka-3-kafka应用的核心要点和内外网访问
kafka实战教程(python操作kafka),kafka配置文件详解 Kafka内外网访问的设置 1 kafka简介 根据官网的介绍,ApacheKafka是一个分布式流媒体平台,它主要有3种功能: (1)发布和订阅消息流,这个功能类似于消息队列&#x…...
VS2017+OpenCV4.5.5 决策树-评估是否发放贷款
决策树是一种非参数的监督学习方法,主要用于分类和回归。 决策树结构 决策树在逻辑上以树的形式存在,包含根节点、内部结点和叶节点。 根节点:包含数据集中的所有数据的集合内部节点:每个内部节点为一个判断条件,并且…...
Prometheus 记录规则和警报规则
前提环境: Docker环境 涉及参考文档: Prometheus 录制规则Prometheus 警报规则 语法检查规则 promtool check rules /path/to/example.rules.yml一:录制规则语法 groups 语法: groups:[ - <rule_group> ]rule_group…...
(API)接口测试的关键技术
接口测试也就是API测试,从名字上可以知道是面向接口的测试活动。所以在讲API测试之前,我们应该说清楚接口是什么,那么接口就是有特定输入和特定输出的一套逻辑处理单元,而对于接口调用方来说,不用知道自身的内部实现逻…...
快速排序算法原理 Quicksort —— 图解(精讲) JAVA
快速排序是 Java 中 sort 函数主要的排序方法,所以今天要对快速排序法这种重要算法的详细原理进行分析。 思路:首先快速排序之所以高效一部分原因是利用了离散数学中的传递性。 例如 1 < 2 且 2 < 3 所以可以推出 1 < 3。在快速排序的过程中巧…...
linux环境搭建私有gitlab仓库
搭建之前,需要安装相应的依赖包,并且要启动sshd服务(1).安装policycoreutils-python openssh-server openssh-clients [rootVM-0-2-centos ~]# sudo yum install -y curl policycoreutils-python openssh-server openssh-clients [rootVM-0-2-centos ~]…...
SpringSecurity授权
文章目录工具类使用自定义失败处理代码配置跨域其他权限授权hasAnyAuthority自定义权限校验方法基于配置的权限控制工具类 import javax.servlet.http.HttpServletResponse; import java.io.IOException;public class WebUtils {/*** 将字符串渲染到客户端** param response 渲…...
学习 Python 之 Pygame 开发坦克大战(一)
学习 Python 之 Pygame 开发坦克大战(一)Pygame什么是Pygame?初识pygame1. 使用pygame创建窗口2. 设置窗口背景颜色3. 获取窗口中的事件4. 在窗口中展示图片(1). pygame中的直角坐标系(2). 展示图片(3). 给部分区域设置颜色5. 在窗口中显示文字6. 播放音…...
2.5|iot冯|方元-嵌入式linux系统开发入门|2.13+2.18
一、 Linux 指令操作题(共5题(共 20 分,每小题 4分)与系统工作、系统状态、工作目录、文件、目录、打包压缩与搜索等主题相关。1.文件1.1文件属性1.2文件类型属性字段的第1个字符表示文件类型,后9个字符中,…...
一起Talk Android吧(第四百九十六回:自定义View实例二:环形进度条)
文章目录 知识回顾实现思路实现方法示例代码各位看官们大家好,上一回中咱们说的例子是"如何使用Java版MQTT客户端",这一回中咱们说的例子是"自定义View实例二:环形进度条"。闲话休提,言归正转,让我们一起Talk Android吧! 知识回顾 看官们,我们又回…...
上传图片尺寸校验
使用方法 ● Image ● URL ● onload代码: async validImageSize(file, imgWidth, imgHeight) {const img new Image()img.src URL.createObjectURL(file)const { w, h } await new Promise((resolve, reject) > {img.onload () > {const { width: w, he…...
【Python】缺失值处理和拉格朗日插值法(含源代码实现)
目录:缺失值处理和拉格朗日插值法一、前言二、理论知识三、代码实现一、前言 对于含有缺失值的数据集,如果通过删除小部分记录达到既定的目标,那么删除含有缺失值的记录的方法是最有效的。然而,这种方法也有很多问题,…...
SpringCloudAlibaba-Sentinel
一、介绍官网:https://github.com/alibaba/Sentinel/下载jar包,启动,访问http://localhost:8080/创建module添加如下依赖<!--SpringCloud ailibaba sentinel --><dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring…...
【程序化天空盒】过程记录02:云扰动 边缘光 消散效果
写在前面 写在前面唉,最近筋疲力竭,课题组的东西一堆没做,才刚刚开始带着思考准备练习作品,从去年5月份开始到现在真得学了快一年了,转行学其他的真的好累,,不过还是加油! 下面是做…...
链表OJ(三) 反转链表合集
目录 反转链表 反转链表 II 链表中的节点每k个一组翻转 描述 给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。 数据范围: 0≤n≤10000≤…...
SQLSERVER2019安装步骤过程
第一步官网下载SQLSERVER软件包 目前官网只能下载最新版本2022版本。 通过迅雷下载网址 SQL Server 2019 Enterprise (x64) - DVD (Chinese-Simplified)企业版 ed2k://|file|cn_sql_server_2019_enterprise_x64_dvd_2bfe815a.iso|1632086016|58C258FF0F1D006DD3C1F5F17AF3E…...
Java模块化概述
3 模块化 3.1 模块化概述 Java语言随着这些年的发展已经成为了一]影响深远的编程语言,无数平台,系统都采用Java语言编写。但是,伴随着发展,Java也越来越庞大,逐渐发展成为-门“臃肿” 的语言。而且,无论是运行个大型的…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
