把一个uint64数组A = [a1,a2,a3...] 用variant压缩(具体怎么压缩不用管，只需要关心写入后的长度)的方式序列化到一个bytes.
已知写入的起始位置是L, 把数组A写入bytes之后, 得到结束位置R.
因为A中的所有元素都小于L, 为了得到更好的压缩率, 有一种优化方法是用R分别减去将A中的所有元素(在反序列化时只能知道R的值,所以不能减去L)
得到数组B = [b1 = R-a1, b2 = R-a2, b3 = R-a3...],在反序列化时，可以通过R - bi的方式得到ai.
但是在序列化之前，不知道R的值，所以需要先求出R，才能用这种优化方法。那么怎么算R的值呢？
换句话说R,L,A符合 已知L,A, 求R的最小值(得到的R不是最小值也可以接受).
可以保证 ai < L < R, 且上述所有的值的取值范围都在uint64的值域内.
觉得描述不清的可以让我补充.
一个比较明显的思路是二分, 但是我想要一个 的算法, 不过我也不确定是不是存在, 大佬们教一下.
更新: 二分不能保证取到的R的值最小.
variant_size的计算方式.
def variant_size(i: int):
assert 0 <= i < (1 << 64);
if i < (1 << 7):
return 1
if i < (1 << 14):
return 2
if i < (1 << 21):
return 3
if i < (1 << 28):
return 4
if i < (1 << 35):
return 5
if i < (1 << 42):
return 6
if i < (1 << 49):
return 7
if i < (1 << 56):
return 8
if i < (1 << 63):
return 9
return 10
# 给一个暴力解造测试数据
def brute_force(l, a):
mi, ma = l, l + len(a) * 10
for r in range(mi, ma + 1):
size = 0
for i in a:
size += variant_size(r - i)
if l + size == r:
return r
print(brute_force(10, [1, 2, 3, 4, 5, 6, 7]))作为感谢, 可以在里面随便挑一个能用LeetCode积分换的 https://leetcode.cn/store
评论 (12)
