题解 | #redis布隆过滤器#
redis布隆过滤器
https://www.nowcoder.com/practice/1ea25727949c4945be2356a9e9569050
题目说的比较模糊，让人不知道如何入手。可以先看一下布隆过滤器的原理，然后再入手做题。
不知道题意理解是否有误，如有错误欢迎指正~~
思路：
- 使用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;
}
比亚迪工作强度 342人发布
投递哔哩哔哩等公司10个岗位