Keshawn_lu's Blog

Leetcode 1016. 子串能表示从 1 到 N 数字的二进制串

字符串
字数统计: 328阅读时长: 1 min
2023/05/11 Share

题目简介：

给定一个二进制字符串 s 和一个正整数 n，如果对于 [1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串** ，就返回 true，否则返回 false 。

子字符串 是字符串中连续的字符序列。

示例 1：

1
2
输入：s = "0110", n = 3
输出：true

提示：

  • 1 <= s.length <= 1000
  • s[i] 不是 '0' 就是 '1'
  • 1 <= n <= 10^9

思路：

利用unordered_set来存储遍历到的数。

当遇到s[i] = 0时，直接continue，因为例如s = "0110"，从s[0]和s[1]开始遍历，得到的结果是相同的。

当更新子串[i, j]的二进制数时，利用x = (x << 1) | (s[j] - '0')，使其能在O(1)的时间复杂度内完成。

即将x整体左移一位，并将最低位设置为s[j]。

最后判断unordered_set中的数字数量是否等于n即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:

    bool queryString(string s, int n) {

        unordered_set<int> set;

        for(int i = 0; i < s.size(); ++i){

            int x = s[i] - '0';

            if(x == 0)
                continue;

            set.insert(x);

            for(int j = i + 1; j < s.size(); ++j){

                x = (x << 1) | (s[j] - '0'); // 子串 [i,j] 的二进制数

                if(x > n)
                    break;

                set.insert(x);
            }
        }

        return set.size() == n;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网