当前位置:网站首页>[算法] 剑指offer2 golang 面试题3:前n个数字二进制形式中1的个数
[算法] 剑指offer2 golang 面试题3:前n个数字二进制形式中1的个数
2022-07-06 09:18:00 【邓嘉文Jarvan】
[算法] 剑指offer2 golang 面试题3:前n个数字二进制形式中1的个数
题目1:
给定一个非负整数 n ,请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数,并输出一个数组。
示例 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
func countBits(n int) []int {
}
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/w3tCBm
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路1:
思路1: 暴力计算每一个数字的每一位1的个数,时间复杂度 O(n*17),10^5 < ^17
代码
func countBits(n int) []int {
//思路1: 暴力计算每一个数字的每一位1的个数,时间复杂度 O(n*17),10^5 < ^17
//参数处理
if n == 0 {
return []int{
0}
}
res := make([]int,n+1)
for i:=0;i <=n;i++{
count := 0
for j:=0;j<17;j ++{
if i & (1 << j) != 0 {
count ++
}
}
res[i] = count
}
return res
}
测试
思路2:
// 要点: i&(i-1)就是比i中1少一个的数字
// 我们可以通过之前求到的i中1的个数来求,时间复杂度是 O(n)
代码2
func countBits(n int) []int {
// 要点: i&(i-1)就是比i中1少一个的数字
// 我们可以通过之前求到的i中1的个数来求,时间复杂度是 O(n)
if n == 0 {
return []int{
0}
}
res := make([]int,n+1)
res[0] = 0
for i:=1;i <=n;i++{
res[i] = res[i&(i-1)] + 1
}
return res
}
测试2
边栏推荐
- Teach you to release a DeNO module hand in hand
- Compile GDAL source code with nmake (win10, vs2022)
- MySQL replacement field part content
- Get the position of the nth occurrence of the string
- (1) Introduction Guide to R language - the first step of data analysis
- Fabrication d'un sac à dos simple fairygui
- SVN更新后不出现红色感叹号
- Excel导入,导出功能实现
- [offer9] implement queues with two stacks
- [Clickhouse kernel principle graphic explanation] about the collaborative work of partitioning, indexing, marking and compressed data
猜你喜欢
PR 2021 quick start tutorial, first understanding the Premiere Pro working interface
Mysql database reports an error: row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT=DY
FGUI工程打包发布&导入Unity&将UI显示出来的方式
First use of dosbox
Matlab读取GNSS 观测值o文件代码示例
[Chongqing Guangdong education] Shandong University College Physics reference materials
Unity3D,阿里云服务器,平台配置
Fabrication of fairygui simple Backpack
Fairygui gain buff value change display
Compilation principle: preprocessing of source program and design and implementation of lexical analysis program (including code)
随机推荐
單片機藍牙無線燒錄
Acwing-116 pilot brother
NovAtel 板卡OEM617D配置步骤记录
MySQL error warning: a long semaphore wait
Unity3D基础入门之粒子系统(属性介绍+火焰粒子系统案例制作)
【rtklib】在rtk下使用抗差自适应卡尔曼滤波初步实践
Devops' future: six trends in 2022 and beyond
数据库课程设计:高校教务管理系统(含代码)
Unity scene jump and exit
FairyGUI增益BUFF数值改变的显示
[Yu Yue education] guide business reference materials of Wuxi Vocational and Technical College of Commerce
What is the maximum length of MySQL varchar field
FairyGUI按钮动效的混用
Design and implementation of general interface open platform - (39) simple and crude implementation of API services
Remember an experience of ECS being blown up by passwords - closing a small black house, changing passwords, and changing ports
FairyGUI人物状态弹窗
By v$rman_ backup_ job_ Oracle "bug" caused by details
编译原理:源程序的预处理及词法分析程序的设计与实现(含代码)
What are the advantages of using SQL in Excel VBA
Unity3d camera, the keyboard controls the front and rear left and right up and down movement, and the mouse controls the rotation, zoom in and out