这是一个创建于 248 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目是这个：
给定一个输入 n ，输出一个包含 n 个元素数组，数组中每个元素表示其索引的二进制形式中的数字 1 的个数，请给出对应算法并说明复杂度
依稀好像看过这个题，不确定到底有没有 o1 的数学解，我就说要是我的话肯定暴力数 0
面试官说给你提个醒能不能动态规划解这个题
我说没必要啊暴力数数也不慢，c 语言里面直接读内存，js 里可以位运算展开一下，最差情况也就是 32n 或者 64n 的复杂度。即使是 o1 的数学解也就是把 32n 降到 n ，讨论复杂度的时候本来就省略固定系数的
然后面试官就结束了提问环境，说我有啥问题要问的没然后结束了面试。
那么动态规划怎么更高效的解这个题呢？还是说我对 32n 的这个解释是有问题的？
给定一个输入 n ，输出一个包含 n 个元素数组，数组中每个元素表示其索引的二进制形式中的数字 1 的个数，请给出对应算法并说明复杂度
依稀好像看过这个题，不确定到底有没有 o1 的数学解，我就说要是我的话肯定暴力数 0
面试官说给你提个醒能不能动态规划解这个题
我说没必要啊暴力数数也不慢，c 语言里面直接读内存，js 里可以位运算展开一下，最差情况也就是 32n 或者 64n 的复杂度。即使是 o1 的数学解也就是把 32n 降到 n ，讨论复杂度的时候本来就省略固定系数的
然后面试官就结束了提问环境，说我有啥问题要问的没然后结束了面试。
那么动态规划怎么更高效的解这个题呢？还是说我对 32n 的这个解释是有问题的？
22 条回复 • 2024-04-24 12:23:59 +08:00
 |
1
vacuitym 248 天前
面试官要动态规划你就回答动态规划，除非你不会
|
 |
3
duality 248 天前
从 0 开始处理，设 A[0] = 0
For (i = 1 ... n) 设 i 的最高非零位为 d 位 A[i] = A[i - (1<<(d-1))] + 1 |
 |
4
kera0a 248 天前 via iPhone
有没有可能都不是算法的问题，面试官只是觉得你不好沟通了。
会觉得等到要给你需求时你也来一句"没必要啊"怎么办 现在牛马太多了，一点点不合意就直接下一位了 |
 |
5
finalwave 248 天前  1
DP[ i ] = DP[ floor(i / 2) ] + (i & 1)
|
 |
6
sagaxu 248 天前
右移一位得到一个更小的数，这个数的 1 的个数已经算好了，加上当前最右位就是当前数字的 1 的个数
计算量是稍微小了一点点，但是空间从 O(1)变 O(n)了，如果是 10 亿个数呢，100 亿个呢 |
 |
8
Sawyerhou 248 天前 via Android
3 楼的递归是个好思路，说态度问题的也有道理，毕竟直接结束了面试
毕竟是算法题，暴力解不太合适吧 |
 |
9
MoYi123 248 天前
2 种可能性,
1. 你题目理解错了 2. 面试官 sb |
 |
10
misdake 248 天前
这个题挺有意思，再往底层走还可以问多线程和 cpu 缓存相关的内容，如何优化到极致
|
|
11
misdake 248 天前
如果把统计 1 的数量改成统计所有质因数之和，会更有意思一点
|
 |
12
codegenerator 248 天前
这题你理解错了，就是个位运算的题目
但是如果你是面前端，那就是面试官的问题 |
 |
13
main1234 248 天前
这里不就是奇数和偶数判断一下么，如果元素为 i ，i 如果是奇数则 i 的二进制 1 为 i-1 的二进制 1 个数+1 ，如果是偶数则是 i/2 的二进制数
|
|
14
main1234 248 天前
|
|
15
main1234 248 天前
对于奇数，二进制表示中奇数一定比前面的偶数多一个 1 ，多的就是最低位的 1
如 0 = 0 ，1 = 1 ，2=10 ，3=11 对于偶数，二进制表示中偶数一定和除以 2 之后的那个数一样多，因为最低位是 0 ，除以 2 就是右移一位 2 = 10 ，4=100 ，8=1000 |
 |
16
zzblack 248 天前
这个“没必要啊”属实绷不住了，面试官是想通过这个题考查你的算法能力，你直接暴力了，那他面试评价咋写？面试是一个候选人展示自己的过程，面试官的题目难度其实是决定了你能展示出来的能力的上限。你这句没必要啊。。是我面你我也直接结束了
|
 |
17
zhuxuanyu0720 248 天前
动态规划解法:
def countBits(n): result = [0] * (n+1) offset = 1 for i in range(1, n+1): if offset * 2 == i: offset *= 2 result[i] = result[i - offset] + 1 return result[:n] offset 代表的是该区间内最小数字(即起始数字)的二进制位数。offset 变量代表当前位置所属的那个长度为 offset 的区间的起始点。举例来说,当 offset=1 时,表示区间[0,1];当 offset=2 时,表示区间[2,3];当 offset=4 时,表示区间[4,7]. 有一个数学规律 对于任意一个数字 x,如果 x 和 x+1 的二进制位数相同,那么 x 和 x+1 对应的 1 的个数,最多只相差 1 ，这个特性就被用来推导 result 数组中相邻两个数字对应的 1 的个数 所以通过区间分治的方式,算法可以高效地确定每一个区间的起点,并利用相邻区间的结果推导出当前区间每个数字对应的 1 的个数,从而达到 O(n)的时间复杂度。 |
 |
18
xiaozhaoz 248 天前
根据前一个数 的三种情况：
- 最后一位 0 ，1 的个数 + 1 - 前一个数全 1 ，1 的个数回到 1 ，实现方法：记住前一个数二进制长度，“~前一个数 & （ 0x1<<位数）- 1” == 0 - 其他情况，1 的个数不变 |
|
19
xiaozhaoz 248 天前
@xiaozhaoz 错了，最后一种情况 1 的个数会变。
看到过一个算法，可以算一个 32bits 的 1 个数。 int count(unsigned x) { x = x - ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0F0F0F0F; x = x + (x >> 8); x = x + (x >> 16); return x & 0x0000003F; } |
 |
20
Orlion 247 天前
leetcode 338 原题，动态规划的转移方程：bits[i] = bits[i >> 1] + (i & 1)。
|
 |
21
GrayXu 247 天前
算法题只是智力题
|
 |
22
majula 247 天前
去看了下 leetcode 338 ，果然是不让用 popcnt intrinsic 的，不然就是一个非常 trivial 的 O(n)
其实就算不让用 intrinsic ，popcnt 也有 branchless 且 lut-less 的 trivial 实现。参考 Bit Twiddling Hacks： v = v - ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 不过既然题干都那么说了，还是别投机取巧了，老老实实动态规划吧 |
Select Language