力扣1016-子串能表示从1到N数字的二进制串

  |  

摘要: 算术+滑动窗口+哈希表

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们看一个需要一点数学推导,同时又综合了滑动窗口和哈希表的问题。

题目

给定一个二进制字符串 s 和一个正整数 n,如果对于 [1, n] 范围内的每个整数,其二进制表示都是 s 的 子字符串 ,就返回 true,否则返回 false 。

子字符串 是字符串中连续的字符序列。

提示:

1
2
3
1 <= s.length <= 1000
s[i] 不是 '0' 就是 '1'
1 <= n <= 1e9

示例 1:
输入:s = “0110”, n = 3
输出:true

示例 2:
输入:s = “0110”, n = 4
输出:false

题解

算法:算术+滑动窗口+哈希表

考虑一个长度为 $k$ 且最高位是 1 的二进制数的范围。

比如 $k = 2$ 时,可以表示的数为:

比如 $k = 3$ 时,可以表示的数为:

因此长为 $k$ 且最高位为 1 的二进制数的范围为 $[2^{k-1}, 2^{k}-1]$。如果把这些数字抹去最高位的 1,则刚好为长度为 $k-1$ 的所有二进制数 $[0, 2^{k-1}-1]$,比如 $k = 3$ 对应 $[0, 3]$。

因此如果 $[2^{k-1}, 2^{k}-1]$ 都是 $s$ 的子串,那么 $[0, 2^{k-1}-1]$ 自然也是 $s$ 的子串。因此如果 $2^{k} - 1 \leq n < 2^{k+1}-1$,我们只需要考察 $[2^{k-1}, 2^{k}-1]$ 和 $[2^{k}, n]$ 这两个个范围的所有数对应的二进制是不是 $s$ 的子串即可。

下面的问题 $[2^{k-1}, 2^{k}-1]$ 和 $[2^{k}, n]$ 这些数的二进制数,字符串的长度 $m$ 最少需要多少才能全覆盖到。

如果是 1 个长为 $k$ 的二进制数,则 $m \geq k$,此后每增加一个,考虑到与原有的可能有重合的部分,$m$ 的最小值最少要增加 1。因此:

  • $[2^{k-1}, 2^{k}-1]$ 是 $2^{k-1}$ 个长度为 $k$ 的不同二进制数,字符串长度 $m$ 需要满足 $m \geq k + 2^{k-1} - 1$。
  • $[2^{k}, n]$ 时 $n - 2^{k} + 1$ 个长度为 $k + 1$ 的不同二进制数,字符串长度 $m$ 需要满足 $m \geq k + 1 + (n - 2^{k} + 1) - 1 = k + 1 + n - 2^{k}$。

综合以上分析,我们的算法流程如下:

  • step1: 确定 $k$,其值为 $n$ 的二进制表示的位数减 1。时间复杂度 $O(\log{n})$
  • step2: 由 $m >= k + 2^{k-1} - 1$ 和 $m \geq k + 1 + n - 2^{k}$ 判断 $m$ 是否满足最小值要求。
  • step3: 用长度为 $k+1$ 的滑动窗口扫描一遍字符串 $s$,用哈希表维护扫描到的二进制数字,看 $[2^{k}, n]$ 是否都扫描到了。时间复杂度 $O(m)$。
  • step4: 用长度为 $k$ 的滑动窗口扫描一遍字符串 $s$,用哈希表维护扫描到的二进制数字,看 $[2^{k-1}, 2^{k}-1]$ 是否都扫描到了。时间复杂度 $O(m)$。

该算法时间复杂度为 $O(\log{n} + m)$。

代码(C++)

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
bool queryString(string s, int n) {
int m = s.size();
int k = bit_length(n) - 1;
if(m < k + pow(2, k-1) - 1)
return false;
if(m < k + 1 + n - pow(2, k))
return false;
if(!sliding_window(s, k + 1, pow(2, k), n))
return false;
if(!sliding_window(s, k, pow(2, k - 1), pow(2, k) - 1))
return false;
return true;
}

bool sliding_window(const string& s, const int len, const int left, const int right)
{
// 长为 len 的滑动窗口扫描 s 一轮,看 [left, right] 是否都取到了
int num = 0; // 窗口的二进制表示的整数
int m = s.size();
// 第一个窗口
for(int i = 0; i < len; ++i)
{
num <<= 1;
num += s[i] - '0';
}
unordered_set<int> setting;
if(num >= left && num <= right)
setting.insert(num);
int mask = (1 << len) - 1;
for(int i = len; i < m; ++i)
{
num <<= 1;
num &= mask;
num += s[i] - '0';
if(num >= left && num <= right)
setting.insert(num);
}
return setting.size() == right - left + 1;
}

int bit_length(int n)
{
int len = 0;
while(n)
{
len++;
n >>= 1;
}
return len;
}
};

Share