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

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 &#xff0c;对于 0 < i < n 中的每个 i &#xff0c;计算其二进制表示中 1 的个数 &#xff0c;返回一个长度为 n 1 的数组 ans 作为答案。 示例 1&#xff1a; 输入&#xff1a;n 2 输出&#xff1a;[0,1,1] 解释&#xff1a; 0 --> 0 1 --> …...

排序评估指标——NDCG和MAP

在搜索和推荐任务中&#xff0c;系统常返回一个item列表。如何衡量这个返回的列表是否优秀呢&#xff1f; 例如&#xff0c;当我们检索【推荐排序】&#xff0c;网页返回了与推荐排序相关的链接列表。列表可能会是[A,B,C,G,D,E,F],也可能是[C,F,A,E,D]&#xff0c;现在问题来了…...

[Android Studio] Android Studio Virtual Device(AVD)虚拟机的功能试用

&#x1f7e7;&#x1f7e8;&#x1f7e9;&#x1f7e6;&#x1f7ea; Android Debug&#x1f7e7;&#x1f7e8;&#x1f7e9;&#x1f7e6;&#x1f7ea; Topic 发布安卓学习过程中遇到问题解决过程&#xff0c;希望我的解决方案可以对小伙伴们有帮助。 &#x1f680;write…...

kafka-3-kafka应用的核心要点和内外网访问

kafka实战教程(python操作kafka)&#xff0c;kafka配置文件详解 Kafka内外网访问的设置 1 kafka简介 根据官网的介绍&#xff0c;ApacheKafka是一个分布式流媒体平台&#xff0c;它主要有3种功能&#xff1a; (1)发布和订阅消息流&#xff0c;这个功能类似于消息队列&#x…...

VS2017+OpenCV4.5.5 决策树-评估是否发放贷款

决策树是一种非参数的监督学习方法&#xff0c;主要用于分类和回归。 决策树结构 决策树在逻辑上以树的形式存在&#xff0c;包含根节点、内部结点和叶节点。 根节点&#xff1a;包含数据集中的所有数据的集合内部节点&#xff1a;每个内部节点为一个判断条件&#xff0c;并且…...

Prometheus 记录规则和警报规则

前提环境&#xff1a; Docker环境 涉及参考文档&#xff1a; Prometheus 录制规则Prometheus 警报规则 语法检查规则 promtool check rules /path/to/example.rules.yml一&#xff1a;录制规则语法 groups 语法&#xff1a; groups:[ - <rule_group> ]rule_group…...

(API)接口测试的关键技术

接口测试也就是API测试&#xff0c;从名字上可以知道是面向接口的测试活动。所以在讲API测试之前&#xff0c;我们应该说清楚接口是什么&#xff0c;那么接口就是有特定输入和特定输出的一套逻辑处理单元&#xff0c;而对于接口调用方来说&#xff0c;不用知道自身的内部实现逻…...

快速排序算法原理 Quicksort —— 图解(精讲) JAVA

快速排序是 Java 中 sort 函数主要的排序方法&#xff0c;所以今天要对快速排序法这种重要算法的详细原理进行分析。 思路&#xff1a;首先快速排序之所以高效一部分原因是利用了离散数学中的传递性。 例如 1 < 2 且 2 < 3 所以可以推出 1 < 3。在快速排序的过程中巧…...

linux环境搭建私有gitlab仓库

搭建之前&#xff0c;需要安装相应的依赖包&#xff0c;并且要启动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 开发坦克大战&#xff08;一&#xff09;Pygame什么是Pygame?初识pygame1. 使用pygame创建窗口2. 设置窗口背景颜色3. 获取窗口中的事件4. 在窗口中展示图片(1). pygame中的直角坐标系(2). 展示图片(3). 给部分区域设置颜色5. 在窗口中显示文字6. 播放音…...

2.5|iot冯|方元-嵌入式linux系统开发入门|2.13+2.18

一、 Linux 指令操作题&#xff08;共5题&#xff08;共 20 分&#xff0c;每小题 4分&#xff09;与系统工作、系统状态、工作目录、文件、目录、打包压缩与搜索等主题相关。1.文件1.1文件属性1.2文件类型属性字段的第1个字符表示文件类型&#xff0c;后9个字符中&#xff0c;…...

一起Talk Android吧(第四百九十六回:自定义View实例二:环形进度条)

文章目录 知识回顾实现思路实现方法示例代码各位看官们大家好,上一回中咱们说的例子是"如何使用Java版MQTT客户端",这一回中咱们说的例子是"自定义View实例二:环形进度条"。闲话休提,言归正转,让我们一起Talk Android吧! 知识回顾 看官们,我们又回…...

上传图片尺寸校验

使用方法 ● Image ● URL ● onload代码&#xff1a; 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】缺失值处理和拉格朗日插值法(含源代码实现)

目录&#xff1a;缺失值处理和拉格朗日插值法一、前言二、理论知识三、代码实现一、前言 对于含有缺失值的数据集&#xff0c;如果通过删除小部分记录达到既定的目标&#xff0c;那么删除含有缺失值的记录的方法是最有效的。然而&#xff0c;这种方法也有很多问题&#xff0c;…...

SpringCloudAlibaba-Sentinel

一、介绍官网&#xff1a;https://github.com/alibaba/Sentinel/下载jar包,启动,访问http://localhost:8080/创建module添加如下依赖<!--SpringCloud ailibaba sentinel --><dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring…...

【程序化天空盒】过程记录02:云扰动 边缘光 消散效果

写在前面 写在前面唉&#xff0c;最近筋疲力竭&#xff0c;课题组的东西一堆没做&#xff0c;才刚刚开始带着思考准备练习作品&#xff0c;从去年5月份开始到现在真得学了快一年了&#xff0c;转行学其他的真的好累&#xff0c;&#xff0c;不过还是加油&#xff01; 下面是做…...

链表OJ(三) 反转链表合集

目录 反转链表 反转链表 II 链表中的节点每k个一组翻转 描述 给定一个单链表的头结点pHead(该头节点是有值的&#xff0c;比如在下图&#xff0c;它的val是1)&#xff0c;长度为n&#xff0c;反转该链表后&#xff0c;返回新链表的表头。 数据范围&#xff1a; 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语言随着这些年的发展已经成为了一]影响深远的编程语言&#xff0c;无数平台,系统都采用Java语言编写。但是&#xff0c;伴随着发展&#xff0c;Java也越来越庞大&#xff0c;逐渐发展成为-门“臃肿” 的语言。而且&#xff0c;无论是运行个大型的…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

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

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

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...