题目说的比较模糊,让人不知道如何入手。可以先看一下布隆过滤器的原理,然后再入手做题。
不知道题意理解是否有误,如有错误欢迎指正~~
思路:
- 使用n个hash函数为每个string生成key,然后将key值对应的bit设置为1
- 遍历第二个输入数组,使用相同的hash函数为其生成对应的key,然后判断对应的bit是否为true,只要有一个不为true就说明该字符不存在
说明:
这里偷懒了一下,因为题目只说明了mod的范围为10000~20000,没有指明每个hash函数的mod,题目说是随机的,这里直接固定写成了10000,但不影响最终的结果~~~
代码很简单,如下:
#include <bits/stdc++.h>
using namespace std;
long generate_key(int i, long mod, const std::string &str)
{
long key = 0;
for (auto s : str)
{
key = (i * key + s) % mod;
}
return key;
}
vector<int> BloomFilter(vector<string> &s1, vector<string> &s2, int n)
{
std::bitset<10000> bs;
long mod = 10000;
for (auto &s : s1)
{
for (int i = 1; i <= n; ++i)
{
long key = generate_key(i, mod, s);
bs.set(key);
}
}
std::vector<int> ans;
for (auto &s : s2)
{
int flag = 1;
for (int i = 1; i <= n; ++i)
{
long key = generate_key(i, mod, s);
if (!bs[key])
{
flag = 0;
break;
}
}
ans.push_back(flag);
}
return ans;
}

京公网安备 11010502036488号