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