设计 - 《算法》 - 极客文档

1500. 设计文件分享系统

我们需要使用一套文件分享系统来分享一个非常大的文件，该文件由 m 个从 1 到 m 编号的文件块组成。
当用户加入系统时，系统应为其注册一个独有的 ID。这个独有的 ID 应当被相应的用户使用一次，但是当用户离开系统时，其 ID 应可以被（后续新注册的用户）再次使用。
用户可以请求文件中的某个指定的文件块，系统应当返回拥有这个文件块的所有用户的 ID。如果用户收到 ID 的非空列表，就表示成功接收到请求的文件块。

实现 FileSharing 类：

FileSharing(int m) 初始化该对象，文件有 m 个文件块。
int join(int[] ownedChunks)：一个新用户加入系统，并拥有文件的一些文件块。系统应当为该用户注册一个 ID，该 ID 应是未被其他用户占用的最小正整数。返回注册的 ID。
void leave(int userID)：ID 为 userID 的用户将离开系统，你不能再从该用户提取文件块了。
int[] request(int userID, int chunkID)：ID 为 userID 的用户请求编号为 chunkID 的文件块。返回拥有这个文件块的所有用户的 ID 所构成的列表或数组，按升序排列。

进阶：

当系统以用户的 IP 地址而不是独有 ID 来识别用户，且用户断开连接后以相同 IP 重新连接系统时，会发生什么？
当用户频繁加入并退出系统，且该用户不请求任何文件块时，你的解决方案仍然保持高效吗？
当所有用户同时加入系统，请求所有文件并离开时，你的解决方案仍然保持高效吗？
如果系统用于分享 n 个文件，其中第 i 个文件由 m[i] 组成，你需要如何修改？

示例:
输入: [“FileSharing”,”join”,”join”,”join”,”request”,”request”,”leave”,”request”,”leave”,”join”] [[4],[[1,2]],[[2,3]],[[4]],[1,3],[2,2],[1],[2,1],[2],[[]]] 输出: [null,1,2,3,[2],[1,2],null,[],null,1] 解释: FileSharing fileSharing = new FileSharing(4); // 我们用该系统分享由 4 个文件块组成的文件。 fileSharing.join([1, 2]); // 一个拥有文件块 [1,2] 的用户加入系统，为其注册 id = 1 并返回 1。 fileSharing.join([2, 3]); // 一个拥有文件块 [2,3] 的用户加入系统，为其注册 id = 2 并返回 2。 fileSharing.join([4]); // 一个拥有文件块 [4] 的用户加入系统，为其注册 id = 3 并返回 3。 fileSharing.request(1, 3); // id = 1 的用户请求第 3 个文件块，只有 id = 2 的用户拥有文件块，返回 [2] 。注意，现在用户 1 现拥有文件块 [1,2,3]。 fileSharing.request(2, 2); // id = 2 的用户请求第 2 个文件块，id 为 [1,2] 的用户拥有该文件块，所以我们返回 [1,2] 。 fileSharing.leave(1); // id = 1 的用户离开系统，其所拥有的所有文件块不再对其他用户可用。 fileSharing.request(2, 1); // id = 2 的用户请求第 1 个文件块，系统中没有用户拥有该文件块，所以我们返回空列表 [] 。 fileSharing.leave(2); // id = 2 的用户离开系统。 fileSharing.join([]); // 一个不拥有任何文件块的用户加入系统，为其注册 id = 1 并返回 1 。注意，id 1 和 2 空闲，可以重新使用。

提示:

1 <= m <= 10^5
0 <= ownedChunks.length <= min(100, m)
1 <= ownedChunks[i] <= m
ownedChunks 的值是互不相同的。
1 <= chunkID <= m
当你正确地注册用户 ID 时，题目保证 userID 是系统中的一个已注册用户。
join、 leave 和 request 最多被调用 10^4 次。
每次对 leave 的调用都有对应的对 join 的调用。

通过次数752
提交次数2,497

class FileSharing:
    def __init__(self, m: int):
        # 维护当前未被占用id
        self.leave_id = []
        self.id = 1
        # 记录每个文件的所有者id
        self.files = collections.defaultdict(set)
        # 记录每个id所拥有的文件
        self.user = collections.defaultdict(list)
    def join(self, ownedChunks: List[int]) -> int:
        if self.leave_id:
            id = heapq.heappop(self.leave_id)
        else:
            id = self.id
            self.id += 1
        for file in ownedChunks:
            self.user[id].append(file)
            self.files[file].add(id)
        return id
    def leave(self, userID: int) -> None:
        for file in self.user[userID]:
            self.files[file].remove(userID)
        self.user[userID] = []
        heapq.heappush(self.leave_id,userID)
    def request(self, userID: int, chunkID: int) -> List[int]:
        ans = list(v for v in self.files[chunkID])
        if not ans:
            return ans
        ans.sort()
        if userID not in self.files[chunkID]:
            self.files[chunkID].add(userID)
            self.user[userID].append(chunkID)
        return ans
