关于算法:每日一题子串能表示从-1-到-N-数字的二进制串

1016. 子串能示意从 1 到 N 数字的二进制串

关键词：数学、二进制

题目起源：1016. 子串能示意从 1 到 N 数字的二进制串 – 力扣（Leetcode）

题目形容

 T 数学
 T 二进制

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

子字符串 是字符串中间断的字符序列。

输出：s = "0110", n = 3
输入：true

输出：s = "0110", n = 4
输入：false

数据范畴
1 <= s.length <= 1000
s[i] 不是 '0' 就是 '1'
1 <= n <= 109

问题剖析

数学知识：对于所有 k 位的二进制数（最高位为 1，k>1），将其最高位的 1 去掉并去除前导 0 后，能够失去所有 1~k- 1 位的二进制数。

对于题目给定的 n，必有 k 满足 2 ^k≤n<2^k+1，若 s 中含有 [2^k-1 , 2^k-1] 所有的数，也即 s 中含有所有 k 位二进制数，则其必然含有所有 1~k 位的二进制数，剩下的就是判断 s 中是否含有 [2^k, n] 所有的数（k+ 1 位）。

于是，问题等价于判断 s 中是否含有所有 k 位二进制数和局部 k + 1 位二进制数。

k 位二进制数共有 2 ^k-1 个，所以 s 至多含有 2 ^k-1 个长度为 k 的 01 序列，也即 m 至多为 k +2^k-1 -1,。

k+ 1 位二进制数共有 n -2^k + 1 个，所以 s 至多含有 n -2^k + 1 个长度为 k + 1 的 01 序列，也即 m 至多为 k +1 + n-2^k +1-1，即 k +1 + n-2^k。

又因为 m 最大值为 1000，所以 k 必然超过 10，故枚举所有长度为 k 和 k + 1 的序列，将其退出哈希表，最初判断是否存在 [2^k-1 , n] 所有的数。

当 n 为 1 时非凡解决，直接判断 s 中是否含有 1 即可。

代码实现

bool queryString(string s, int n) {
    // n= 1 非凡解决
    if (n == 1)
        return s.find('1') != s.npos;
    // n∈[2^k, 2^(k+1)-1]
    int k = 31;
    while ((1 << --k) >= n);
    // 判断长度
    if (s.size() < (1 << (k - 1)) + k - 1 ||
        s.size() < n - (1 << k) + k + 1)
        return false;
    // 枚举
    auto check = [&](int l, int dn, int up) {
        unordered_set<int> f;
        int t = 0, m = s.size(), M = (1 << l) - 1;
        for (int i = 0; i < m; i++) {t = ((t << 1) | (s[i] - '0')) & M;
            if (t >= dn && t <= up)
                f.insert(t);
        }
        return f.size() == up - dn + 1;};
    return check(k, 1 << (k - 1), (1 << k) - 1) && check(k + 1, 1 << k, n);
}

工夫复杂度：O(log(n)+m)

空间复杂度：O(m)