为什么选用Python写算法题#
毋庸置疑，Python是主流编程语言中语法最简洁的，再加上python内置函数丰富，熟练之后写算法题可以大幅减少代码量和用时。
面向ICPC/CCPC的同学出于性能考虑往往会采用C++作为首选编程语言，但是在普通比赛或者面试中碰到的编程题并不会卡编程语言的时间，只要算法的时间复杂度达标即可通过，所以当习惯使用Python写算法题后可以提高效率，并且能够体会到Python的简洁之道。
常用技巧#
Counter#
c = Counter(list)
for k, v in c.items():
print(k, v)
for k in c.keys():
print(k, c[k])
for v in c.values():
print(v)
for i in c.elements():
print(i)
dict = defaultdict(list) #默认为空列表
dict = defaultdict(int) #默认为0
for k, v in dict:
print(k, v)
推导式#
# 列表推导式
newnames = [name.upeer() for name in names if len(name) > 3]
multiples = [i for i in range(30) if 3 % 3 == 0]
# 字典推导式
newdict = {key:len(key) for key in listdemo}
dic = {x:x**2 for x in (2, 4, 6)}
# 集合推导式
newset = {i**2 for i in (1, 2, 3)}
a = {x for x in 'abracadabra' if x not in 'abc'}
自定义排序#
data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
data.sort(key=lambda r: r[1])
# 自定义排序函数
def custom_sort_key(item):
# 根据item的某种特性生成排序键
return item['priority'] # 假设我们按照优先级排序
# 示例数据
items = [
{'name': 'A', 'priority': 2},
{'name': 'B', 'priority': 1},
{'name': 'C', 'priority': 3},
]
# 使用sorted()进行排序
sorted_items = sorted(items, key=custom_sort_key)
print(sorted_items) # 输出排序后的列表
# 使用list.sort()进行排序
items.sort(key=custom_sort_key)
print(items) # 输出就地排序后的列表
记忆化函数#
from functools import cache
# 在函数前使用@cache即可完成记忆化函数
二分查找函数#
import bisect
my_list = [1, 3, 5, 5, 7, 9]
# 使用 bisect_left 查找目标元素的插入位置
left_index = bisect.bisect_left(my_list, 5)
print("插入位置（最左边）:", left_index)
# 使用 bisect_right 查找目标元素的插入位置
right_index = bisect.bisect_right(my_list, 5)
print("插入位置（最右边）:", right_index)
插入位置（最左边）: 2
插入位置（最右边）: 4
# 详细使用：
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
在列表a的[lo,hi)子集块中查找第一个大于等于x的下标
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
在列表a的[lo,hi)子集块中查找第一个大于x的下标
# 自定义比较规则
my_list = [1, 3, 5, 7, 9]
index = bisect.bisect_left(my_list, 5, key=lambda x: x * x)
# 应用示例 成绩分组
def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
i = bisect(breakpoints, score)
return grades[i]
[grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']
通用模板#
此模版面向ICPC/CCPC竞赛，如果对于python代码有性能需求可以考虑使用模板中封装的IO模块
import sys, os, math
from math import gcd, sqrt
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations, product
from heapq import nsmallest, nlargest, heapify, heappop, heappush
BUFSIZE = 8192
def solve():
n = 1
def main():
tt = 1
tt = II()
for _ in range(tt):
solve()
def qmi(a, b, p):
res = 1 % p
while b:
if b & 1:
res = (res * a) % p
a = a * a % p
b >>= 1
return res
def comb(n, r):
return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0
def I():
return input()
def II():
return int(input())
def MII():
return map(int, input().split())
def LMII():
return list(map(int, input().split()))
def YES(t = 1): print("YES" if t else "NO")
def NO(t = 1): YES(t ^ 1)
def Yes(t = 1): print("Yes" if t else "No")
def No(t = 1): Yes(t ^ 1)
def yes(t = 1): print("yes" if t else "no")
def no(t = 1): yes(t ^ 1)
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin = IOWrapper(sys.stdin)
input = lambda: sys.stdin.readline().rstrip()
if __name__ == "__main__":
main()