# Your FileSharing object will be instantiated and called as such:
# obj = FileSharing(m)
# param_1 = obj.join(ownedChunks)
# obj.leave(userID)
# param_3 = obj.request(userID,chunkID)
作者：ZhonghaoWang
链接：https://leetcode-cn.com/problems/design-a-file-sharing-system/solution/py3-dui-hashmap-by-zhonghaowang-baxr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

731. 我的日程安排表 II

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。
当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。
每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。
请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar();MyCalendar.book(start, end)

示例：
MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(50, 60); // returns true MyCalendar.book(10, 40); // returns true MyCalendar.book(5, 15); // returns false MyCalendar.book(5, 10); // returns true MyCalendar.book(25, 55); // returns true 解释： 前两个日程安排可以添加至日历中。第三个日程安排会导致双重预订，但可以添加至日历中。第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订；时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。

提示：

每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。
调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。

通过次数4,022
提交次数7,954

错误代码

class MyCalendarTwo:

    def __init__(self):
        self.time = [0 for _ in range(10**5)]

    def book(self, start: int, end: int) -> bool:
        flag = False
        mark = 0
        for i in range(start, end):
            self.time[i] += 1
            if self.time[i] == 3:
                flag = True
                mark = i
                break
        if flag:
            for i in range(start, mark):
                self.time[i] -= 1
            return False
        return True

class MyCalendarTwo:

    def __init__(self):
        self.one = []
        self.two = []

    def book(self, start: int, end: int) -> bool:
        for i in self.two:
            s = max(start, i[0])
            e = min(end, i[1])
            if s < e:
                 return False
        for i in self.one:
            s = max(start, i[0])
            e = min(end, i[1])
            if s < e:
                self.two.append([s, e])
        self.one.append([start, end])
        return True


# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)

关键代码是一重中判断是否有交集需要插入到二重中，关键代码是:

if s < e:
    self.two.append([s, e])

插入的是 [s, e] 而不是[start, end]

参考
解题思路

区间求解。
维护一重和二重日程表。
如果当前预订的区间与二重日程表中任意区间有重合就返回False。
否则遍历一重日程表，把与当前日程重叠部分加入二重日程表，同时在一重日程表中添加当前日程。

作者：haoyuhu
链接：https://leetcode-cn.com/problems/my-calendar-ii/solution/731-wo-de-ri-cheng-an-pai-biao-ii-by-haoyuhu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class MyCalendarTwo:

    def __init__(self):
        self.calendars = []
        self.overlaps = []


    def book(self, start: int, end: int) -> bool:
        # print(self.calendars, self.overlaps)
        for ol in self.overlaps:
            s = max(start, ol[0])
            e = min(end, ol[1])
            if s < e:
                return False
        for i in range(len(self.calendars)):
            c = self.calendars[i]
            s = max(start, c[0])
            e = min(end, c[1])
            if s < e:
                self.overlaps.append([s, e])
        self.calendars.append([start, end])
        return True


# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)


作者：haoyuhu
链接：https://leetcode-cn.com/problems/my-calendar-ii/solution/731-wo-de-ri-cheng-an-pai-biao-ii-by-haoyuhu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

利用hashmap

class MyCalendarTwo {
    TreeMap<Integer,Integer> map = new TreeMap<>();
    public MyCalendarTwo() {

    }

    public boolean book(int start, int end) {
        map.put(start, map.getOrDefault(start, 0) + 1);
        map.put(end, map.getOrDefault(end, 0) - 1);
        int sum = 0;
        for(int v: map.values()){
            sum += v;
            if(sum >= 3){
                map.put(start, map.getOrDefault(start, 0) - 1);
                map.put(end, map.getOrDefault(end, 0) + 1);
                return false;
            }
        }
        return true;
    }
}

642. 设计搜索自动补全系统

为搜索引擎设计一个搜索自动补全系统。用户会输入一条语句（最少包含一个字母，以特殊字符 ‘#’ 结尾）。除 ‘#’ 以外用户输入的每个字符，返回历史中热度前三并以当前输入部分为前缀的句子。下面是详细规则：

