连接连续二进制数字
难度:
标签:
题目描述
代码结果
运行时间: 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的顺序来计算结果?
▷🦆
在题解中提到的变量`t`, `u`, `v`, `w`, `x`分别代表什么意义?这些变量如何影响最终的计算结果?
▷🦆
题解中使用了pow函数来进行幂运算和模运算,这种方法在处理大数字时的效率如何?
▷🦆
题解中将`zeroes`变量用于记录二进制串中0的数量,这一步骤在算法中起到了什么作用?
▷