LeetCode——子串能表示从 1 到 N 数字的二进制串

逃离我推掉我的手 2023-09-27 21:22 12阅读 0赞

[1016. 子串能表示从 1 到 N 数字的二进制串 - 力扣（Leetcode）][1016. _ 1 _ N _ - _Leetcode]

**目录**

一、题目

二、题目解读

三、代码

--------------------

## 一、题目 ##

给定一个二进制字符串 `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`⁹

## 二、题目解读 ##

> 1、暴力Ⅰ
> 
> 我们可以遍历1到n看是否其二级制是s的子字符串。在这个过程我们可以进行倒序进行判断，先判断较大的数。
> 
> 可能有人会说这样不会超时吗？
> 
> 举例说明。如果 n=7，单看闭区间 \[4,7\]，有 4 个互不相同的整数，它们的二进制长度均为 3。如果要让字符串 s 包含这 4 个数，s 中至少要有 4 个长为 3 的互不相同的子串。考虑到这些子串可以有重叠部分，设 s 的长度为 m，则应满足 m≥3+(4−1)=6，否则直接返回false。（想象一个长为 3 的滑动窗口在 s 中滑动，至少要得到 4 个子串。）随着 n 的变大，m 的长度也应当随之变大。本题 m 至多为 1000，而 n 却高达 10⁹ 。
> 
> 所有如果 n≥2014n，可以直接返回 `false`。
> 
> Ⅱ、
> 
> 反过来想，把 s 的子串都转成二进制数，如果数字在 \[1,n\] 内，就保存到一个哈希表中。如果哈希表的大小最终为 n，就说明 \[1,n\] 的二进制都在 s 里面。
> 
> 2、滑动窗口
> 
> 1、根据 n 和 m（字符串长度） 的值来提前判断是否要返回 false。  
> 2、只需要考虑长为 k 和 k+1 的这两组二进制数 s 是否都有，因此可以用长为 k 和 k+1 的滑动窗口实现，从而做到线性时间复杂度。  
> 3、进一步地，由于区间 \[2ᴷ,n\] 内的所有数右移一位可以得到区间 \[2ᴷ⁻¹,n/2 \]，所以对于 \[2ᴷ⁻¹,2ᴷ−1\]，只需从 n/2+1 开始考虑。

## 三、代码 ##

代码Ⅰ

class Solution {
        public boolean queryString(String s, int n) {
            for (int i = n; i >= 1; i--) {
                if (!s.contains(Integer.toBinaryString(i))) {
                    return false;
                }
            }
            return true;
        }
    }

代码Ⅱ

class Solution {
        public boolean queryString(String S, int n) {
            HashSet<Integer> set = new HashSet<>();
            char[] s = S.toCharArray();
            for (int i = 0, m = s.length; i < m; ++i) {
                int x = s[i] - '0';
                if (x == 0) continue; // 二进制数从 1 开始
                for (int j = i + 1; x <= n; j++) {
                    set.add(x);
                    if (j == m) break;
                    x = (x << 1) | (s[j] - '0'); // 子串 [i,j] 的二进制数
                }
            }
            return set.size() == n;
        }
    }

滑动窗口

class Solution {
        public boolean queryString(String s, int n) {
            if (n == 1)
                return s.contains("1");
    
            int k = 31 - Integer.numberOfLeadingZeros(n); // 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);
        }
    
        // 对于长为 k 的在 [lower, upper] 内的二进制数，判断这些数 s 是否都有
        private boolean check(String s, int k, int lower, int upper) {
            if (lower > upper) return true;
            var seen = new HashSet<Integer>();
            int mask = (1 << (k - 1)) - 1;
            int x = Integer.parseInt(s.substring(0, k - 1), 2);
            for (int i = k - 1, m = s.length(); i < m; i++) {
                // & mask 可以去掉最高比特位，从而实现滑窗的「出」
                // << 1 | (s.charAt(i) - '0') 即为滑窗的「入」
                x = ((x & mask) << 1) | (s.charAt(i) - '0');
                if (lower <= x && x <= upper)
                    seen.add(x);
            }
            return seen.size() == upper - lower + 1;
        }
    }

**超详细题解可看**

[1016. 子串能表示从 1 到 N 数字的二进制串 - 力扣（Leetcode）][1016. _ 1 _ N _ - _Leetcode 1]

[1016. _ 1 _ N _ - _Leetcode]: https://leetcode.cn/problems/binary-string-with-substrings-representing-1-to-n/description/
[1016. _ 1 _ N _ - _Leetcode 1]: https://leetcode.cn/problems/binary-string-with-substrings-representing-1-to-n/solutions/2265097/san-chong-suan-fa-cong-bao-li-dao-you-hu-nmtq/