leetcode
leetcode 1501 ~ 1550
连接连续二进制数字

连接连续二进制数字

难度:

标签:

题目描述

代码结果

运行时间: 61 ms, 内存: 16.1 MB


/*
 * 思路:
 * 1. 使用 IntStream 从 1 到 n 进行遍历。
 * 2. 对于每个整数 i,计算其二进制表示的长度 len。
 * 3. 使用 reduce 方法将结果累加起来。
 * 4. 在每次累加时,将当前结果左移 len 位并加上 i,最后对结果取模 10^9 + 7。
 * 5. 返回最终结果。
 */

import java.util.stream.IntStream;

public class Solution {
    public int concatenatedBinary(int n) {
        final int MOD = 1000000007;
        return IntStream.rangeClosed(1, n)
                .reduce(0, (res, i) -> (int)(((res * (1L << Integer.toBinaryString(i).length())) + i) % MOD));
    }
}

解释

方法:

该题解采用了一种逆向思考的方法,通过逐步减小 n 的值来计算结果。算法从最大的可能的二进制位数开始,逐步向下计算。对于每个 k(从 64 到 2),检查 2^(k-1) 是否小于等于 n。如果是,则计算当前位数下的二进制数的贡献,并更新 n 和 zero 的值。最后,将所有贡献累加得到最终答案。

时间复杂度:

O(log n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在题解中采用逆向思考的方法,而不是直接按照1到n的顺序来计算结果?
逆向思考的方法允许从最大可能的二进制位数开始逐步向下计算,这样做可以更高效地利用二进制数的性质,减少重复计算。从1到n的顺序计算可能涉及到大量的字符串操作和位移,这在处理大量数据时会非常低效。逆向方法可以直接从较大的块开始处理,减少运算次数和提高效率。
🦆
在题解中提到的变量`t`, `u`, `v`, `w`, `x`分别代表什么意义?这些变量如何影响最终的计算结果?
`t` 表示从当前的二进制位数开始计数,直到n的剩余部分。`u` 是用于计算当前位数下所有可能的二进制数的和。`v` 是求模逆元,用于计算除法在模运算下的结果。`w` 用于调整计算结果,确保正确计算二进制数的总贡献。`x` 用于通过之前计算的0的数量来调整结果。这些变量相互作用,共同确定最终的模运算结果,确保在大数字计算中的正确性和效率。
🦆
题解中使用了pow函数来进行幂运算和模运算,这种方法在处理大数字时的效率如何?
使用pow函数进行幂运算和模运算非常高效,特别是在处理大数字时。Python的pow函数实现了模幂运算,这可以大幅减少计算时间和空间复杂度。特别是当基数和指数非常大时,直接计算将非常耗时和占用大量内存,而使用pow函数可以有效解决这个问题,确保算法在大规模输入下仍然高效。
🦆
题解中将`zeroes`变量用于记录二进制串中0的数量,这一步骤在算法中起到了什么作用?
`zeroes`变量记录的是在计算过程中,所有已处理的二进制数中0的总数量。这个数量对于调整每个新数值的位置非常重要,确保它们在最终结果中正确地拼接。例如,如果前面的数占据了多个二进制位,后续的数必须相应地左移这么多位,`zeroes`用于记录这个位移量。这确保了每个数的二进制表示在最终结果中的相对位置正确无误。

相关问题