语法细节，数据结构，使用时容易出错的和忽略的地方
之python篇
了解 熟悉 ==掌握== 精通
if len(heap) < k:
heapq.heappush(heap, x)
else:
heapq.heappushpop(heap, x)
return heap[0]
# 1. 插入：[list].insert
是插入原list，而不是返回新list
有两个参数，[list].insert([值], [位置])
# 2. str｜list 通用｜有区别的参数
in str和list都可以用。
find 和 index:
① find 只可以用在 str，不存在会返回-1；
② index可用在str和list，不存在会error；
# 3. 判断list是否相等
① 必须位置、值全相等才算相等
② 可以使用 operator
import operator
operator.eq(a, b)
对象创建后hash值在生命周期里不可变
可hash：不可变的数据结构 str tuple object
不可hash：可变的数据结构 list dict set
使用hash算法的数据结构叫hash表，也叫散列表。
# 4. 相等
is：值和地址都相等
==：只有值相等
__eq__：和==一样。即引用相等。
__hash__：返回一个int值：hash(id(self))，为这个对象设定一个唯一hash值
set 去重
① 当两个变量hash值不同，就认为两个变量不同
② 当两个变量hash值一样时，调用__eq__方法，true去重，false不去。
# 5. 时间开销
默认长度皆为n。k代表随机。x是随便一个字符。
LIST：
.append() O(1)
.pop() O(1)
.pop[k] O(k)
.insert() O(n)
.extend() O(k)
.index() O(n) # 返回alsit里【第一个】astr的序列号
[x] in O(n)
min()/max() O(n)
len() O(1)
SET/DICT：
in 平均 1 | 最差 n
get 平均 1 | 最差 n
set 平均 1 | 最差 n
del 平均 1 | 最差 n
* 最坏是因为摊销 *
* ep: dic[N]，删除N-1个元素，会重新为N个元素调整大小 *
# 6. 删除
LIST：
.pop(索引)
.remove(值)
del list[索引]
DICT：
.pop(key) O(1)
.popitem() 【随机】
del dict[key]
.clear() 【删所有】
SET：
.pop() 【随机】 O(1)
.remove(值) O(1)
.discard(值)
其中，
list的.remove(值)为删除首个该值；
dict的 del dict[key]没有返回值，.pop(key)有返回值。
# 7. random
.randint(i, j) # [i, j] 范围内整数。**注意是闭区间**
.random() # 0-1间浮点数
.uniform(i, j) # [i, j] 范围内浮点数
.choice(str)
.randrange(i, j, gap)
.shuffle() # 打乱原函数
# 8. 堆
import heapq # 默认是小顶堆/最小堆 min_heap,也就是堆顶元素始终是堆中最小的元素
大顶堆就是根最大。小顶堆就是根最小。
import heapq # 它是小顶堆/最小堆 min_heap,也就是堆顶元素始终是堆中最小的元素
1. 创建：
heap = []
for n in data:
heapq.heappush(heap, n) # heap要提前创建个list
或者：
heapq.heapify(data) # data本身就变成堆
2. 弹出：
heapq.heapify(data)
for i in range(2):
smallest = heapq.heappop(data)
3. 删除并替换成新值
heapq.heapify(data)
for n in [0, 13]:
smallest = heapq.heapreplace(data, n)
# 在一个操作中将num添加到堆并从heap中删除最小项
heapq.heappushpop(heap, num)
4. 找范围
heapq.nlargest(3, data) # 最大的前3个 按从大到小
heapq.nsmallest(3, data) # 最小的前3个 按从小到大
5. 找第k
找第k大的元素，用小顶堆。因为当 len(list)>=k时，再进去值时，被替换出来的是堆顶=【最小的值】。
所以当循环完了之后，里面剩的是最大的k个值，且第k个是堆里最小的。
找第k小的元素，用大顶堆。pushpop出的是堆定=最大的值。完之后剩的是最小的k个值
模板：
if len(heap) < k:
heapq.heappush(heap, x)
else:
heapq.heappushpop(heap, x)
return heap[0]
**创建大顶堆和大顶堆排序不一样。**
大顶堆排序 = 创建大顶堆 + 不断交换 n[0] 和 n[-1]，并重复创建剩下的数为大顶堆。
创建大顶堆关键：找出最后一个有子树的i = len(n) // 2 - 1
# 9. 队列 queue
四种队列
queue.Queue ｜ 面向多生产/多消费线程的队列
asyncio.Queue ｜ 面向多生产/多消费协程的队列
multiprocessing.Queue ｜ 面向多生产/多消费进程的队列
collections.deque ｜ 在数据结构层面实现队列，无应用场景的基础数据结构
① collections.deque
一般做数据结构就用这种
from collections import deque
# 初始化
queue = deque(maxlen=10)
queue可原地初始化
q = queue(alist) | queue('astring')
添加：O(1)
.append(元素) ｜ .appendleft(元素)
.extend(数组) ｜ .extendleft(数组)
插入：O(n)
insert(index, 值)
弹出：O(1)
.pop() | .popleft()
往后挪k个：
.rotate(k) # k为正值为顺时针旋转，k为负值为逆时针旋转
可以使用 in
**线程安全**
以上都是原子操作，是GIL保护下的线程安全方法
② queue.Queue VS asyncio.Queue
共性：
都支持多生产者、多消费者的队列
基于collections.deque
都提供了Queue（FIFO队列），PriorityQueue（优先级队列），LiftQueue（LIFO队列）
区别：
queue.Queue 适用多线程场景
asyncio.Queue 适用协程场景下的通信，返回协程对象
| | queue.Queue | asyncio.Queue |
| ---- | ---- | ---- |
| 线程安全 | ✔︎ | ✘ |
| 超时机制 | timeout | asyncio.wait.for() |
| qsize() | 预估的队列长度（可能被其它线程修改） | 准确的队列长度（单线程，不会被其它线程修改）|
| put()/set() | put(item, block=true,timeout=None) | put()返回协程对象，so无block/timeout。非阻塞方法：put_nowait |
③ multiprocessing.Queue
三种队列：Queue . simpleQueue . JoinableQueue
线程安全 & 进程安全
支持put/get 操作
底层结构是multiprocessing Pipe
不支持join()和task_done操作
# 10. 树
完全二叉树：中间没有空的，按顺序排列
平衡二叉树：左右子树深不超过1
二叉搜索树 = 二叉排序树：左 < 中 < 右
满二叉树：这样行满了的完全二叉树。深度为k，且有2^k-1个结点。
字典树：
① 根节点不包含字符
② 子 = 父 + 路径
③ 子节点各不相同
④ 是现实，会在节点中是一个flag，标记该节点处是否构成一个单词
# 11. 读写
❗️ 读时最好用逐行方式，否则容易撑爆内存。
# 逐行读
with open("your_file.txt", "r") as file:
for line in file:
print(line, end="")
# 一次性读
with open("your_file.txt", "r") as file:
content = file.read()
print(content)
# 一次性写
file = open("your_file.txt", "w")
file.write("Hello, World!")
file.close()
# 逐行写
lines = ["Hello, World!\n", "Welcome to Python programming.\n"]
with open("your_file.txt", "w") as file:
# file.writelines(lines) # 此行为一次性写
for line in lines:
file.write(line)
# 12. 位运算
左移：<< ｜ 相当于 ×2
高位舍掉，低位补0
右移：>> ｜ 相当于 ÷2
有符号数，符号为随同移动。+，最高位补0；-，最高位补1。这个取决于编译系统。
>>>：无视符号的右移。
# 13. sort 和 operator
**py3的sort取消了cmp，可以用key**
itemgetter
from operator import itemgetter
sort(nums, key=itemgetter(0, 1))
= sort(nums, key=lambda x:(x[0], x[1]))
methodcaller
from operator import methodcaller
# 这里面count是内置函数，这条意思是按元素里'!'的个数排序
sort(messages, key=methodcaller('count', '!'))
cmp_to_key
sort(nums, key=cmp_to_key(func_compare))
func_compare(a, b) #如果a在b前面返回-1，后面返回1，相等返回0
# ord() 转ascii码
a的码：95；A的码：65
str转int 可使用：ord('c') - ord('0') # 'c'是当前想改的字母
# 14. 3.10字符串新特性
name = "Alice"
age = 25
s = f"{name} is {age} years old."
# 格式：f"{} xxx"