关于算法:每日一题子串能表示从-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 <= 1000s[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)