首页算法

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

难度

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

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

示例 1：

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

输出：true

示例 2：

输入：s = "0110", n = 4'

输出：false

提示：

  • 1 <= s.length <= 1000
  • s[i] 不是 '0' 就是 '1'
  • 1 <= n <= 10^9

# 暴力枚举字符串 + 哈希表

左边作为低位

class Solution {
    public boolean queryString(String s, int n) {
        // 0 1 1 0
        // 0 01 011 0110
        Set<Long> set = new HashSet<>();
        int m = s.length();
        int ans = 0;
        for (int i = m - 1; i >= 0; i--) {
            long v = 0;
            for (int j = i, k = 0; j >= 0; j--, k++) {
                if (s.charAt(j) != '0') {
                    v = v | ((long) 1 << k);
                    if (v > n) {
                        break;
                    }
                    set.add(v);
                }
            }
        }
        return set.size() == n;
    }
}

左边作为高位

class Solution {
    public boolean queryString(String s, int n) {
        // 0 1 1 0
        //   1 11 110
        Set<Long> set = new HashSet<>();
        int m = s.length();
        for (int i = 0; i < m; i++) {
            if (s.charAt(i) == '0') {
                continue;
            }
            long v = 0;
            for (int j = i, k = 0; j < m; j++, k++) {
                v = (v << 1) | (s.charAt(j) - '0');
                if (v > n) {
                    break;
                }
                set.add(v);
            }
        }
        return set.size() == n;
    }
}

# 复杂度分析

  • 时间复杂度：O(m log n)O(m\,log\,n)，mm 为 ss 的长度，内层最多循环 O(log n)O(log\,n) 次

    为什么不为超时？从上述可以大致看出，假设不考虑 ss 的重叠部分（即每个子串都不相同）nn 最多也就 m2m^2 个

  • 空间复杂度：O(min(m log n,n))O(min(m\,log\,n,n))

# 数学 + 滑动窗口 + 哈希表

参考：三种算法：从暴力到优化

若 n=7n = 7，对于闭区间 [4,7][4, 7]，有 44 个数，其二进制的长度均为 33，要让 ss 包含这 44 个数，则最少需要满足 m>=3+(4−1)m >= 3 + (4 - 1)

  • 考虑重复部分，即：长度为 33 的滑动窗口在 ss 中滑动，至少要得到 44 个子串。最少情况下滑动一个包含一个子串，由于初始就是一个，最少只需要滑动剩余 33 个即可。

假设 nn 的二进制长度为 k+1k + 1

  • 对于区间 [2k,n][2^{k}, n] 内，一共有 n−2k+1+1n - 2^{k + 1} + 1 个元素，由于长度为 k+1k + 1，则 m>=(k+1)+(n−2k+1+1−1)=k+n−2k+1+1m >= (k + 1) + (n - 2^{k + 1} + 1 - 1) = k + n - 2^{k + 1} + 1

    长度为 k+1k + 1 的滑动窗口在 ss 中滑动，考虑到重复部分，最少需要滑动 n−2k+1+1−1n - 2 ^ {k + 1} + 1 - 1 次

  • 对于区间 [2k−1,2k−1][2^{k - 1}, 2^{k} - 1] 内，一共有 2k−1−2k−1+1=2k−12^{k}-1 - 2^{k - 1} + 1 = 2^{k - 1} 个元素，由于长度为 kk，则 m>=(k)+(2k−1−1)m >= (k) + (2^{k - 1} - 1)

  • 注：当 n=1n = 1 时，k=0k = 0，区间 [2k−1,2k−1][2^{k - 1},2^k - 1] 不存在，需要额外考虑

对于区间 [1,2k−1−1][1, 2^{k - 1} - 1] 内，由于区间 [2k−1,2k−1][2^{k - 1},2^{k} - 1] 的数右移一位可以得到 [2k−2,2k−1−1][2^{k - 2}, 2^{k - 1} - 1] 的所有数，重复下去......

例如：[4,7]:[4, 7]: 100100，101101，110110，111111 全部右移一位 ⟹\Longrightarrow [2,3]:[2, 3]: 1010，1111

即：若 m<max(k+n−2k+1+1,k+2k−1−1)m < max(k + n-2^{k + 1} + 1,k + 2^{k - 1} - 1)，直接可以返回 false

由于 mm 最大为 10001000，则 nn 最大为 20132013

此时只需要判断区间 [2k,n][2^{k}, n] 与 [2k−1,2k−1][2^{k - 1}, 2^{k} - 1] 是否满足即可

  • 由于 [2k,n][2^k,n] 必然包含 [2k−1,n/2][2^{k - 1}, n / 2]，对于 [2k−1,2k−1][2^{k - 1}, 2^{k} - 1]，只需要从 n/2+1n/2 + 1 开始考虑是否满足即可
class Solution {
    public boolean queryString(String s, int n) {
        if (n == 1) {
            return s.contains("1");
        }
        int m = s.length();
        //k 为 n 的二进制的长度 - 1
        int k = 31 - Integer.numberOfLeadingZeros(n);
        if (m < Math.max(k + n - (1 << (k + 1)) + 1, k + (1 << (k - 1)) - 1)) {
            return false;
        }
        return helper(s, 1 << k, n, k + 1) && helper(s, n / 2 + 1, (1 << k) - 1, k);
    }
    public boolean helper(String s, int low, int high, int k) {
        if (low > high) {
            return true;
        }
        Set<Integer> set = new HashSet<>();
        // 初始化为二进制长度为 k - 1
        int x = Integer.parseInt(s.substring(0, k - 1), 2);
        int mask = (1 << (k - 1)) - 1;
        int m = s.length();
        for (int i = k - 1; i < m; i++) {
            // 去掉左边界 (即 x 的最高位): x & mask
            // 加入右边界:  << 1 | (s.charAt (i) - '0')
            x = ((x & mask) << 1) | (s.charAt(i) - '0');
            if (low <= x && x <= high) {
                set.add(x);
            }
        }
        return set.size() == high - low + 1;
    }
}
# 复杂度分析


    

  • 

    时间复杂度：O(m)O(m)，mm 为 ss 的长度
    

    • 

  • 

    空间复杂度：O(min(m,n))O(min(m,n))
    

    • 



# 暴力枚举 n


class Solution {
    public boolean queryString(String s, int n) {
        for (int i = 1; i <= n; i++) {
            if (!s.contains(Integer.toBinaryString(i))) {
                return false;
            }
        }
        return true;
    }
}
# 复杂度分析


    

  • 

    时间复杂度：O(min(m,n)⋅m log(min(m,n))O(min(m,n)\cdot m\,log(min(m,n))，mm 为 ss 的长度，由上述可知，最多循环 min(m,n)min(m,n) 次
    

    • 

  • 

    空间复杂度：O(log n)O(log\,n)
    

    •