剑指Offer 03比特位计数
只是记录
题目链接
题目链接
自己想出来的 第一种解法
思路简述
遍历[0,n]之间的数字,对于每一个数字按照二进制的方式展开,判断最低位置是否为1,若为1则+1,反之不加,直到该数字等于0就停止。
public static int[] countBits(int n) {int[] res = new int[n+1];res[0] = 0;for(int i=1;i<=n;i++){int t = i;int sum = 0;while (t>0){sum = sum + (t&1);t/=2;}res[i]=sum;}return res;}
时间复杂度:O(NlogN)
空间复杂度:O(N)
解法二 动态规划
我是没有想到的哈,我想到的是题目既然说有一种时间复杂度为O(N)的解法
我当时想到的是找数字和他们二进制数中含1的个数之间的规律。但冥思苦想了好久,实在想不出来,看别人的讲解
下面的推导过程
十进制 二进制 二进制中含1的个数
000 − > 000 − > 0 000->000->0 000−>000−>0
001 − > 001 − > 1 001->001->1 001−>001−>1
002 − > 010 − > 1 002->010->1 002−>010−>1
003 − > 0011 − > 2 003->0011->2 003−>0011−>2
004 − > 0100 − > 1 004->0100->1 004−>0100−>1
005 − > 0101 − > 2 005->0101->2 005−>0101−>2
006 − > 0110 − > 2 006->0110->2 006−>0110−>2
007 − > 0111 − > 3 007->0111->3 007−>0111−>3
008 − > 1000 − > 1 008->1000->1 008−>1000−>1
既然是偶数,那么一定可以将2左移一定次数后得到该偶数。我们假设左移1位的数字是n,不做任何操作的数字是n/2, 那么dp[n] = dp [n/2],
例如6和3,他们中的二进制数含1的个数是一样的
偶数解决了,奇数怎么办?奇数可以看成偶数+1,又因为偶数是dp[n]=dp[n/2],所以奇数直接就是dp[n]=dp[n/2]+1