一条句子的热度定义为历史上用户输入这个句子的总次数。
返回前三的句子需要按照热度从高到低排序（第一个是最热门的）。如果有多条热度相同的句子，请按照 ASCII 码的顺序输出（ASCII 码越小排名越前）。
如果满足条件的句子个数少于 3，将它们全部输出。
如果输入了特殊字符，意味着句子结束了，请返回一个空集合。

你的工作是实现以下功能：
构造函数：
AutocompleteSystem(String[] sentences, int[] times): 这是构造函数，输入的是历史数据。 Sentences 是之前输入过的所有句子，Times 是每条句子输入的次数，你的系统需要记录这些历史信息。
现在，用户输入一条新的句子，下面的函数会提供用户输入的下一个字符：
List input(char c): 其中 c 是用户输入的下一个字符。字符只会是小写英文字母（’a’ 到 ‘z’ ），空格（’ ‘）和特殊字符（’#’）。输出历史热度前三的具有相同前缀的句子。

样例：
操作： AutocompleteSystem([“i love you”, “island”,”ironman”, “i love leetcode”], [5,3,2,2])
系统记录下所有的句子和出现的次数：
“i love you” : 5 次
“island” : 3 次
“ironman” : 2 次
“i love leetcode” : 2 次
现在，用户开始新的键入：

输入： input(‘i’)
输出： [“i love you”, “island”,”i love leetcode”]
解释：
有四个句子含有前缀 “i”。其中 “ironman” 和 “i love leetcode” 有相同的热度，由于 ‘ ‘ 的 ASCII 码是 32 而 ‘r’ 的 ASCII 码是 114，所以 “i love leetcode” 在 “ironman” 前面。同时我们只输出前三的句子，所以 “ironman” 被舍弃。

输入： input(‘ ‘)
输出： [“i love you”,”i love leetcode”]
解释:
只有两个句子含有前缀 “i “。

输入： input(‘a’)
输出： []
解释：
没有句子有前缀 “i a”。

输入： input(‘#’)
输出： []
解释：
用户输入结束，”i a” 被存到系统中，后面的输入被认为是下一次搜索。

注释：

输入的句子以字母开头，以 ‘#’ 结尾，两个字母之间最多只会出现一个空格。
即将搜索的句子总数不会超过 100。每条句子的长度（包括已经搜索的和即将搜索的）也不会超过 100。
即使只有一个字母，输出的时候请使用双引号而不是单引号。
请记住清零 AutocompleteSystem 类中的变量，因为静态变量、类变量会在多组测试数据中保存之前结果。详情请看这里。

错误解答

class Word():
    def __init__(self):
        self.node = {}
        self.sentences = []

class AutocompleteSystem:

    def __init__(self, sentences: List[str], times: List[int]):
        self.root = Word()
        self.input_word = ""
        for i in range(len(sentences)):
            self.insert(sentences[i], times[i])

    def insert(self, word, count):
        temp = self.root
        for i in word:
            if i in temp.node:
                temp = temp.node[i]
            else:
                temp.node[i] = Word()
                temp = temp.node[i]
            temp.sentences.append([word, -count])

    def input(self, c: str) -> List[str]:
        if c == '#':
            self.insert(self.input_word, 1)
            self.input_word = ""
            return []
        self.input_word += c 
        temp = self.root
        for i in self.input_word:
            if i not in temp.node:
                return []
            temp = temp.node[i]
        words = temp.sentences
        res = sorted(words, key = lambda x : (x[1], x[0]))[:3]
        return [i[0] for i in res]



# Your AutocompleteSystem object will be instantiated and called as such:
# obj = AutocompleteSystem(sentences, times)
# param_1 = obj.input(c)

Word类中使用 self.sentences = [] 来保存当前单词的数量是不对的，因为在之后可以会插入同样的单词，同时新增count, 因此需要用map来维护这个单词的count数量

正确解答

from collections import defaultdict

class Word:
    def __init__(self):
        self.node = {}
        self.cur_word = defaultdict(int)

class AutocompleteSystem:

    def __init__(self, sentences: List[str], times: List[int]):
        self.input_word = ""
        self.prefix_tree = Word()
        for i in range(len(sentences)):
            self.insert(sentences[i], times[i])

    def insert(self, word, count):
        temp = self.prefix_tree
        for i in word:
            if i in temp.node:
                temp = temp.node[i]
            else:
                temp.node[i] = Word()
                temp = temp.node[i]
            temp.cur_word[word] -= count

    def input(self, c: str) -> List[str]:
        if c == '#':
            self.insert(self.input_word, 1)
            self.input_word = ""
            return []
        self.input_word += c
        temp = self.prefix_tree
        for i in self.input_word:
            if i not in temp.node:
                return []
            temp = temp.node[i]
        words = temp.cur_word
        words1 = sorted(words.items(), key=lambda x: (x[1], x[0]))[:3]
        res = [x[0] for x in words1]
        return res



# Your AutocompleteSystem object will be instantiated and called as such:
# obj = AutocompleteSystem(sentences, times)
# param_1 = obj.input(c)

855. 考场就座

在考场里，一排有 N 个座位，分别编号为 0, 1, 2, …, N-1 。
当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)
返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave(p) 时都保证有学生坐在座位 p 上。

