LeetCode 1016. 子串能表示从 1 到 N 数字的二进制串
原题链接
中等
作者:
胡歌-此生不换
,
2022-09-23 22:46:52
,
所有人可见
,
阅读 131
解题思路
- 用 unordered_set[HTML_REMOVED] hash; 存储字符串 s 能够表示的整数。
- 再枚举每一个数(1–n) 是否在 hash 里面有,hash.count(i) == 0 表示 i 在 hash 里面出现的次数是 0 次。
时间复杂度 O(s.size() * 30)
代码
class Solution {
public:
bool queryString(string s, int n)
{
unordered_set<int> hash;
// 最大的时间复杂度是 1000 * 30 (2 的 30 次方这个数, 比1 <= n <= 109 大)
for(int i = 0; i < s.size(); i++)
{
int x = 0;
for(int j = i; j < s.size(); j++)
{
x = x * 2 + s[j] - '0';
if(x > n) break;
if(x > 0) hash.insert(x);
}
}
// 再枚举 1 - n 的数是否在 hash 里面出现过
for(int i = 1; i <= n; i++)
if(hash.count(i) == 0)
return false;
return true;
}
};