题目描述：
给出一个二进制字符串 $s$ 和一个正整数 $n$ ，如果对于 $[1,n]$ 中的每个证书，其二进制都是 $s$ 的子字符串，返回 $true$ ，否则返回 $false$ 。
数据范围：
$1\le n \le 10^9;1\le s.length\le 1000$
题解：
因为 $10^9$ 的二进制最多有 $30$ 位，因此对于一个位置 $i$ ，最多能找到 $\log(n)$ 个数字，因此最多能得到 $m\log(n)$ 个数字，其实范围很小，是 $30\times m$ 。其实最多应该是 $m \times \log (\min(m,n))$ ，因为字符串长度 $m$ 也有限制。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
string int_to_bit(int n)
{
string ret;
while (n)
{
if (n & 1)
ret.push_back('1');
else
ret.push_back('0');
n >>= 1;
}
reverse(ret.begin(), ret.end());
return ret;
}
bool queryString(string s, int n)
{
string bit;
if(n > s.size() * 30) return false;
for (int i = 1; i <= n; ++i)
{
bit = int_to_bit(i);
if (s.find(bit) == s.npos)
return false;
}
return true;
}
};
|