这是一个创建于 536 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目是这个：
给定一个输入 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 的这个解释是有问题的？
 | 1 vacuitym 2024-04-23 15:24:35 +08:00 面试官要动态规划你就回答动态规划，除非你不会 |
 | 3 duality 2024-04-23 15:33:53 +08:00 从 0 开始处理，设 A[0] = 0 For (i = 1 ... n) 设 i 的最高非零位为 d 位 A[i] = A[i - (1<<(d-1))] + 1 |
 | 4 kera0a 2024-04-23 15:39:30 +08:00 via iPhone 有没有可能都不是算法的问题，面试官只是觉得你不好沟通了。 会觉得等到要给你需求时你也来一句"没必要啊"怎么办 现在牛马太多了，一点点不合意就直接下一位了 |
 | 5 finalwave 2024-04-23 15:41:42 +08:00  1 DP[ i ] = DP[ floor(i / 2) ] + (i & 1) |
 | 6 sagaxu 2024-04-23 15:43:55 +08:00 右移一位得到一个更小的数，这个数的 1 的个数已经算好了，加上当前最右位就是当前数字的 1 的个数 计算量是稍微小了一点点，但是空间从 O(1)变 O(n)了，如果是 10 亿个数呢，100 亿个呢 |
 | 8 Sawyerhou 2024-04-23 15:59:54 +08:00 via Android 3 楼的递归是个好思路，说态度问题的也有道理，毕竟直接结束了面试 毕竟是算法题，暴力解不太合适吧 |
 | 9 MoYi123 2024-04-23 16:02:36 +08:00 2 种可能性, 1. 你题目理解错了 2. 面试官 sb |
 | 10 misdake 2024-04-23 16:08:48 +08:00 这个题挺有意思，再往底层走还可以问多线程和 cpu 缓存相关的内容，如何优化到极致 |
| 11 misdake 2024-04-23 16:12:31 +08:00 如果把统计 1 的数量改成统计所有质因数之和，会更有意思一点 |
 | 12 codegenerator 2024-04-23 16:14:34 +08:00 这题你理解错了，就是个位运算的题目 但是如果你是面前端，那就是面试官的问题 |
 | 13 main1234 2024-04-23 16:21:25 +08:00 这里不就是奇数和偶数判断一下么，如果元素为 i ，i 如果是奇数则 i 的二进制 1 为 i-1 的二进制 1 个数+1 ，如果是偶数则是 i/2 的二进制数 |
| 14 main1234 2024-04-23 16:22:26 +08:00 |
| 15 main1234 2024-04-23 16:23:46 +08:00 对于奇数，二进制表示中奇数一定比前面的偶数多一个 1 ，多的就是最低位的 1 如 0 = 0 ，1 = 1 ，2=10 ，3=11 对于偶数，二进制表示中偶数一定和除以 2 之后的那个数一样多，因为最低位是 0 ，除以 2 就是右移一位 2 = 10 ，4=100 ，8=1000 |
 | 16 zzblack 2024-04-23 16:51:52 +08:00 这个“没必要啊”属实绷不住了，面试官是想通过这个题考查你的算法能力，你直接暴力了，那他面试评价咋写？面试是一个候选人展示自己的过程，面试官的题目难度其实是决定了你能展示出来的能力的上限。你这句没必要啊。。是我面你我也直接结束了 |
 | 17 playkuntepai 2024-04-23 17:31:01 +08:00 动态规划解法: 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 2024-04-23 18:06:28 +08:00 根据前一个数 的三种情况： - 最后一位 0 ，1 的个数 + 1 - 前一个数全 1 ，1 的个数回到 1 ，实现方法：记住前一个数二进制长度，“~前一个数 & （ 0x1<<位数）- 1” == 0 - 其他情况，1 的个数不变 |
| 19 xiaozhaoz 2024-04-23 18:22:43 +08:00 @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 2024-04-24 09:24:52 +08:00 leetcode 338 原题，动态规划的转移方程：bits[i] = bits[i >> 1] + (i & 1)。 |
 | 21 GrayXu 2024-04-24 12:15:22 +08:00 算法题只是智力题 |
 | 22 48y1951r9G8k7Zou 2024-04-24 12:23:59 +08:00 去看了下 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