示例：
输入：[“ExamRoom”,”seat”,”seat”,”seat”,”seat”,”leave”,”seat”], [[10],[],[],[],[],[4],[]] 输出：[null,0,9,4,2,null,5] 解释： ExamRoom(10) -> null seat() -> 0，没有人在考场里，那么学生坐在 0 号座位上。 seat() -> 9，学生最后坐在 9 号座位上。 seat() -> 4，学生最后坐在 4 号座位上。 seat() -> 2，学生最后坐在 2 号座位上。 leave(4) -> null seat() -> 5，学生最后坐在 5 号座位上。

提示：

1 <= N <= 10^9
在所有的测试样例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被调用 10^4 次。
保证在调用 ExamRoom.leave(p) 时有学生正坐在座位 p 上。

通过次数4,819
提交次数11,790

题解

class ExamRoom:

    def __init__(self, N):
        self.N = N
        # 记录学生的位置
        self.students = []

    def seat(self):
        # 还没有学生，直接坐在第一个位置
        if not self.students:
            student = 0
        else:
            # 有学生，要比较相邻学生之间的位置
            dist, student = self.students[0], 0
            for i, s in enumerate(self.students):
                if i:
                    prev = self.students[i - 1]
                    # 与前一个学生之间的中间的位置
                    d = int((s - prev) / 2)
                    # 记录最大的间隔，以及插入的位置
                    if d > dist:
                        dist, student = d, prev + d
            # 最后一个学生与最后一个位置的距离
            d = self.N - 1 - self.students[-1]
            if d > dist:
                student = self.N - 1
        # 按顺序插入学生的位置
        bisect.insort(self.students, student)
        return student

    def leave(self, p):
        self.students.remove(p)



# Your ExamRoom object will be instantiated and called as such:
# obj = ExamRoom(N)
# param_1 = obj.seat()
# obj.leave(p)


作者：skyland-2
链接：https://leetcode-cn.com/problems/exam-room/solution/ji-lu-yi-xia-by-skyland-2-naov/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

284. 窥探迭代器

请你设计一个迭代器，除了支持 hasNext 和 next 操作外，还支持 peek 操作。
实现 PeekingIterator 类：

PeekingIterator(int[] nums) 使用指定整数数组 nums 初始化迭代器。
int next() 返回数组中的下一个元素，并将指针移动到下个元素处。
bool hasNext() 如果数组中存在下一个元素，返回 true ；否则，返回 false 。
int peek() 返回数组中的下一个元素，但不移动指针。

示例：
输入： [“PeekingIterator”, “next”, “peek”, “next”, “next”, “hasNext”] [[[1, 2, 3]], [], [], [], [], []] 输出： [null, 1, 2, 2, 3, false] 解释： PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3] peekingIterator.next(); // 返回 1 ，指针移动到下一个元素 [1,2,3] peekingIterator.peek(); // 返回 2 ，指针未发生移动 [1,2,3] peekingIterator.next(); // 返回 2 ，指针移动到下一个元素 [1,2,3] peekingIterator.next(); // 返回 3 ，指针移动到下一个元素 [1,2,3] peekingIterator.hasNext(); // 返回 False

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
对 next 和 peek 的调用均有效
next、hasNext 和 peek 最多调用 1000 次

进阶：你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？

# Below is the interface for Iterator, which is already defined for you.
#
# class Iterator:
#     def __init__(self, nums):
#         """
#         Initializes an iterator object to the beginning of a list.
#         :type nums: List[int]
#         """
#
#     def hasNext(self):
#         """
#         Returns true if the iteration has more elements.
#         :rtype: bool
#         """
#
#     def next(self):
#         """
#         Returns the next element in the iteration.
#         :rtype: int
#         """

