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

这道题到底在问什么

输入

s="0110", n=3

输出

true（1=1、2=10、3=11 都在 0110 里）

输入

s="0110", n=4

输出

false（4=100 在 0110 里找不到）

先想最直接的笨办法

先把 s 等于 100110100 摆好，下标 0 到 8。右边清单列着 1 到 5 各自的二进制，现在全是「待查」。我们一个一个来，把它们的二进制都在 s 里找一遍。（动画第 4 步）

最优解：一步一步想明白

1. 3记住这套:逐个数字转二进制，再用一个等长窗口在 s 上滑动找它。一个找不到就出局，全找到才算 true。下面每帧都在套它。
2. 4先把 s 等于 100110100 摆好，下标 0 到 8。右边清单列着 1 到 5 各自的二进制，现在全是「待查」。我们一个一个来，把它们的二进制都在 s 里找一遍。
3. 5轮到数字 1，它的二进制是 1，一共 1 位。接下来用一个宽 1 的窗口，从 s 最左边开始往右滑，看哪一段正好是 1。
4. 6窗口滑到 [0, 0]，框住的是 1，正好等于目标 1，命中！数字 1 在 s 里确实出现，这一段标绿。
5. 7数字 1 搞定，它的二进制 1 落在 s 的 [0, 0] 这段。右边清单给 1 打上勾，目前 1 个都找到了，接着查下一个。
6. 8轮到数字 2，它的二进制是 10，一共 2 位。接下来用一个宽 2 的窗口，从 s 最左边开始往右滑，看哪一段正好是 10。
7. 9窗口滑到 [0, 1]，框住的是 10，正好等于目标 10，命中！数字 2 在 s 里确实出现，这一段标绿。
8. 10数字 2 搞定，它的二进制 10 落在 s 的 [0, 1] 这段。右边清单给 2 打上勾，目前 2 个都找到了，接着查下一个。
9. 11轮到数字 3，它的二进制是 11，一共 2 位。接下来用一个宽 2 的窗口，从 s 最左边开始往右滑，看哪一段正好是 11。
10. 12窗口在 [0, 1]，框住的是 10，和目标 11 不一样，没命中。窗口整体往右挪一格，继续比。
11. 13窗口在 [1, 2]，框住的是 00，和目标 11 不一样，没命中。窗口整体往右挪一格，继续比。
12. 14窗口在 [2, 3]，框住的是 01，和目标 11 不一样，没命中。窗口整体往右挪一格，继续比。
13. 15窗口滑到 [3, 4]，框住的是 11，正好等于目标 11，命中！数字 3 在 s 里确实出现，这一段标绿。
14. 16数字 3 搞定，它的二进制 11 落在 s 的 [3, 4] 这段。右边清单给 3 打上勾，目前 3 个都找到了，接着查下一个。
15. 17轮到数字 4，它的二进制是 100，一共 3 位。接下来用一个宽 3 的窗口，从 s 最左边开始往右滑，看哪一段正好是 100。
16. 18窗口滑到 [0, 2]，框住的是 100，正好等于目标 100，命中！数字 4 在 s 里确实出现，这一段标绿。
17. 19数字 4 搞定，它的二进制 100 落在 s 的 [0, 2] 这段。右边清单给 4 打上勾，目前 4 个都找到了，接着查下一个。
18. 20轮到数字 5，它的二进制是 101，一共 3 位。接下来用一个宽 3 的窗口，从 s 最左边开始往右滑，看哪一段正好是 101。
19. 21窗口在 [0, 2]，框住的是 100，和目标 101 不一样，没命中。窗口整体往右挪一格，继续比。
20. 22窗口在 [1, 3]，框住的是 001，和目标 101 不一样，没命中。窗口整体往右挪一格，继续比。
21. 23窗口在 [2, 4]，框住的是 011，和目标 101 不一样，没命中。窗口整体往右挪一格，继续比。
22. 24窗口在 [3, 5]，框住的是 110，和目标 101 不一样，没命中。窗口整体往右挪一格，继续比。
23. 25窗口滑到 [4, 6]，框住的是 101，正好等于目标 101，命中！数字 5 在 s 里确实出现，这一段标绿。
24. 26数字 5 搞定，它的二进制 101 落在 s 的 [4, 6] 这段。右边清单给 5 打上勾，目前 5 个全部找到，没有下一个了，进入总判断、准备返回 true。
25. 271 到 5 全都在 s 里找到了二进制对应的子串，清单一个不漏全打了勾。没有任何一个数字落空，所以答案是 true。要是中途有一个找不到，那一刻就该直接返回 false。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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))

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问