问个算法题# JobHunting - 待字闺中
G*n
1 楼
数出从0到N用二进制表示的所有数的1的个数.算法复杂度要求log(N),可以用
recurrence.
比如0到4,一共有有0+1+1+2+1=5
recurrence.
比如0到4,一共有有0+1+1+2+1=5
i*e
2 楼
Recursion + caching，可以转换成 bottom-up DP.
0000. F(0) = 0
0001. F(1) = 1
0010. F(2) = 2
0011. F(3) = 4
0100. F(4) = 5
0101. F(5) = 7
0110. F(6) = 9
0111. F(7) = 12 = (7-3) + 2*F(3) = 4 + 2*4 = 12
1000. F(8) = 13
...
1111. F(15) = (15-7) + 2*F(7) = 8 + 2*12 = 32
假设要找的是 F(N)，那么首先设 k = ceil( log(N+1) )
建立表从 F(2^i - 1), i = 0 .. k , O(log N) 时间
然后计算 F(N) = N-(2^k - 1) + F(2^k - 1)
0000. F(0) = 0
0001. F(1) = 1
0010. F(2) = 2
0011. F(3) = 4
0100. F(4) = 5
0101. F(5) = 7
0110. F(6) = 9
0111. F(7) = 12 = (7-3) + 2*F(3) = 4 + 2*4 = 12
1000. F(8) = 13
...
1111. F(15) = (15-7) + 2*F(7) = 8 + 2*12 = 32
假设要找的是 F(N)，那么首先设 k = ceil( log(N+1) )
建立表从 F(2^i - 1), i = 0 .. k , O(log N) 时间
然后计算 F(N) = N-(2^k - 1) + F(2^k - 1)
d*t
3 楼
为啥F（2）＝2？
【在 i**********e 的大作中提到】
: Recursion + caching，可以转换成 bottom-up DP.
: 0000. F(0) = 0
: 0001. F(1) = 1
: 0010. F(2) = 2
: 0011. F(3) = 4
: 0100. F(4) = 5
: 0101. F(5) = 7
: 0110. F(6) = 9
: 0111. F(7) = 12 = (7-3) + 2*F(3) = 4 + 2*4 = 12
: 1000. F(8) = 13
【在 i**********e 的大作中提到】
: Recursion + caching，可以转换成 bottom-up DP.
: 0000. F(0) = 0
: 0001. F(1) = 1
: 0010. F(2) = 2
: 0011. F(3) = 4
: 0100. F(4) = 5
: 0101. F(5) = 7
: 0110. F(6) = 9
: 0111. F(7) = 12 = (7-3) + 2*F(3) = 4 + 2*4 = 12
: 1000. F(8) = 13
i*e
4 楼
不好意思，自己发现有漏洞：
最后的 F(N) = N-(2^k - 1) + F(2^k - 1)，这是不对的
这个要不断递归才能找到。
最后的 F(N) = N-(2^k - 1) + F(2^k - 1)，这是不对的
这个要不断递归才能找到。
i*e
5 楼
F(2) = F(1) + #bits in 2 = 1 + 1 = 2.
因为 2 的二进制表示是10，只有1个 one bit.
【在 d********t 的大作中提到】
: 为啥F（2）＝2？
因为 2 的二进制表示是10，只有1个 one bit.
【在 d********t 的大作中提到】
: 为啥F（2）＝2？
i*e
6 楼
补充一下，最后的递归 formula 应该是：
F(N) = N-(2^k - 1) + F(2^k - 1) + F（N - k）
，k = ceil( log(N+1) )
F(N-k) 不断的带进去递归最后找到。
如上面所说的，首先做 caching 来优化成 O(log N) runtime
建立表从 F(2^i - 1), i = 0 .. k , O(log N) 时间
F(N) = N-(2^k - 1) + F(2^k - 1) + F（N - k）
，k = ceil( log(N+1) )
F(N-k) 不断的带进去递归最后找到。
如上面所说的，首先做 caching 来优化成 O(log N) runtime
建立表从 F(2^i - 1), i = 0 .. k , O(log N) 时间
j*a
7 楼
http://mitbbs.com/article1/Programming/31212895_3_0.html
【在 G***n 的大作中提到】
: 数出从0到N用二进制表示的所有数的1的个数.算法复杂度要求log(N),可以用
: recurrence.
: 比如0到4,一共有有0+1+1+2+1=5
【在 G***n 的大作中提到】
: 数出从0到N用二进制表示的所有数的1的个数.算法复杂度要求log(N),可以用
: recurrence.
: 比如0到4,一共有有0+1+1+2+1=5
b*c
8 楼
easy high school coding contest problem
H*e
9 楼
假设N用二进制表示为 1101 ， 一共有m 位,ie 4，
可以考虑一个虚拟的二进制树，不用建树，所以不会增加复杂度
因为这个树一定是binary的，并且是 complete tree（ heap 的那种结构 ，只有最后
的leaf可能有gap)
定义full tree为完树，也就是总共有2^n + 1的那种
先算一下所有以0为root的full tree的中1的个数，
f(k) = 2f(k-1) + 1 and f(2) = 1 f(1) =0
比如: full tree:
0
0 1
0 1 0 1
f(3) = 3
接着， 对N的二进制(1100)表示进行处理，从最高位开始，如果是0什么都不做，进入
下一位， 如果是1，则以为着有一个full tree的以0为root的存在，在sum = sum + f(
4) + 1 (此位) ，然后进入下一位。
这里为1，意味着有0为root的full tree存在 sum=sum+f(3)+1
再下一位0,什么都不做，进入下一位: 1, sum=sum+f(1) + 1
total = 7+1+3 + 1 + 1= 13
因为只有lgN位，所以复杂度是lgN
【在 G***n 的大作中提到】
: 数出从0到N用二进制表示的所有数的1的个数.算法复杂度要求log(N),可以用
: recurrence.
: 比如0到4,一共有有0+1+1+2+1=5
可以考虑一个虚拟的二进制树，不用建树，所以不会增加复杂度
因为这个树一定是binary的，并且是 complete tree（ heap 的那种结构 ，只有最后
的leaf可能有gap)
定义full tree为完树，也就是总共有2^n + 1的那种
先算一下所有以0为root的full tree的中1的个数，
f(k) = 2f(k-1) + 1 and f(2) = 1 f(1) =0
比如: full tree:
0
0 1
0 1 0 1
f(3) = 3
接着， 对N的二进制(1100)表示进行处理，从最高位开始，如果是0什么都不做，进入
下一位， 如果是1，则以为着有一个full tree的以0为root的存在，在sum = sum + f(
4) + 1 (此位) ，然后进入下一位。
这里为1，意味着有0为root的full tree存在 sum=sum+f(3)+1
再下一位0,什么都不做，进入下一位: 1, sum=sum+f(1) + 1
total = 7+1+3 + 1 + 1= 13
因为只有lgN位，所以复杂度是lgN
【在 G***n 的大作中提到】
: 数出从0到N用二进制表示的所有数的1的个数.算法复杂度要求log(N),可以用
: recurrence.
: 比如0到4,一共有有0+1+1+2+1=5
相关阅读
H1B申请时完成博士学业但是没有学位证如何处理？Google vs Facebook 如何选择 及 问题招software engineerAgent Recuriter 联系需要SSN吗湾区Fremont 小公司招java developer有在FB和G工作过的大牛评价一下两家的review过程吧国人当大老板还是强啊！选大公司还是继续在小公司混亚麻在西雅图的sde 2 package是什么水准？opt转h1b需新offer letter吗 (转载)【转】Uber- 非常可怕 《在Uber奇怪的一年》这年头弯曲人的BSO的多了 (转载)突然想到一个面试题，要是问能估算一下今晚全球的安全套用量H1B和H4 EAD该选哪个三星内推(好项目)Data Scientist-NLP/text analyticsRang Technologies这个公司有人了解吗？遇到这样的老板咋办兩年沒工作 懇求內推會計/財務職位请问物理专业PhD转码工应该学那种语言？花街教弯曲资本家压榨码工的新招 (转载)