数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中检查字符串是否包含大小为 K 的所有二进制代码
假设我们有一个二进制字符串 s 和一个整数 k。我们必须检查长度为 k 的每个二进制代码是否都是 s 的子字符串。否则，返回 False。
因此，如果输入类似于 S = "00110110"，k = 2，则输出将为 true。长度为 2 的二进制代码为“00”、“01”、“10”和“11”。它们分别位于索引 0、1、3 和 2 处。
要解决此问题，我们将遵循以下步骤：
定义一个集合 v
temp := 空字符串
req := 2^k
初始化 i := 0，当 i < s 的大小，更新（i 增加 1），执行：
temp := temp + s[i]
如果 i >= k，则：
从 temp 的第一个索引删除一个字符
如果 i >= k - 1，则：
将 temp 插入 v
如果 v 的大小与 req 相同，则：
返回 true
返回 false
示例
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli fastPow(lli b, lli p){
lli ret = 1;
while (p) {
if (p & 1) {
ret *= b;
}
b *= b;
p >>= 1;
}
return ret;
}
bool hasAllCodes(string s, int k) {
unordered_set<string> v;
string temp = "";
lli req = fastPow(2, k);
for (lli i = 0; i < s.size(); i++) {
temp += s[i];
if (i >= k) {
temp.erase(0, 1);
}
if (i >= k - 1) {
v.insert(temp);
}
if ((lli)v.size() == req)
return true;
}
return false;
}
};
main(){
Solution ob;
cout << (ob.hasAllCodes("00110110",2));
}输入
"00110110",2
输出
1
更新于： 2020-11-18
192 次浏览
广告