LeetCode每日一题:1680. 连接连续二进制数字
在LeetCode上,我们经常会遇到各种有趣的算法问题。今天,我们将探讨第1680题:连接连续二进制数字。这个问题要求我们将从1到n的所有整数的二进制表示连接起来,然后返回这个长二进制字符串对应的十进制数字,并对10^9 + 7取余。
问题描述
给定一个整数n,你需要将1到n的二进制表示连接起来,并返回连接结果对应的十进制数字对10^9 + 7取余的结果。例如,如果n=3,那么1, 2, 3的二进制表示分别是'1', '10', '11',连接起来就是'11011',对应的十进制数是27。
示例
- 输入:n = 1
输出:1
解释:二进制的'1'对应十进制的1。 - 输入:n = 3
输出:27
解释:二进制下,1,2和3分别对应'1','10'和'11'。将它们连接起来得到'11011',对应十进制的27。
解题思路
为了解决这个问题,我们可以采用以下步骤:
- 初始化一个变量来存储最终的十进制结果,初始值为0。
- 遍历从1到n的每一个整数。
- 对于每一个整数,将其转换为二进制字符串,并将其添加到最终结果中。
- 将连接后的二进制字符串转换为十进制,并对10^9 + 7取余。
- 返回最终的十进制结果。
代码实现
以下是一个可能的Python实现:
def concatenatedBinary(n: int) -> int:
MOD = 10**9 + 7
result = 0
length = 0
for i in range(1, n + 1):
if (i & (i - 1)) == 0: # 检查i是否是2的幂
length += 1
result = ((result << length) | i) % MOD
return result
在这个实现中,我们使用位操作来优化二进制字符串的连接过程。每次遇到一个2的幂,我们就增加二进制字符串的长度。然后,我们将当前的整数左移相应的位数,并与结果进行按位或操作,最后对10^9 + 7取余。
测试
我们可以通过几个测试用例来验证我们的实现是否正确:
print(concatenatedBinary(1)) # 输出:1
print(concatenatedBinary(3)) # 输出:27
print(concatenatedBinary(5)) # 输出:31
这些测试用例应该返回正确的结果,验证我们的算法是有效的。
总结
通过这个问题,我们学习了如何处理二进制字符串的连接,并使用位操作来优化算法的性能。在解决类似问题时,考虑使用位操作可以大大提高效率,特别是在处理二进制数据时。
希望这个解答对你有所帮助!如果你有任何问题或需要进一步的解释,请随时提问。