动态规划解法:
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)的时间复杂度。
1.在 COS 存储端,可以考虑用每个 object name 来决定顺序,例如加上时间戳等唯一 ID,而不是用 append 的方式。
2.也可以考虑使用消息队列,Worker 按序从 MQ 中消费结果文件路径,进一步确保顺序。
3.对结果文件本身,也可以添加序号或标识,这样即使顺序错乱,解析时也能恢复正确顺序
Select Language