2022-6-26 第三期 哈希表的妙用（一）

• 前言
• 一、题目大意
• 二、解题思路
• 三、总结

这个专栏好久没有更新了，最近打算把刷过的一些题目给汇总一下，感觉动态规划、哈希表以及二分法特别常见，但每一块内容居多，因此我打算写成打分块中的小分块来对其总结，总之勤耕-勤更！

提示：以下是本篇文章正文内容，下面案例可供参考

  这是一道随机黑名单的题目，具体的内容可以直接去LC看一下，这里就不多描述了，这道题中文题目特别容易懵，可以看一下英文的解释，结合提供的题例可以大致理解为：给一个range(n)以及blacklist，随机获取range(n)中不含blacklist的元素。

• 710. Random Pick with Blacklist

   一幅图解

   python代码：

class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        # construct a dict like this:
        # 0 1 2 3 4 5 6
        # 0 1 4 6 2 3 5
        m = len(blacklist)
        self.bound = n-m
        self.map = {}
        blackNotInWhite = {b for b in blacklist if b >= self.bound} 
        i = self.bound
        for black in blacklist:
            # 在白名单区域的需要映射黑名单区域中可选的元素
            if black < self.bound:
                while i in blackNotInWhite:
                    i += 1
                # 白名单区域的不可选元素映射黑名单区域的可选元素
                self.map[black] = i
                # 记着加一
                i += 1

    def pick(self) -> int:
        x = random.randrange(self.bound)
        # 白名区域的不可选元素的值如果选到就返回，而剩余的没有值的元素返回自身即可
        # 这 get函数委实让人脑壳疼
        return self.map.get(x,x)

# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()

  后续只需更新，等内容差不多了再写几个总篇归纳一下。