子串能表示从 1 到 N 数字的二进制串 图解题解

s 里要翻得出 1 到 n 每个数的二进制

题目给一个只含 0 和 1 的字符串 s 和一个正整数 n。要把 1、2 一直到 n 每个数写成二进制，看它们是不是都能在 s 里找到一段连续字符跟它一模一样——子串就是连续的一段、中间不能断。全找得到返回 true，有一个找不到就 false。题面 s=0110、n=3 返回 true（1、10、11 都在），n=4 返回 false（4 的 100 找不到）。

从 1 挨个查到 n，n 一大这法子还扛得住吗

从 1 到 n 一个个查：把数字转成二进制，去 s 里搜有没有这一段。麻烦在 n 可以很大，逐个搜像没尽头。但有个硬上限压着——(n/2, n] 这半段的数都大于 n/2，两串若从 s 同一处起头，短的必是长的前缀；可这里谁翻倍都越过 n、互不为前缀，就只能各占 s 里一个不同起点。s 一共才 |s| 个起点，n 一旦超过 2 倍 |s| 便塞不下、必有一个落空，直接返回 false。真正要查的 n 顶多 2|s|，两千以内。

为什么只查后半段的数，前半段能整段跳过

更省的一刀是：连 1 到 n/2 这下半段都不用查。任取一个 x≤n/2，把它的二进制末尾不断补 0（等于每次翻倍），迟早会落进 (n/2, n] 得到某个 y；而 bin(x) 正好是 bin(y) 砍掉末尾那几个 0 剩下的前缀。只要 y 的二进制是 s 的子串，它开头那一截 bin(x) 自然也在 s 里。所以下半段每个数都被上半段某个数顺带盖住了，只需验 (n/2, n] 上半段就够，检查量砍半。

先短路，再逐个转二进制拿窗口在 s 上滑

合起来的流程很短。先短路：n 大于 2 倍 |s| 直接判 false。否则从 n 往下数到 n/2+1，逐个取它的最短二进制（去掉 0b 前缀、不带前导零），拿这段定宽的模式在 s 上从左往右滑，一格一格比，看有没有哪一段和它完全相同。中途任意一个数在 s 里滑到头都没配上，立刻返回 false；上半段全部配上，才返回 true。

s=0110、n=3，看 1 是怎么被顺带盖掉的

拿题面 s=0110、n=3 走一遍。2 倍 |s| 是 8，n=3 没超，不短路。n/2=1，要查 3 和 2。先看 3，二进制 11，滑宽 2 的窗口：01 不是、11 对上（下标 1 到 2）。再看 2，二进制 10，滑到下标 2 到 3 截出 10，配上。上半段都在，返回 true——1 全程没查，它的二进制 1 是 2 的 10 的前缀，顺带盖掉。若 n 换成 4，多出的 4 是 100，滑宽 3 只截得出 011、110，没有 100，直接返回 false。

二进制取最短那版，带着前导零就和 s 对不上

几处一错就整道判反。二进制一定取最短那版：Python 用 bin(i)[2:] 去掉 0b、C++ 砍掉前导零；留着前导零就和 s 里的子串对不上，本能找到的数会被漏判。也别只顾逐个查而丢了砍半——下半段是上半段前缀，只验 (n/2, n]。还有几个边界：s 只有一个 0、n=1 时里头没有 1，返回 false；s 里有个 1、n=1 就已满足；n 超过 2 倍 |s| 直接出局。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def queryString(self, s: str, n: int) -> bool:
        if n > 2 * len(s):
            return False
        return all(bin(i)[2:] in s for i in range(n, n // 2, -1))

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    bool queryString(string s, int n) {
        if (n > 2 * (int)s.size()) {
            return false;
        }
        for (int i = n; i > n / 2; --i) {
            string b = bitset<32>(i).to_string();
            b = b.substr(b.find_first_not_of('0'));
            if (s.find(b) == string::npos) {
                return false;
            }
        }
        return true;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public boolean queryString(String s, int n) {
        if (n > 2 * s.length()) {
            return false;
        }
        for (int i = n; i > n / 2; i--) {
            if (!s.contains(Integer.toBinaryString(i))) {
                return false;
            }
        }
        return true;
    }
}