LeetCode每日一题：1680. 连接连续二进制数字

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。

解题思路

为了解决这个问题，我们可以采用以下步骤：

1. 初始化一个变量来存储最终的十进制结果，初始值为0。
2. 遍历从1到n的每一个整数。
3. 对于每一个整数，将其转换为二进制字符串，并将其添加到最终结果中。
4. 将连接后的二进制字符串转换为十进制，并对10^9 + 7取余。
5. 返回最终的十进制结果。

代码实现

以下是一个可能的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

这些测试用例应该返回正确的结果，验证我们的算法是有效的。

总结

通过这个问题，我们学习了如何处理二进制字符串的连接，并使用位操作来优化算法的性能。在解决类似问题时，考虑使用位操作可以大大提高效率，特别是在处理二进制数据时。

希望这个解答对你有所帮助！如果你有任何问题或需要进一步的解释，请随时提问。