问个算法题# 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
相关阅读
求推荐资料：想重新系统性复习下OO designcheck time table created in IBM SQL Aginity workbench ? (转载)Yahoo现在怎么样A question about C++. Thanks.coursera的这门课咋样? Programming Cloud Services for Android Handheld Systemsericsson research media 组情况 （NMS）版上流行的包裹说法是怎么算的?好人做不了manager。有人听说过Origami Logic吗？H1B 已经生效 但之前的opt extension申请RFEG家店面考system design吗？leetcode里有从 字典里找词，然后操作的题目吧？突然找不到了暗示被拒的三句话面试 Expectation 问题请问：邮寄OPT 资料时，需要寄回邮信封吗？求码工工作refercloudera这个机会值得跳吗找工作时专业比经验到底哪个重要？［求内推］UX/UI design position问一个，有人知道在大公司fulltime用cpt工作的成功案例吗？