问个算法题# 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
相关阅读
CS硕士毕业，想再去读本科是否可行？工资问题小公司的boss要面试Regular h1b 申请的国内成绩单需要美国这边认证吗pp h1b拿到receipt 多久才能有结果，急，求过来人我的 background check好像有点儿过长？攒rp，我今天的面试教训，一个很小的细节你为什么选择来工业界工作，面试回答。贴道老Coding题目两个brainteaser被hr耍了关于singleton 的面试题律师的意见都不一样啊...关于from H1b to F1,强烈呼吁中国企业在印度基础设施建设方面“戒急用忍“。 (转载)问一道算法题算法和编程的牛人很多啊...面试时这个问题怎么回答？请推荐C++多线程编程方面书籍回馈版面,Amazon onsite面经求Software Engineer大公司面试题库！