LC.P1016[子串能表示从1到N数字的二进制串]

方法一：暴力

1
2
3
4
5
6
7
8
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) \times mlogmin(m,n))$，其中$m$为s的长度。
  • 空间复杂度：$O(logn)$

方法二：数学+滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean queryString(String s, int n) {
        if (n == 1) return s.contains("1");
        int k = 31 - Integer.numberOfLeadingZeros(n);
        if (s.length() < Math.max(n - (1 << k) + k + 1, (1 << k - 1) + k + 1)) {
            return false;
        }
        return check(s, k, n / 2 + 1, (1 << k) - 1) && check(s, k + 1, 1 << k, n);
    }

    private boolean check(String s, int k, int low, int high) {
        if (low > high) return true;
        Set<Integer> visited = new HashSet<>();
        int mask = (1 << (k - 1)) - 1;
        int x = Integer.parseInt(s.substring(0, k - 1), 2), m = s.length();
        for (int i = k - 1; i < m; ++i) {
            x = ((x & mask) << 1) | (s.charAt(i) - '0');
            if (low <= x && x <= high) visited.add(x);
        }
        return visited.size() == high - low + 1;
    }
}
  • 时间复杂度：$O(m)$
  • 空间复杂度：$O(min(m,n))$