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

LeetCode刷题之HOT100之比特位计数

今天把仙剑三看完了,茂茂割肉让人无法释怀,眼泪止不住的流。长卿和紫萱的分离似乎也意味着重逢,这就是他们的宿命吧。怅然若失的感觉席卷全身,哎,做题吧。

1、题目描述

在这里插入图片描述

2、逻辑分析

题目要求将整数从0到此元素(都包括),计算每一个数二进制表示1的个数,返回数组。我想到了那个斐波拉契数,类似阶层,又有所不同,我去看看题解。官方题解给出了四种解法,其中分别是Brian Kernighan 算法与动态规划算法。下面先从第一种方法Brian Kernighan 算法开始。

Brian Kernighan 算法:从0到n,每个整数都分别计算它们的二进制中表示1的个数,再返回数组即可,而使用Brian Kernighan 算法的优点是可以在一定程度上进一步提升计算速度。Brian Kernighan算法的原理是:对于任意整数 x,令 x = x & (x−1),该运算将 x 的二进制表示的最后一个 1 变成 0。因此,对 x 重复该操作,直到 x 变成 0,则操作次数即为 x 的「二进制带有1的比特数」。

3、代码演示

public int[] countBits(int n) {// 创建一个大小为n+1的数组来存储结果int [] bits = new int[n +1];// 遍历从0到n的每个数字  for(int i = 0 ; i <= n; i++){// 计算当前数字i的二进制表示中1的个数,并将结果存储在数组中bits[i] = countOne(i);}return bits;}public int countOne(int x){int ones = 0;while(x >0){x &= (x - 1);ones++;}return ones;}

我叫GPT给我写注释,他说我的countOne函数写的不对,问题在于 x &= (x - 1); 这一行。这行代码确实会消除 x 的二进制表示中的最低位的1,但它并不适合用于计数。因为无论你执行多少次这个操作,只要 x 不为0,ones 就会一直增加,即使 x 的某些位原本就是0。应该这样写:

public int countOne(int x){  int ones = 0;  while(x > 0){  if ((x & 1) == 1) { // 检查x的最低位是否为1  ones++; // 如果是,增加计数  }  x >>= 1; // 右移一位,丢弃最低位的1  }  return ones; // 返回正确的计数结果  
}

时间复杂度:O(nlogn),空间复杂度:O(1)。

接下来一起看看动态规划的解法,我先去看看挑哪一个来写哈!官方的写的太深奥了,我发现了一个天才般的解法:

在这里插入图片描述

也就是说,可以根据奇数、偶数中二进制1的个数来解题。下面直接上代码,就像三行情诗一样美哈哈:

public int[] countBits(int n) { int [] countOne = new int[n + 1];for(int i = 1; i <= n; i++){// 当前数字i的二进制表示中1的个数等于其除以2的商(即i/2)的二进制表示中1的个数 // 加上i的最低位(即i % 2)的值(0或1)// 这是基于一个观察:一个数字的二进制表示中1的个数与其除以2的商的二进制表示中1的个数相关countOne[i] = countOne[i /2] + i % 2;}return countOne;}

时间复杂度:O(n),空间复杂度:O(1)。

ok啦,今天差不多就到这儿了,明天好好学习!BYE

相关文章:

  • PHP在线制作表白网源码
  • 电脑usb数据线共享网络给手机
  • 必应崩了?
  • 高校网络安全管理运维赛WP
  • Springboot+Vue项目-基于Java+MySQL的游戏交易系统(附源码+演示视频+LW)
  • JVM(7):虚拟机性能分析和故障解决工具之jstat工具
  • 五步定位性能瓶颈
  • 第13章 Python建模库介绍
  • 提权方式及原理汇总
  • [力扣题解] 474. 一和零
  • vue 拷贝
  • RNN-循环神经网络
  • Linux——进程信号(一)
  • Spring Security整合Gitee第三方登录
  • 智能车竞赛指南:从零到一,驶向自动驾驶的未来
  • 【RocksDB】TransactionDB源码分析
  • JS变量作用域
  • Rancher如何对接Ceph-RBD块存储
  • Xmanager 远程桌面 CentOS 7
  • 大型网站性能监测、分析与优化常见问题QA
  • 如何编写一个可升级的智能合约
  • 十年未变!安全,谁之责?(下)
  • 跳前端坑前,先看看这个!!
  • 为视图添加丝滑的水波纹
  • 吴恩达Deep Learning课程练习题参考答案——R语言版
  • 异常机制详解
  • 在electron中实现跨域请求,无需更改服务器端设置
  • Unity3D - 异步加载游戏场景与异步加载游戏资源进度条 ...
  • ​520就是要宠粉,你的心头书我买单
  • # 数据结构
  • #git 撤消对文件的更改
  • #我与Java虚拟机的故事#连载08:书读百遍其义自见
  • (16)Reactor的测试——响应式Spring的道法术器
  • (八)c52学习之旅-中断实验
  • (规划)24届春招和25届暑假实习路线准备规划
  • (蓝桥杯每日一题)love
  • (力扣)循环队列的实现与详解(C语言)
  • (太强大了) - Linux 性能监控、测试、优化工具
  • (万字长文)Spring的核心知识尽揽其中
  • (转)iOS字体
  • (转)Mysql的优化设置
  • ./configure,make,make install的作用(转)
  • .Net IOC框架入门之一 Unity
  • .net MVC中使用angularJs刷新页面数据列表
  • .Net(C#)常用转换byte转uint32、byte转float等
  • .netcore 6.0/7.0项目迁移至.netcore 8.0 注意事项
  • .NETCORE 开发登录接口MFA谷歌多因子身份验证
  • .NET单元测试
  • .NET面试题解析(11)-SQL语言基础及数据库基本原理
  • // an array of int
  • @angular/cli项目构建--Dynamic.Form
  • @Bean注解详解
  • @Import注解详解
  • [ 代码审计篇 ] 代码审计案例详解(一) SQL注入代码审计案例
  • []串口通信 零星笔记