算法leetcode

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

字数统计: 1.1k字   |   阅读时长: 4分
, ,

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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