py3中 collections 的常用STL

对于这个工具包非常好用，尤其是其中的 Counter() 函数 使用次数颇为频繁，现在对collections中的一些常用的容器函数进行梳理总结。
主要包括：
Counter() 函数，defaultdict() 函数，deque() 函数,orderedDict() 函数。将结合一些LC上的例题进行一个简单总结。
参考文档链接为：https://docs.python.org/3.8/library/collections.html

Counter() 函数

Counter() 函数功能非常强大，主要用于是计算散列对象的dict子类，有点抽象，也不知道百度翻译说的对不对，原为是：dict subclass for counting hashable objects，Counter()函数下的函数方法最常用的是：elements() 方法、most_common()方法，另外像 values() ，items()，del等，都非常实用，具体可以参见 Counter的文档。在此就不举例了，LC的例题将选择一道既包含Counter()，又包含defaultdict()的困难题。

defaultdict() 函数

dict subclass that calls a factory function to supply missing values，一个强大的字典存储器，有点像C++中的自定义数据类型。非常好用，也非常常用，常用的内置函数主要有：append()、items()、values()，具体参见defaultdict文档。

举一个LC上的例题：
题目链接：895. 最大频率栈
题目大意：设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
实现 FreqStack 类:

• FreqStack() 构造一个空的堆栈。
• void push(int val) 将一个整数 val 压入栈顶。
• int pop() 删除并返回堆栈中出现频率最高的元素。如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。

注意：（1）0 <= val <= 10⁹；（2）push 和 pop 的操作数不大于 2 * 10⁴；（3）输入保证在调用 pop 之前堆栈中至少有一个元素。

示例：

输入：
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
FreqStack = new FreqStack();
freqStack.push (5);//堆栈为 [5]
freqStack.push (7);//堆栈是 [5,7]
freqStack.push (5);//堆栈是 [5,7,5]
freqStack.push (7);//堆栈是 [5,7,5,7]
freqStack.push (4);//堆栈是 [5,7,5,7,4]
freqStack.push (5);//堆栈是 [5,7,5,7,4,5]
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。
freqStack.pop ();//返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。
freqStack.pop ();//返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。

参考代码：

class FreqStack:def __init__(self):# 设置三个变量 ： （1）计频；（2）记元素；（3）固定最大频次。self.counter = collections.Counter()self.hash_map = collections. defaultdict(list)self.max_freq = 0def push(self, x: int) -> None:f = self.counter[x]+1self.counter[x] = fif f > self.max_freq:self.max_freq = f self.hash_map[f].append(x)def pop(self) -> int:x = self.hash_map[self.max_freq].pop()self.counter[x] -= 1if not self.hash_map[self.max_freq]:self.max_freq -= 1return x# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()

deque() 函数

list-like container with fast appends and pops on either end双头队列，在处理广度优先遍历、排序问题中非常常见，常用的内置函数方法有：append()，pop()，popleft() 等，具体参见deque文档。

举一个LC上的例题：
题目链接：933. 最近的请求次数
题目大意：
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0 。
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
• 保证 每次对 ping 的调用都使用比之前更大的 t 值。

注意：（1）1 <= t <= 10⁹；（2）保证每次对 ping 调用所使用的 t 值都 严格递增；（3）至多调用 ping 方法 10⁴ 次。

示例：

输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

参考代码：

class RecentCounter:def __init__(self):self.q = deque()def ping(self, t: int) -> int:self.q.append(t)while self.q[0] < t-3000:self.q.popleft()return len(self.q)# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)

orderedDict() 函数（缺例题）

dict subclass that remembers the order entries were added保留源字符串的顺序进行对应弹出或移动操作，这个我是用的不多，遇到后再补充吧。

举一个LC上的例题：
题目链接：
题目大意：
注意：
示例：
参考代码：

在这里插入代码片

小结

 总算把一些想整理的东西弄得差不多了，接下来要对以往学习的东西进行梳理，同时准备下一阶段的学习了，未来怎么走仍然充满可能性，相信可能性是个好东西吧！