leetcode 2026-02-28 每日一练 - 连接连续二进制数字

题目描述

LeetCode 1680. 连接连续二进制数字

给你一个整数 n，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的十进制数字对 10⁹ + 7 取余的结果。

示例：

  • 输入：n = 3
  • 输出：27
  • 解释：二进制表示中，1、2 和 3 分别是 "1"、"10" 和 "11"，连接起来是 "11011"，对应十进制 27

解题思路

核心思想

将 1 到 n 的二进制表示依次连接，相当于：

  1. 对于每个数字 i，先将当前结果左移 i 的二进制长度位
  2. 然后将 i 加到结果中
  3. 每次操作后对 10⁹ + 7 取余

位运算技巧

  • 获取二进制长度：使用 bits.Len(uint(i)) 获取数字 i 的二进制位数
  • 左移操作：ans << len 相当于将 ans 乘以 2^len
  • 连接操作：ans << len | i 相当于将 i 追加到 ans 的二进制表示后面

示例演示

以 n = 3 为例：

  1. i = 1：len = 1，ans = (0 << 1 | 1) % mod = 1（二进制：1）
  2. i = 2：len = 2，ans = (1 << 2 | 2) % mod = 6（二进制：110）
  3. i = 3：len = 2，ans = (6 << 2 | 3) % mod = 27（二进制：11011）

代码实现

1
2
3
4
5
6
7
8
func concatenatedBinary(n int) (ans int) {
    const mod = 1_000_000_007
    for i := 1; i <= n; i++ {
        len := bits.Len(uint(i))
        ans = (ans<<len | i) % mod
    }
    return
}

核心细节

  1. bits.Len()：返回表示数字所需的最少位数

    • bits.Len(1) = 1（1 需要 1 位）
    • bits.Len(2) = 2（10 需要 2 位）
    • bits.Len(3) = 2（11 需要 2 位）
    • bits.Len(4) = 3（100 需要 3 位）

  2. 位运算组合：ans<<len | i

    • ans<<len：将当前结果左移，为新数字腾出空间
    • | i：将新数字 i 追加到末尾

  3. 取余时机：每次操作后立即取余，防止整数溢出

复杂度分析

  • 时间复杂度：O(n log n)，遍历 n 个数字，每次计算二进制长度需要 O(log i) 时间
  • 空间复杂度：O(1)，只使用常数额外空间

总结

这道题的关键点：

  • 理解二进制连接的本质：左移 + 或运算
  • 使用 bits.Len() 高效获取二进制位数
  • 及时取余避免溢出
  • 位运算比字符串拼接效率更高