好,递推公式搞定,接下来初始化问题,当n为0的时候,那么结果就是0,所以你不用初始化也可以
public static int[] countBits(int n) {int[] res = new int[n+1];res[0] = 0;for(int i=1;i<=n;i++){if(i % 2 == 0)res[i] = res[i/2];elseres[i] = res[i/2] + 1;}return res;}
搞定
相关文章:
剑指Offer 03比特位计数
只是记录 题目链接 题目链接 自己想出来的 第一种解法 思路简述 遍历[0,n]之间的数字,对于每一个数字按照二进制的方式展开,判断最低位置是否为1,若为1则1,反之不加,直到该数字等于0就停止。 public static int[] …...
多音轨视频使用FFmpeg删除不要音轨方法
近期给孩子找宫崎骏动画,但是有很多是多音轨视频但是默认的都是日语,电视上看没办法所以只能下载后删除音轨文件只保留中文。 方法分两步,先安装FFmpeg在转文件即可。 第一步FFmpeg安装 FFmpeg是一个开源项目,包含了处理视频的…...
elasticsearch 使用enrich processor填充数据
文章目录 使用 POST 请求手动插入用户数据1. 创建 Enrich Policy步骤 1.1: 创建 Enrich Policy步骤 1.2: 执行 Enrich Policy 2. 创建 Ingest Pipeline步骤 2.1: 创建 Ingest Pipeline步骤 2.2: 配置 Enrich Processor 参数 3. 使用 Ingest Pipeline步骤 3.1: 使用 Pipeline 进…...
VMProtect:软件保护与安全的全面解决方案
在当今数字化时代,软件的安全性和保密性愈发重要。VMProtect 作为一款备受瞩目的软件保护工具,因其强大的功能和广泛的应用而成为开发者保护软件的首选方案。 VMProtect 是一款新一代的软件保护实用程序,支持多个编译器平台,包括…...
Web 毕设篇-适合小白、初级入门练手的 Spring Boot Web 毕业设计项目:教室信息管理系统(前后端源码 + 数据库 sql 脚本)
🔥博客主页: 【小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍ 1.0 项目介绍 开发工具:IDEA、VScode 服务器:Tomcat, JDK 17 项目构建:maven 数据库:mysql 8.0 系统用户前台和管理…...
第十二篇:linux下socket本地套接字通讯
使用套接字除了可以实现网络间不同主机间的通信外,还可以实现同一主机的不同进程间的通信,且建立的通信是双向的通信。socket进程通信与网络通信使用的是统一套接口,只是地址结构与某些参数不同。 用途 进程间通信:本地套…...
Spring Boot 2.1.7 数据源自动加载过程详解
在 Spring Boot 中,数据源的自动配置是框架中一个关键功能,本文将以 Spring Boot 2.1.7 版本为例,详细讲解在单数据源情况下数据源是如何自动加载的。我们通过源码分析,追踪整个加载流程。 1. 自动配置类的发现 Spring Boot 使用…...
【Vue.js 3.0】provide 、inject 函数详解
在 Vue 3 中,provide 和 inject 是用于跨组件层次结构进行依赖注入的一对 API。这些 API 主要用于祖先组件和后代组件之间的数据传递,尤其是当这些组件之间没有直接的父子关系时。 1. 示例 1.1 provide provide 函数用于在祖先组件中定义一个值&#…...
JVM(Java虚拟机)的虚拟机栈
JVM(Java虚拟机)的虚拟机栈是Java程序运行时的重要组件,以下是对其的详细解析: 一、概念与功能 概念:虚拟机栈也称为Java栈,是JVM为每个线程分配的一个私有的内存区域。每个线程在创建时都会创建一个虚拟…...
Elasticsearch02-安装7.x
零、文章目录 Elasticsearch02-安装7.x 1、Windows安装Elasticsearch (1)JDK安装 Elasticsearch是基于java开发的,所以需要安装JDK。我们安装的Elasticsearch版本是7.15,对应JDK至少1.8版本以上。也可以不安装jdk,…...
iPhone恢复技巧:如何从 iPhone 恢复丢失的照片
在计算机时代,我们依靠手机来捕捉和存储珍贵的回忆。但是,如果您不小心删除或丢失了手机上的照片怎么办?这真的很令人沮丧和烦恼,不是吗?好吧,如果您在 iPhone 上丢失了照片,您不必担心…...
vba批量化调整word的图和图表标题
vba代码 将图片进行居中操作 Sub ChangePictureFormate()Dim oPara As ParagraphDim oRange As RangeDim i As LongDim beforeIsPicture As BooleanbeforesIsPicture False 确保文档中至少有图片If ActiveDocument.InlineShapes.Count 0 ThenMsgBox "没有找到图片。&qu…...
【Flutter_Web】Flutter编译Web第二篇(webview篇):flutter_inappwebview如何改造方法,变成web之后数据如何交互
前言 欢迎来到第二篇文章,这也是第二个难题,就是原有的移动端本身一些页面H5的形式去呈现(webview),例如某些需要动态更换内容的页面,某些活动页面、支付页面,不仅仅做页面呈现,还包…...
【C语言的奥秘11】指针知识点总结(续)
目录 一、指针的运算 1、指针与整数相加减 2、指针-指针(地址-地址) 3、指针的关系运算 六、指针和数组 七、二级指针 八、指针数组 一、指针的运算 1、指针与整数相加减 看一下下面的代码: #include<stdio.h> int my_strlen(c…...
excel 列名是数据表 的字段名 ,单元格的值 是数据表对应字段的值,生成sql插入语句
在 Excel 中,按 Alt F11 打开 VBA 编辑器。在菜单栏选择 插入 -> 模块,在新模块中粘贴以下代码。 VBA 代码 Sub GenerateSQLInsertStatementsToFile()Dim ws As WorksheetDim lastRow As Long, lastCol As Long, i As Long, j As LongDim sql As S…...
AI Agent与MEME:技术与文化融合驱动Web3创新
AI Agent如何引领Web3新时代? 随着Web3与区块链技术的迅速发展,AI Agent作为人工智能与区块链的交汇点,正在逐步成为推动去中心化生态的重要力量。同时,MEME文化凭借其强大的社区驱动力和文化渗透力,在链上生态中扮演着…...
IO的入门
目录 1.IO概述1.1流的分类 2.字符流2.1 案例 1.IO概述 IO(Input/Output):输入和输出,指的是某个设备或环境进行数据的输入或者输出。例如:键盘的输入,再比如显示器就是输出设备,输出图像。 对于java来说输…...
构建一个rust生产应用读书笔记四(实战1)
我们需要从访客那里收集哪些信息,以便将其登记为电子邮件通讯的订阅者? 电子邮件地址:这是最基本的要求,因为我们需要通过电子邮件地址向订阅者发送内容。姓名:虽然这不是强制性的,但我们希望收集一个名字…...
SpringCloudAlibaba | Sentinel从基础到进阶
一、Sentinel简介 Sentinel是SpringCloudAlibaba的一个组件,主要用于解决微服务架构中的高可用性和稳定性问题(雪崩问题)。 常见的使用场景有: 流量控制舱壁模式(线程隔离)超时处理熔断降级 二、流量控…...
算法刷题Day18: BM41 输出二叉树的右视图
题目链接 描述 思路: 递归构造二叉树在Day15有讲到。复习一下,就是使用递归构建左右子树。将中序和前序一分为二。 接下来是找出每一层的最右边的节点,可以利用队列层次遍历。 利用队列长度记录当前层有多少个节点,每次从队列里…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
