1016. Binary String With Substrings Representing 1 To N

Given a binary string S (a string consisting only of ‘0’ and ‘1’s) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

Example 1:

Input: S = "0110", N = 3
Output: true

Example 2:

Input: S = "0110", N = 4
Output: false

Note:

  1. 1 <= S.length <= 1000
  2. 1 <= N <= 10^9

这道题给了一个二进制的字符串S,和一个正整数N,问从1到N的所有整数的二进制数的字符串是否都是S的子串。没啥说的,直接上最简单粗暴的解法,验证从N到1之间所有的数字,先求出其二进制数的字符串,在 C++ 中可以利用 bitset 来做,将其转为字符串即可。由于定义了 32 位的 bitset,转为字符串后可能会有许多 leading zeros,所以首先要移除这些0,通过在字符串中查找第一个1,然后通过取子串的函数就可以去除所有的起始0了。然后在S中查找是否存在这个二进制字符串,若不存在,直接返回 false,遍历完成后返回 true 即可,参见代码如下:

class Solution {
public:
    bool queryString(string S, int N) {
        for (int i = N; i > 0; --i) {
            string b = bitset<32>(i).to_string();
            if (S.find(b.substr(b.find("1"))) == string::npos) return false;
        }
        return true;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1016

参考资料:

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/discuss/260847/JavaC%2B%2BPython-O(S)

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/discuss/260882/C%2B%2B-O(S-log-N)-vs.-O(N-*-(S-%2B-log-N))

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation