redis布隆过滤器

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-07-27

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s1 string字符串vector 
     * @param s2 string字符串vector 
     * @param n int整型 
     * @return int整型vector
     */
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;
}
};

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s1 string字符串vector 
     * @param s2 string字符串vector 
     * @param n int整型 
     * @return int整型vector
     */
    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) {
        // write code here
        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;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2022-07-30

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s1 string字符串vector 
     * @param s2 string字符串vector 
     * @param n int整型 
     * @return int整型vector
     */
    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;
}
    
};

C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2022-07-27

class Solution {
public:
	/**
	 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
	 *
	 *
	 * @param s1 string字符串vector
	 * @param s2 string字符串vector
	 * @param n int整型
	 * @return int整型vector
	 */
	vector<int> BloomFilter(vector<string>& s1, vector<string>& s2, int n) {
		// write code here
		vector<int> ret;

		for (int i = 0; i < n; i++) {
			v_mod.push_back(10000 + rand() % 10001);
		}

		add(s1, n);
		for (auto& s : s2) {
            if (contains(s, n)) {
                ret.emplace_back(1);
            }else {
                ret.emplace_back(0);
            }
        }
        return ret;
	}

	int generate_key(int i, int mod, const string& str) {
		int key = 0;
		for (auto& c : str) {
			key = (i * key + c) % mod;
		}
		return key;
	}

	void add(vector<string>& s1, int n) {
		for (int i = 1; i <= n; i++) {
			for (auto& s : s1) {
				int k = generate_key(i, v_mod[i - 1], s);
				bits.set(k);
			}
		}
	}

	int contains(const string& s, int n) {
		for (int i = 1; i <= n; i++) {
			int k = generate_key(i, v_mod[i - 1], s);
			if (!bits[k]) {
				return 0;
			}
		}
		return 1;
	}

	std::bitset<20000> bits;
	vector<int> v_mod;
};

C++ 解法, 执行用时: 3ms, 内存消耗: 440KB, 提交时间: 2022-07-25

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s1 string字符串vector 
     * @param s2 string字符串vector 
     * @param n int整型 
     * @return int整型vector
     */
    
    set<string> st;
    vector<int> vec;
    int k=0;
    void init(int n)
    {
        k=n;
        for(int i=0;i<n;i++)
        {
            vec.push_back(10000+rand()%10001);
        }
    }
    void add(string s)
    {
        int key = 0;
        string str;
        for(int i=1;i<=k;i++) //共k个函数
        {
            for(int j=0;j<s.length();j++)
            {
                key = (i*key + (int)s[j])%vec[i-1];
            }
            str += to_string(key);
            str += ",";
            key = 0;
        }
        st.insert(str);

    }
    bool contains(string s)
    {
        int key = 0;
        string str;
        for(int i=1;i<=k;i++)
        {
            for(int j=0;j<s.length();j++)
            {
                key = (i*key + (int)s[j])%vec[i-1];
            }
            str += to_string(key);
            str += ",";
            key = 0;
                
        }
        if(st.find(str)!=st.end())
            return true;
        else
            return false;
    }
    
    
    vector<int> BloomFilter(vector<string>& s1, vector<string>& s2, int n) {
        // write code here
        init(n); //初始化n个布隆过滤器匹配函数
        vector<int> res;
        for(string s: s1)
        {
            add(s);
        }
        for(string s:s2)
        {
            if(contains(s))
                res.push_back(1);
            else
                res.push_back(0);
        }
        return res;

    }
};

详情