我正在制作一个函数,以
length:int
和 distance:int
作为输入,并输出在其二进制表示中满足以下属性的最大整数:
以
1
开头,以 1
结束
每个
distance - 1
之间有
0
很多
1
其长度严格小于
length
可以按如下方式实现:
def repeatdigit(length:int, distance:int) -> int:
result = 0
pointer = 1
for _ in range(1, length, distance):
result |= pointer
pointer <<= distance
return result
例如:
repeatdigit(10,3)==0b1001001
、repeatdigit(15,4)=0b1000100010001
。我只关心二进制,因为我需要将它用作位操作的工具。实际上,length
会很大,distance ** 2 < length
。假设输入有效。
顾名思义,它一遍又一遍地重复相同的模式。
一个明确的公式:
result = (1 << (length+distance-2 - ((length-2) % distance)))//((1 << distance) - 1)
但这两种算法都很慢,它们的时间复杂度都是 O(n²),其中 n =
length
。
用列表做类似的事情只需要 O(n)。即
([1]+[0]*(distance-1)) * ((length-2)//distance) + [1]
(上下文:我想制作这样一个整数,这样我就不需要将 0 和 1 存储在很长的列表中,因为它很占用空间)
如何在 O(n) 时间内生成这样一个整数?
将 1 位的数量加倍,而不是一次只添加一个:
def repeatdigit(length:int, distance:int) -> int:
def f(want):
if want == 1:
return 1
have = (want + 1) // 2
x = f(have)
add = min(have, want - have)
return x | (x << (add * distance))
ones = 1 + (length - 2) // distance
return f(ones)