返回信息流第一个题
第二个题
第三个没图
记得是给一个降序数组[7,6,5,4,3,2,1]，输出调整顺序使得变成[7,1,6,2,5,3,4],就是变成 [最大，最小，次大次小...] 这样的顺序
哦哦，这个题要求空间复杂度o（1）
第四个也没图
x是一个整数
f(x)是一个把x各个位相加的函数，比如：
x=123
f(x)=1+2+3=6
g(x)是把x的二进制的各个位相加的函数，比如：
x=123
bin(x)=1111011
g(x)=1+1+1+1+0+1+1=6
然后让写一个函数，输入n，返回有多少个小于n的数，使得f(x)=g(x)
这个题直接比的话肯定超时，有没有trick啊？
求大大们教导啊
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91107同步于 2016/9/19
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
笔试题从来做不出来系列（求指教）
lzc6996
2016/9/19镜像同步38 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
空间复杂度要求o1
【 在 flymop 的大作中提到: 】
: 第三题我觉得可以用findkth的算法复杂度是logn遍厉一遍复杂度是nlogn 有更简单的算法么
【 在 lzc6996 的大作中提到: 】
: 第一个题
: [upload=1][/upload]
: [upload=2][/upload]
: ...................
第三题o(1)空间怎么读数组？
第四题：十进制之和肯定是要求的（当然也可以递推，不过log(10)n应该很快的）
二进制之和可以开个数组，先求出2的n次方对应的二进制之和，0是0，其他都是1，然后递推，n=2的x次方+（x-1次方-x次方之间的一个数）然后n的二进制就对应那两个二进制的数的二进制之和，每个查询两次
总的复杂度计算n*log(10)n*2
即为：O(n*lgn)
直接求二进制的和就再*logn
第四题，DP
对于十进制 dp[x]表示x 10进制所有位数之和 则dp[x] = dp[x / 10] + x %10
对于二进制 dp[x]表示x 2进制所有位数之和 则dp[x] = 1 + dp [x & (x - 1)]
o(n)时间计算出结果 之后直接遍历2个dp数组判断对应是否相等即可