Medium

题目描述

给定一个整数 n，返回将 1 到 n 的二进制表示按顺序连接形成的二进制字符串对应的十进制值，结果需要对 10^9 + 7 取模。

示例 1：

输入：n = 1
输出：1
解释："1" 的二进制对应十进制值 1。

示例 2：

输入：n = 3
输出：27
解释：1, 2, 3 的二进制分别为 "1", "10", "11"。
连接后得到 "11011"，对应十进制值 27。

示例 3：

输入：n = 12
输出：505379714
解释：连接结果为 "1101110010111011110001001101010111100"。
对应十进制值为 118505380540。
对 10^9 + 7 取模后结果为 505379714。

约束条件：

  • 1 <= n <= 10^5

提示：

  • 用递推公式表达第 n 个数的值，并考虑如何快速计算。

解题思路

这道题要求将 1 到 n 的二进制表示串联起来，然后转换为十进制数。

核心思路： 我们可以用递推的方式来解决这个问题。假设我们已经计算出了前 i-1 个数字串联的结果 result，现在要加入第 i 个数字的二进制表示。

关键观察：

  1. 当我们在已有的二进制串后面添加数字 i 的二进制表示时，相当于将原有结果左移 i 的二进制位数，然后加上 i
  2. 数字 i 的二进制位数可以通过 bit_length = floor(log2(i)) + 1 计算，或者更简单地用位运算判断

算法步骤：

  1. 从 1 开始遍历到 n
  2. 对于每个数字 i，计算其二进制位数
  3. 将当前结果左移相应位数（相当于乘以 2^位数），然后加上 i
  4. 每步都要对 MOD 取模防止溢出

优化技巧：

  • 可以预先计算每个数字的二进制位数，避免重复计算
  • 使用位运算来判断位数变化的时机：当 i 是 2 的幂时，位数会增加 1

时间复杂度：O(n)，空间复杂度：O(1)。

代码实现

class Solution {
public:
    int concatenatedBinary(int n) {
        const int MOD = 1e9 + 7;
        long long result = 0;
        int bitLength = 0;
        
        for (int i = 1; i <= n; i++) {
            // 当i是2的幂时，位长度增加1
            if ((i & (i - 1)) == 0) {
                bitLength++;
            }
            
            // 将result左移bitLength位，然后加上i
            result = ((result << bitLength) + i) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        MOD = 10**9 + 7
        result = 0
        bit_length = 0
        
        for i in range(1, n + 1):
            # 当i是2的幂时，位长度增加1
            if i & (i - 1) == 0:
                bit_length += 1
            
            # 将result左移bit_length位，然后加上i
            result = ((result << bit_length) + i) % MOD
        
        return result

public class Solution {
    public int ConcatenatedBinary(int n) {
        const int MOD = 1000000007;
        long result = 0;
        int bitLength = 0;
        
        for (int i = 1; i <= n; i++) {
            // 当i是2的幂时，位长度增加1
            if ((i & (i - 1)) == 0) {
                bitLength++;
            }
            
            // 将result左移bitLength位，然后加上i
            result = ((result << bitLength) + i) % MOD;
        }
        
        return (int)result;
    }
}

var concatenatedBinary = function(n) {
    const MOD = 1000000007;
    let result = 0;
    let shift = 0;
    
    for (let i = 1; i <= n; i++) {
        if ((i & (i - 1)) === 0) {
            shift++;
        }
        result = ((result << shift) + i) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历从1到n的所有数字
空间复杂度O(1)只使用常数级别的额外空间

相关题目