class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.iter = iterator
        self.pk = None

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        if self.pk is None:
            self.pk = self.iter.next()
        return self.pk

    def next(self):
        """
        :rtype: int
        """
        if self.pk is not None:
            val = self.pk 
            self.pk = None 
            return val
        return self.iter.next()

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.pk is not None or self.iter.hasNext()

# Your PeekingIterator object will be instantiated and called as such:
# iter = PeekingIterator(Iterator(nums))
# while iter.hasNext():
#     val = iter.peek()   # Get the next element but not advance the iterator.
#     iter.next()         # Should return the same value as [val].

剑指 Offer II 058. 日程表

请实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。
当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。
每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。
请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar();MyCalendar.book(start, end)

示例:

输入:
["MyCalendar","book","book","book"]
[[],[10,20],[15,25],[20,30]]
输出: [null,true,false,true]
解释: 
MyCalendar myCalendar = new MyCalendar();
MyCalendar.book(10, 20); // returns true 
MyCalendar.book(15, 25); // returns false ，第二个日程安排不能添加到日历中，因为时间 15 已经被第一个日程安排预定了
MyCalendar.book(20, 30); // returns true ，第三个日程安排可以添加到日历中，因为第一个日程安排并不包含时间 20 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fi9suh
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

提示：

每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。
0 <= start < end <= 109

class MyCalendar:

    def __init__(self):
        self.arr = []

    def book(self, start: int, end: int) -> bool:
        self.arr.append((start, 1))
        self.arr.append((end, -1))
        # self.arr.sort(key= lambda x : (x[0], -x[1]))
        self.arr.sort()
        cur = 0
        for time, num in self.arr:
            cur += num
            if cur > 1 :
                self.arr.remove((start, 1))
                self.arr.remove((end, -1))
                return False
        return True

1286. 字母组合迭代器

请你设计一个迭代器类，包括以下内容：

一个构造函数，输入参数包括：一个 有序且字符唯一 的字符串 characters（该字符串只包含小写英文字母）和一个数字 combinationLength 。
函数 next() ，按 字典序 返回长度为 combinationLength 的下一个字母组合。
函数 hasNext() ，只有存在长度为 combinationLength 的下一个字母组合时，才返回 True；否则，返回 False。

示例：
CombinationIterator iterator = new CombinationIterator(“abc”, 2); // 创建迭代器 iterator iterator.next(); // 返回 “ab” iterator.hasNext(); // 返回 true iterator.next(); // 返回 “ac” iterator.hasNext(); // 返回 true iterator.next(); // 返回 “bc” iterator.hasNext(); // 返回 false

提示：

1 <= combinationLength <= characters.length <= 15
每组测试数据最多包含 10^4 次函数调用。
题目保证每次调用函数 next 时都存在下一个字母组合。

import heapq
import itertools
class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.arr = list(itertools.combinations(characters, combinationLength))
        heapq.heapify(self.arr)
        self.n = combinationLength

    def next(self) -> str:
        temp = heapq.heappop(self.arr)
        ans = "".join(temp)
        return ans

    def hasNext(self) -> bool:
        return len(self.arr) > 0

2080. 区间内查询数字的频率

请你设计一个数据结构，它能求出给定子数组内一个给定值的频率。
子数组中一个值的频率指的是这个子数组中这个值的出现次数。
请你实现 RangeFreqQuery 类：

RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
int query(int left, int right, int value) 返回子数组 arr[left…right] 中 value 的频率。

一个 子数组 指的是数组中一段连续的元素。arr[left…right] 指的是 nums 中包含下标 left 和 right 在内的中间一段连续元素。

示例 1：
输入： [“RangeFreqQuery”, “query”, “query”] [[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]] 输出： [null, 1, 2] 解释： RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]); rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。 rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。

提示：

1 <= arr.length <= 105
1 <= arr[i], value <= 104
0 <= left <= right < arr.length
调用 query 不超过 105 次。

from collections import defaultdict
import bisect
class RangeFreqQuery:

    def __init__(self, arr: List[int]):
        self.maps = defaultdict(list)
        for idx, n in enumerate(arr):
            self.maps[n].append(idx)
        for k, v in self.maps.items():
            v.sort()

    def query(self, left: int, right: int, value: int) -> int:
        temp = self.maps[value]
        l = bisect.bisect_left(temp, left)
        r = bisect.bisect_right(temp, right)
        return r - l