当前位置:网站首页>算法---比特位计数(Kotlin)
算法---比特位计数(Kotlin)
2022-07-07 02:27:00 【小米科技Android 研发曹新雨】
题目
比特位计数
给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1:
输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
示例 2:
输入:n = 5
输出:[0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示:
0 <= n <= 105
https://leetcode.cn/problems/counting-bits/
解决思路
2的n次幂 一定是只有一个1
因为都是10000
每当超过一个2的n次幂
我们就可以把超过的部分
从之前的数组里面找出结果
比如超过2,那么当前的结果其实就是1 + int[2]
解决方法
fun countBits(n: Int): IntArray {
val intArray = IntArray(n + 1)
var highBit = 0
for (i in 1..n) {
if ((i and (i - 1)) == 0) {
intArray[i] = 1
highBit = i
} else {
intArray[i] = intArray[i - highBit] + 1
}
}
return intArray
}
总结
1.怎么判断一个数是2的n次幂?
x&(x-1) = 0 就说明是2的n次幂
边栏推荐
猜你喜欢
PostgreSQL database timescaledb function time_ bucket_ Gapfill() error resolution and license replacement
How can I check the DOI number of a foreign document?
请问如何查一篇外文文献的DOI号?
力扣62 不同路径(从矩阵左上到右下的所有路径数量) (动态规划)
Implementation of VGA protocol based on FPGA
Navicat导入15G数据报错 【2013 - Lost connection to MySQL server during query】 【1153:Got a packet bigger】
Shared memory for interprocess communication
Force deduction 62 different paths (the number of all paths from the upper left to the lower right of the matrix) (dynamic planning)
String (explanation)
快速定量,Abbkine 蛋白质定量试剂盒BCA法来了!
随机推荐
Matlab / envi principal component analysis implementation and result analysis
二十岁的我4面拿到字节跳动offer,至今不敢相信
使用TCP/IP四层模型进行网络传输的基本流程
Performance comparison between Ceres solver and g2o
学习笔记|数据小白使用DataEase制作数据大屏
【OpenCV】形态学滤波(2):开运算、形态学梯度、顶帽、黑帽
FlexRay通信协议概述
【解决】Final app status- UNDEFINED, exitCode- 16
Which foreign language periodicals are famous in geology?
VIM mapping large K
LM small programmable controller software (based on CoDeSys) Note 23: conversion of relative coordinates of servo motor operation (stepping motor) to absolute coordinates
How to install swoole under window
c语言(结构体)定义一个User结构体,含以下字段:
Pinduoduo lost the lawsuit: "bargain for free" infringed the right to know but did not constitute fraud, and was sentenced to pay 400 yuan
Ha Qu projection dark horse posture, only half a year to break through the 1000 yuan projector market!
2022Android面试必备知识点,一文全面总结
Networkx绘图和常用库函数坐标绘图
JESD204B时钟网络
Google Chrome browser released patch 103.0.5060.114 to fix the 0-day vulnerability
一条慢SQL拖死整个系统