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

剑指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;}

搞定

http://www.lryc.cn/news/505408.html

相关文章:

  • 多音轨视频使用FFmpeg删除不要音轨方法
  • elasticsearch 使用enrich processor填充数据
  • VMProtect:软件保护与安全的全面解决方案
  • Web 毕设篇-适合小白、初级入门练手的 Spring Boot Web 毕业设计项目:教室信息管理系统(前后端源码 + 数据库 sql 脚本)
  • 第十二篇:linux下socket本地套接字通讯
  • Spring Boot 2.1.7 数据源自动加载过程详解
  • 【Vue.js 3.0】provide 、inject 函数详解
  • JVM(Java虚拟机)的虚拟机栈
  • Elasticsearch02-安装7.x
  • iPhone恢复技巧:如何从 iPhone 恢复丢失的照片
  • vba批量化调整word的图和图表标题
  • 【Flutter_Web】Flutter编译Web第二篇(webview篇):flutter_inappwebview如何改造方法,变成web之后数据如何交互
  • 【C语言的奥秘11】指针知识点总结(续)
  • excel 列名是数据表 的字段名 ,单元格的值 是数据表对应字段的值,生成sql插入语句
  • AI Agent与MEME:技术与文化融合驱动Web3创新
  • IO的入门
  • 构建一个rust生产应用读书笔记四(实战1)
  • SpringCloudAlibaba | Sentinel从基础到进阶
  • 算法刷题Day18: BM41 输出二叉树的右视图
  • 【信息系统项目管理师-论文真题】2015下半年论文详解(包括解题思路和写作要点)
  • Windows如何安装go环境,离线安装beego
  • JavaScript网络请求( XMLHttpRequest 对象,进度事件, 跨源资源共享)
  • 计算机网络信息系统安全问题及解决策略
  • 解决并发情况下调用 Instruct-pix2pix 模型推理错误:index out of bounds 问题
  • 你了解TCP/IP参考模型吗
  • 高斯混合模型及最大期望算法(EM)聚类
  • 批处理命令的语法与功能
  • 33. Three.js案例-创建带阴影的球体与平面
  • Three.js材质纹理扩散过渡
  • 免费开源!推荐一款网页版数据库管理工具!