子串能表示从 1 到 N 数字的二进制串
难度:
标签:
题目描述
代码结果
运行时间: 28 ms, 内存: 16.0 MB
/*
* Problem Statement:
* Given a binary string 's' and a positive integer 'n',
* return true if for every integer in the range [1, n],
* its binary representation is a substring of 's'. Otherwise, return false.
*
* Approach using Java Stream:
* 1. Utilize IntStream to iterate through each integer from 1 to n.
* 2. Convert each integer to its binary representation.
* 3. Check if the binary representation is a substring of 's'.
* 4. If all binary representations are found, return true; otherwise, return false.
*/
import java.util.stream.IntStream;
public class Solution {
public boolean queryString(String s, int n) {
return IntStream.rangeClosed(1, n)
.mapToObj(Integer::toBinaryString) // Convert each integer to binary
.allMatch(s::contains); // Check if all binary representations are in s
}
}
解释
方法:
该题解使用了一个直接而有效的方法,利用 Python 的 all() 函数和字符串的 in 操作符来判断每个在1到n范围内的整数的二进制表示是否为给定字符串 s 的子字符串。对于每个 i 从 1 到 n,我们将 i 转换成它的二进制表示(通过 bin(i)[2:] 获取,去掉前缀 '0b'),并检查这个二进制字符串是否存在于 s 中。
时间复杂度:
O(n*m*log(n))
空间复杂度:
O(m)
代码细节讲解
🦆
如何评估这种方法对于非常大的n值(接近10^9)的执行效率?
▷🦆
题解中提到利用的是Python的all()函数,这种函数在处理大量数据时的性能表现如何?
▷🦆
对于二进制字符串中存在大量重复子字符串的情况,这种算法的性能会受到哪些影响?
▷