语法问题
我常用的库函数
1 copy库
import copy
copy.deepcopy()
2、list库
from typing import List
获取迭代对象的第一个值
方法一：使用list方法
my_dict = {'a': 1, 'b': 2, 'c': 3}
first_key = list(my_dict.keys())[0]
print(first_key) # 输出：'a'
方法二：使用next()函数和iter()函数
my_dict = {'a': 1, 'b': 2, 'c': 3}
iter_keys = iter(my_dict.keys())
first_key = next(iter_keys)
print(first_key) # 输出：'a'
全局变量（易错）
这里的re2会被覆盖
逻辑运算/位运算、
注意事项
如果你想把某一位置为0，不能直接等于 （result = (0 << i)）
如果你想把某一位置为1，不能直接等于 （result = (0 << i)）
位运算是一种对二进制数字进行特殊操作的方法，它针对每一位数字进行运算。在 Python 中，我们可以使用位运算符来执行这些操作。以下是 Python 中常用的位运算符：
右移运算 (>>)：将数字 x 向右移动 y 位，得到结果。
左移运算 (<<)：将数字 x 向左移动 y 位，得到结果。
与运算 (&)：返回结果的每一位是 x 和 y 中对应位进行 AND 运算的结果。只有 1 AND 1 = 1，其他情况为 0。
或运算 (|)：返回结果的每一位是 x 和 y 中对应位进行 OR 运算的结果。只有 0 OR 0 = 0，其他情况为 1。
反转运算 (~)：对 x 的每一位取补，结果是 -x - 1。
异或运算 (^)：如果 y 对应位是 0，则结果位取 x 的对应位；如果 y 对应位是 1，则取 x 对应位的补。(0^1=0 0^0=0 1^1=0 1^0=1 口诀：相同为0 ，不同为1)
这些运算符对整数进行操作，需要将数字转换为二进制表示形式，按最低位对齐，短的高位补零，然后进行位运算，最后将结果转换回十进制数12.
list拷贝（易错）
这段代码的问题在于，虽然在函数内部对nums进行了修改，但是这个修改并没有影响到函数外部的nums。这是因为在Python中，列表是可变对象，但是当你将一个列表赋值给另一个变量时，实际上是将原列表的引用赋值给了新变量，而不是创建了一个新的列表。所以在这个函数中，nums = last_k这行代码只是改变了nums这个局部变量的引用，而没有改变函数外部的nums。
正确的做法是：
可以使用列表的切片操作来直接修改原数组。这里是一个修改后的版本：
import copy
from collections import Counter
class Solution:
def rotate(self, nums, k):
k = k % len(nums)
retote = nums[:len(nums)-k] # 保存前面的的n-k个元素
last_k = nums[len(nums)-k:] # 保存后面的k个元素
last_k.extend(retote)
nums[:] = last_k
取余
dividend = 10
divisor = 3
quota = dividend // divisor
print("商是：", quota)
quota = dividend % divisor
print("余数：", quota)
# 商是： 3
# 余数： 1
求平方根/指数运算
for j in range(1, int((n)**(0.5))+1)
最大最小值
inf
-inf
list反转
if t == t[::-1]: # 判断是否回文
大小判断
if not 0 <= i < len(board) 居然可以一行判断
求随机值
Python的random库提供了生成随机数的功能。以下是一些常用的random库函数：
random.random()：生成一个0到1之间的随机浮点数，包括0，不包括1。
random.randint(a, b)：生成一个a到b之间的随机整数，包括a和b。
random.uniform(a, b)：生成一个a到b之间的随机浮点数，包括a和b。
random.choice(sequence)：从给定的序列中随机选择一个元素。
random.shuffle(sequence)：将给定的序列随机打乱
import random
# 生成一个0到1之间的随机浮点数
random_float = random.random()
print(random_float)
# 生成一个1到10之间的随机整数
random_int = random.randint(1, 10)
print(random_int)
# 生成一个1到10之间的随机浮点数
random_uniform = random.uniform(1, 10)
print(random_uniform)
# 从列表中随机选择一个元素
my_list = [1, 2, 3, 4, 5]
random_choice = random.choice(my_list)
print(random_choice)
# 将列表随机打乱
random.shuffle(my_list)
print(my_list)
排序和自自定义排序（重要）
https://zhuanlan.zhihu.com/p/108949863
方法1 lambda
单关键字排序
sorted(kids, key=lambda x: x['score'])
多关键字排序
sorted(kids, key=lambda x: (x['score'], x['age']))
最小会议室
# 题目见：https://www.jianshu.com/p/ba14c9d175e7
最少会议室数量：
思路：
1、先排序
2、re = [] # 保存每个会议室的最后的时间
3、两层遍历。对所有会议时间，如果存在一个会议室的最后时间早于当前时间，即可加入。否则另创建一个会议室
def minMeetingRooms(a:list):
a.sort(key=lambda k: k[0])
re = [] # 保存最后的时间
for x, y in a:
flag = False
for i in range(len(re)):
if x > re[i]:
re[i] = y # 更新当前会议室的最晚时间
flag = True # 如果存在一个会议室的最后时间早于当前时间，即可加入
break
if not flag:
re.append(y) # 否则另创建一个会议室
return len(re)
ee = minMeetingRooms([[0,30],[5, 10],[15,20]])
print(ee)
方法2 cmp_to_key（类c++）
注意：from functools import cmp_to_key
def cmp(kid1, kid2):
if kid1.score == kid2.score:
return kid1.age < kid2.age
else:
return kid1.score > kid2.score
from functools import cmp_to_key
sorted(kids, key=cmp_to_key(cmp))
cmp_to_key原理:
我们可以看到，在函数内部，它其实定义了一个类，然后在类当中重载了比较函数，最后返回的是一个重载了比较函数的新的对象。这些__lt__, __gt__函数就是类当中重载的比较函数。比如__lt__是小于的判断函数，__eq__是相等的函数。那么问题来了，我们能不能直接在Kid类当中重载比较函数呢，这样就可以直接排序了。
方法3 直接重载操作符 lt
class Kid:
def __init__(self, name, score, age):
self.name = name
self.score = score
self.age = age
def __repr__(self):
return 'Kid, name: {}, score: {}, age:{}'.format(self.name, self.score, self.age)
def __lt__(self, other):
return self.score > other.score or (self.score == other.score and self.age < other.age)
sorted(kids)
map reduce filter使用
map
注意返回的时候一定要用list包一层
def add(x, y):
return x + y
numbers1 = [1, 2, 3]
numbers2 = [4, 5, 6]
summed_numbers = map(add, numbers1, numbers2)
print(list(summed_numbers)) # 输出：[5, 7, 9]
numbers = [1, 2, 3, 4, 5]
squared_numbers = map(lambda x: x * x, numbers)
print(list(squared_numbers)) # 输出：[1, 4, 9, 16, 25]
注意这两种用法的区别
ddd = list(map(lambda item: sorted(item), re))
和
ddd = list(map(lambda item: item.sort, re)) #得到的全是none，因为 item.sort,返回的是none
filter
def is_greater_than_5(x):
return x > 5
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
greater_than_5 = filter(is_greater_than_5, numbers)
print(list(greater_than_5)) # 输出：[6, 7, 8, 9, 10]
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
even_numbers = filter(lambda x: x % 2 == 0, numbers)
print(list(even_numbers)) # 输出：[2, 4, 6, 8, 10]
reduce
from functools import reduce
numbers = [1, 2, 3, 4, 5]
sum_of_numbers = reduce(lambda x, y: x + y, numbers)
print(sum_of_numbers) # 输出：15
from functools import reduce
def add(x, y):
return x + y
numbers = [1, 2, 3, 4, 5]
sum_of_numbers = reduce(add, numbers)
print(sum_of_numbers) # 输出：15
容器的使用
优先级队列(难)（重要）
https://www.cnblogs.com/nxf-rabbit75/p/15921105.html
练习题：
621. 任务调度器
https://leetcode-cn.com/problems/task-scheduler/
253. 会议室 II
https://leetcode-cn.com/problems/meeting-rooms-ii/
703. 数据流中的第 K 大元素
https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
347. 前 K 个高频元素
https://leetcode-cn.com/problems/top-k-frequent-elements/
215. 数组中的第K个最大元素
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
剑指 Offer II 061. 和最小的 k 个数对
https://leetcode-cn.com/problems/qn8gGX/
import heapq
from typing import List
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
pq = [] # 将数组加入小顶堆，堆中维护当前值最大的k个数
for num in nums:
heapq.heappush(pq, num) # 当前元素入堆
if len(pq) > k:
heapq.heappop(pq) # 堆中元素超过k个，弹出最小的那个
return pq[0] # 最后堆顶的即为第k大的数,注意堆顶是最小的
if __name__ == '__main__':
re = Solution().findKthLargest([1,2,3],1)
print(re)
pass
队列（重要）
from collections import deque
cur = que.popleft() # 左出
que.append(item) # 右进
que = deque([key for key,val in ru_map.items() if val == 0]) # 初始化queen
队列应用：拓扑排序
1 初始化入度表
2 将入度为0的加入到队列中
3 遍历所有队列，挨个处理（减入度+加入到队列中等）
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
ru_map = {item:0 for item in range(numCourses) } # 这里初始化值为0 # 优化点 du = [0]*numCourses #存放每个结点的入读
ddd = [[] for _ in range(numCourses)] # 存放每个结点的子结点
result = [] # 进入过队列的所有点
for item in prerequisites:
n1, n2 = item
ru_map[n1] += 1
ddd[n2].append(n1)
que = deque([key for key,val in ru_map.items() if val == 0]) # 初始化queen
while que:
cur = que.popleft() # 左出
result.append(cur)
for item in ddd[cur]:
ru_map[item] -= 1
if ru_map[item] == 0:
que.append(item) # 右进
return len(result) == numCourses
作者：YingL
链接：https://leetcode.cn/problems/course-schedule/solutions/2745954/207-ke-cheng-biao-by-user5776-6nxn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
栈的使用（重要）
aa = stack.pop() 弹出最后一个元素
stack[-1]: 获取最后一个元素
while stack 来进行判空（直接使用list作为判断标准，则空列表相当于False）
https://blog.csdn.net/weixin_43977640/article/details/109909787 --介绍了list判空的三种方法
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = {}
stack = []
for num in reversed(nums2):
while stack and num >= stack[-1]:
stack.pop()
res[num] = stack[-1] if stack else -1
stack.append(num)
return [res[num] for num in nums1]
list
必知必会：查找、排序、增加、删除、反转、去重
查找索引：在中序遍历建立二叉树时需要使用
index
a = [1,2,5,3, 3]
print(a.index(3)) # 3 这个是找到第一个
print(a.count(3)) # 2
去重
list(set(a))
# 删除
del a[3]
print(a) # [1, 2, 5, 3]
a.remove(3)
print(a) # [1, 2, 5]
remove()函数需要一个参数，即要删除的元素，而del语句需要一个参数，即要删除的元素的索引。 如果列表中有多个匹配项，remove()函数只会删除第一个匹配项。 例如，如果我们有一个列表a=[1,2,3,4,5,3]，要删除元素3，使用remove()函数只会删除第一个3，列表变成a=[1,2,4,5,3]。
其他
#!/usr/bin/python
del list1[2]
1 cmp(list1, list2)
比较两个列表的元素
2 len(list)
列表元素个数
3 max(list)
返回列表元素最大值
4 min(list)
返回列表元素最小值
5 list(seq)
将元组转换为列表
1 list.append(obj)
在列表末尾添加新的对象
2 list.count(obj)
统计某个元素在列表中出现的次数
3 list.extend(seq)
在列表末尾一次性追加另一个序列中的多个值（用新列表扩展原来的列表）
4 list.index(obj)
从列表中找出某个值第一个匹配项的索引位置
5 list.insert(index, obj)
将对象插入列表
6 list.pop([index=-1])
移除列表中的一个元素（默认最后一个元素），并且返回该元素的值
7 list.remove(obj)
移除列表中某个值的第一个匹配项
8 list.reverse()
反向列表中元素
9 list.sort(cmp=None, key=None, reverse=False)
对原列表进行排序
dict
删除
#!/usr/bin/python
# -*- coding: UTF-8 -*-
tinydict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}
del tinydict['Name'] # 删除键是'Name'的条目
tinydict.clear() # 清空字典所有条目
del tinydict # 删除字典
print "tinydict['Age']: ", tinydict['Age']
print "tinydict['School']: ", tinydict['School']
判断dict中是否存在某个key值
if tar in ddddict:
pass
动态扩容(易错)
能否实时修改内部元素
一个二维数组，[ [] ,[] ] 怎样获取其中元素的引用。一般用dict
初始化定长的数组
self.children = [None] * 26
初始化二维定长数组
visited = [[False for _ in range(m)] for _ in range(n)]
!!!!!!(重要重要)注意这种方法其实是三个引用 第一行的数据和第二行的数据是一样的
visited = [[False] * m] * n
这行代码在 Python 中创建了一个 m 行 n 列的二维布尔数组，所有的元素初始值都是 False。但是，这里存在一个潜在的问题，即它并不是创建了 m 个独立的数组，而是创建了一个数组，然后复制了 m 次。这意味着所有的行都引用同一个内存地址，因此如果你修改一个元素的值，所有的相同位置的元素都会被改变。
这行代码的问题可以通过一个简单的例子来说明：
visited = [[False] * m] * n
visited[0][0] = True
print(visited)
[[True, False, False], [True, False, False], [True, False, False]]
正确的做法是
visited = [[False for _ in range(m)] for _ in range(n)]
错题记录
visited = [[False] * len(board[0]) for _ in range(len(board))] --我之前把这里的行列弄反了
hash字母表
self.children = [None] * 26
ch = ord(ch) - ord("a")
if not node.children[ch]:
统计频率 Counter
c = Counter('abracadabra')
for key, value in c.items():
print(f"{key}: {value}")
t = "abc"
cnt_s = Counter() # s 子串字母的出现次数,初始化方法
cnt_t = Counter(t) # t 中字母的出现次数
while cnt_s >= cnt_t: # 涵盖
cnt_s[s[left]] -= 1 # 左端点字母移出子串
dfs 基本框架 + 上下左右
python是引用传值，所以这里的grid和re都是全局变量
岛屿数量
import concurrent.futures
from typing import List
"""
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
"""
def num_of_islands(grid: List[List[str]]) -> int:
def dfs(i, j):
if grid[i][j] != '1':
return
grid[i][j] = '#'
direcion = [[1, 0], [0, 1], [-1, 0], [0, -1]] #上下左右方向
for item in direcion:
i1,j1 = i + item[0],item[1]
if i1 in range(0, n) and j1 in range(0, m): # 是否在边界内部
dfs(i1, j1)
re = 0
n, m = len(grid), len(grid[0])
for i in range(n):
for j in range(m):
if grid[i][j] == '1':
dfs(i, j)
re += 1
return re
if __name__ == '__main__':
grid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]
]
re2 = num_of_islands(grid)
print(re2)
集合合并
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
ans = []
intervals.sort() # 按照左区间进行排序
for interval in intervals:
# 把第一个区间放入 或者 当前区间的左区间在目前候选区间的右边（无重叠）
if not ans or ans[-1][1] < interval[0]:
ans.append(interval)
else: # 当前区间的左区间在目前候选区间的左边（有重叠）
ans[-1][1] = max(ans[-1][1], interval[1]) # 取最大的右区间
return ans
作者：aJupyter
链接：https://leetcode.cn/problems/merge-intervals/solutions/2738570/56-he-bing-qu-jian-by-ajupyter-6ryu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
单例模式和适配器模式
单例模式
way1：使用函数装饰器来是实现（通用方法）
def singleton(cls):
_instance = {}
def inner():
if cls not in _instance:
_instance[cls] = cls()
return _instance[cls]
return inner
@singleton
class Cls(object):
def __init__(self):
pass
cls1 = Cls()
way2：java和c++的方法（针对某个类）
class Single(object):
_instance = None
def __new__(cls, *args, **kw):
if cls._instance is None:
cls._instance = object.__new__(cls, *args, **kw)
return cls._instance
def __init__(self):
pass
single1 = Single()
single2 = Single()
print(id(single1) == id(single2))
装饰器模式
简单装饰器
def use_logging(func):
def wrapper():
logging.warn("%s is running" % func.__name__)
return func()
return wrapper
@use_logging
def foo():
print("i am foo")
foo()
带参数的装饰器
def use_logging(level):
def decorator(func):
def wrapper(*args, **kwargs):
if level == "warn":
logging.warn("%s is running" % func.__name__)
elif level == "info":
logging.info("%s is running" % func.__name__)
return func(*args)
return wrapper
return decorator
@use_logging(level="warn")
def foo(name='foo'):
print("i am %s" % name)
foo()
线程同步
线程同步的方法
在Python中，线程同步是通过锁（Locks）、事件（Events）、信号量（Semaphores）、条件变量（Conditions）和队列（Queues）等机制来实现的。以下是一些常用的线程同步方法：
threading.Lock：
提供一个简单的锁机制，用于防止多个线程同时访问共享资源。
使用acquire()方法来获取锁，使用release()方法来释放锁。
如果锁已被其他线程获取，尝试获取锁的线程将阻塞，直到锁被释放。
threading.Event：
提供一个事件对象，线程可以使用它来协调工作。
使用set()方法来设置事件，使用clear()方法来清除事件，使用wait()方法来等待事件被设置。
事件用于线程间的信号传递，可以用来同步操作的开始和结束。
threading.Semaphore：
类似于锁，但允许多个线程同时访问资源，最多允许N个线程同时访问。
使用acquire()方法来获取许可，使用release()方法来释放许可。
当没有可用的许可时，线程会阻塞，直到有可用的许可。
threading.Condition：
条件变量允许线程在某些条件成立时才能继续执行。
通常与锁一起使用，以便线程在等待特定条件时释放锁。
使用wait()方法来等待条件变量，使用notify()或notify_all()方法来通知等待的线程条件已经成立。
threading.Queue：
提供一个线程安全的队列，用于在不同线程之间传递数据。
队列本身是线程安全的，不需要额外的同步机制。
使用put()方法来添加数据，使用get()方法来获取数据。
threading.Barrier：
barrier 允许一组线程在某个点上同步，直到所有线程都到达该点后，才能继续执行。
使用wait()方法来等待所有线程到达屏障点。
两个线程交互打印
锁+event 机制
锁保证了 数据的互斥修改
event保证了时序性
import threading
# 定义一个Event对象用于线程同步
event = threading.Event()
# 定义一个共享变量
number = 0
def print_even():
global number
with threading.Lock(): # 确保共享资源访问的安全
while number < 100:
if number % 2 == 0:
print(number)
number += 2
event.set() # 设置事件，通知另一个线程继续执行
event.clear() # 清空事件，以便下一个循环时重新检查条件
def print_odd():
global number
with threading.Lock(): # 确保共享资源访问的安全
while number < 100:
if number % 2 != 0:
print(number)
number += 1
event.wait() # 等待事件被设置
event.clear() # 清空事件，以便下一个循环时重新检查条件
# 创建并启动线程
thread1 = threading.Thread(target=print_even)
thread2 = threading.Thread(target=print_odd)
thread1.start()
thread2.start()
# 等待线程结束
thread1.join()
thread2.join()
两个线程交互打印
with threading.Lock()
import threading
import time
# 定义一个Event对象用于线程同步
event1 = threading.Event()
event2 = threading.Event()
def print_even():
global event1, event2
with threading.Lock(): # 确保共享资源访问的安全
while True:
if event1.is_set(): # 检查事件1是否被设置
print(f"Even: {event1.is_set()}")
event1.clear() # 清空事件1
event2.set() # 设置事件2
break
time.sleep(0.1) # 等待一段时间
def print_odd():
global event1, event2
with threading.Lock(): # 确保共享资源访问的安全
while True:
if event2.is_set(): # 检查事件2是否被设置
print(f"Odd: {event2.is_set()}")
event2.clear() # 清空事件2
event1.set() # 设置事件1
break
time.sleep(0.1) # 等待一段时间
# 创建并启动线程
thread1 = threading.Thread(target=print_even)
thread2 = threading.Thread(target=print_odd)
thread1.start()
thread2.start()
# 等待线程结束
thread1.join()
thread2.join()
多个线程依次访问
使用lock
with lock: # 使用 with 语句自动获取和释放锁
import threading
# 创建一个共享资源
shared_resource = "Hello, World!"
# 创建一个锁
lock = threading.Lock()
# 定义一个函数，用于访问共享资源
def access_shared_resource():
with lock: # 使用 with 语句自动获取和释放锁
# 访问共享资源
print(shared_resource)
# 创建并启动多个线程
threads = []
for i in range(5):
thread = threading.Thread(target=access_shared_resource)
threads.append(thread)
thread.start()
# 等待所有线程完成
for thread in threads:
thread.join()