当前位置:网站首页>[algorithm] sword finger offer2 golang interview question 3: the number of 1 in the binary form of the first n numbers
[algorithm] sword finger offer2 golang interview question 3: the number of 1 in the binary form of the first n numbers
2022-07-06 12:51:00 【Deng Jiawen jarvan】
[ Algorithm ] The finger of the sword offer2 golang Interview questions 3: front n A number in binary form 1 The number of
subject 1:
Given a nonnegative integer n , Please calculate 0 To n In the binary representation of each number between 1 The number of , And output an array .
Example 1:
Input : n = 2
Output : [0,1,1]
explain :
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input : n = 5
Output : [0,1,1,2,1,2]
explain :
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
explain :
0 <= n <= 105
func countBits(n int) []int {
}
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/w3tCBm
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas 1:
Ideas 1: Violence counts every digit of every number 1 The number of , Time complexity O(n*17),10^5 < ^17
Code
func countBits(n int) []int {
// Ideas 1: Violence counts every digit of every number 1 The number of , Time complexity O(n*17),10^5 < ^17
// Processing parameters
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
}
test
Ideas 2:
// The main points of : i&(i-1) It's more than i in 1 One less number
// We can get through the previous i in 1 To find the number of , The time complexity is O(n)
Code 2
func countBits(n int) []int {
// The main points of : i&(i-1) It's more than i in 1 One less number
// We can get through the previous i in 1 To find the number of , The time complexity is 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
}
test 2
边栏推荐
- [算法] 剑指offer2 golang 面试题8:和大于或等于k的最短子数组
- [leetcode622]设计循环队列
- [leetcode622] design circular queue
- SSD technical features
- Fairygui gain buff value change display
- 【GNSS】抗差估计(稳健估计)原理及程序实现
- Agile development helps me
- [算法] 剑指offer2 golang 面试题2:二进制加法
- [algorithme] swordfinger offer2 golang question d'entrevue 2: addition binaire
- HCIP Day 12
猜你喜欢
[算法] 劍指offer2 golang 面試題2:二進制加法
Unity3D,阿里云服务器,平台配置
[Clickhouse kernel principle graphic explanation] about the collaborative work of partitioning, indexing, marking and compressed data
使用rtknavi进行RT-PPP测试
Idea problem record
Compilation principle: preprocessing of source program and design and implementation of lexical analysis program (including code)
C programming exercise
Affichage du changement de valeur du Buff de gain de l'interface graphique de défaillance
【无标题】
FairyGUI复选框与进度条的组合使用
随机推荐
SVN更新后不出现红色感叹号
地球围绕太阳转
Design and implementation of general interface open platform - (39) simple and crude implementation of API services
HCIP Day 12
NRF24L01 troubleshooting
Unity scene jump and exit
Halcon knowledge: gray_ Tophat transform and bottom cap transform
Compilation principle: preprocessing of source program and design and implementation of lexical analysis program (including code)
Office prompts that your license is not genuine pop-up box solution
FGUI工程打包发布&导入Unity&将UI显示出来的方式
1041 be unique (20 points (s)) (hash: find the first number that occurs once)
FairyGUI简单背包的制作
Fairygui loop list
Prove the time complexity of heap sorting
Excel导入,导出功能实现
PRIDE-PPPAR源码解析
Servlet
FairyGUI循環列錶
[算法] 剑指offer2 golang 面试题5:单词长度的最大乘积
Unity场景跳转及退出