国庆节10月1日
--



Python 语法速查与常用算法模板合集,含 97 张配图(原笔记 6180 行)
固定模板
1import sys2import math3import bisect4import heapq5
6from collections import (7 deque,8 Counter,9 defaultdict10)11
12from functools import lru_cache13from itertools import permutations, combinations, accumulate14from operator import itemgetter15
16
17# ==================== 快速输入 ====================18
19# 方式一:按行读取,适合普通输入20input = sys.stdin.buffer.readline21
22# 读取一行整数23n, m = map(int, input().split())24
25# 读取一行数组26a = list(map(int, input().split()))27
28
29# 方式二:一次性读取全部输入,适合数据量特别大30# data = list(map(int, sys.stdin.buffer.read().split()))31# index = 032# n = data[index]33# index += 134
35
36# ==================== 数学函数 math ====================37
38# 最大公约数39g = math.gcd(12, 18) # 640
41# 最小公倍数42l = math.lcm(12, 18) # 3643
44# 平方根45x = math.sqrt(16) # 4.046
47# 向上取整、向下取整48up = math.ceil(3.2) # 449down = math.floor(3.8) # 350
51# 阶乘52f = math.factorial(5) # 12053
54# 组合数 C(n, k)55c = math.comb(5, 2) # 1056
57# 无穷大58INF = 10**1859
60# 负无穷61NEG_INF = -10**1862
63
64# ==================== 二分 bisect ====================65
66a = [1, 2, 2, 4, 6]67
68# 第一个大于等于 x 的位置69left = bisect.bisect_left(a, 2) # 170
71# 第一个大于 x 的位置72right = bisect.bisect_right(a, 2) # 373
74# 统计 x 出现次数75count = bisect.bisect_right(a, 2) - bisect.bisect_left(a, 2)76
77# 向有序数组中插入元素,保持有序78bisect.insort(a, 3)79
80
81# ==================== 队列 deque ====================82
83q = deque()84
85# 入队86q.append(1)87
88# 从队头出队89x = q.popleft()90
91# 从队尾入队92q.appendleft(2)93
94# 从队尾出队95x = q.pop()96
97
98# ==================== BFS 常用写法 ====================99
100directions = [101 (-1, 0), # 上102 (1, 0), # 下103 (0, -1), # 左104 (0, 1) # 右105]106
107queue = deque()108queue.append((0, 0))109
110while queue:111 x, y = queue.popleft()112
113 for dx, dy in directions:114 nx = x + dx115 ny = y + dy116
117
118# ==================== 堆 heapq ====================119
120# Python 默认是小根堆121heap = []122
123heapq.heappush(heap, 5)124heapq.heappush(heap, 2)125heapq.heappush(heap, 8)126
127# 取出最小值128smallest = heapq.heappop(heap)129
130# 查看堆顶但不删除131top = heap[0]132
133
134# 模拟大根堆:存入负数135max_heap = []136
137heapq.heappush(max_heap, -10)138heapq.heappush(max_heap, -3)139
140# 最大值141maximum = -heapq.heappop(max_heap)142
143
144# ==================== Counter 计数 ====================145
146a = [1, 2, 2, 3, 3, 3]147
148cnt = Counter(a)149
150# cnt[3] == 3151# 出现次数最多的元素152most_common = cnt.most_common(1)153
154
155# ==================== defaultdict ====================156
157# 不存在的键默认值为 0158freq = defaultdict(int)159
160for x in a:161 freq[x] += 1162
163
164# 默认创建空列表165graph = defaultdict(list)166
167graph[1].append(2)168graph[2].append(3)169
170
171# ==================== 前缀和 accumulate ====================172
173a = [1, 2, 3, 4]174
175prefix = list(accumulate(a))176# prefix = [1, 3, 6, 10]177
178# 区间 [l, r] 的和:179# prefix[r] - prefix[l - 1]180# 注意这里假设下标从 1 开始181
182
183# ==================== 缓存递归结果 ====================184
185@lru_cache(None)186def fib(n):187 if n <= 1:188 return n189
190 return fib(n - 1) + fib(n - 2)191
192
193# ==================== 主程序 ====================194
195def solve():196 # 在这里写题目代码197 pass198
199
200if __name__ == "__main__":201 solve()1import sys2import math3import bisect4import heapq5sys.set_int_max_str_digits(0)6sys.set_int_max_str_digits(0)7from collections import deque, Counter, defaultdict8from functools import lru_cache9
10input = sys.stdin.buffer.readline11
12INF = 10**1813
14directions = [15 (-1, 0),16 (1, 0),17 (0, -1),18 (0, 1)19]20
21
22def solve():23 n = int(input())24 a = list(map(int, input().split()))25
26 # 在这里写代码27
28
29if __name__ == "__main__":30 solve()课程(知识点)TsingPig视频专辑-TsingPig视频合集-哔哩哔哩视频
https://github.com/TsingPig/Lesson_Python_TsingPig.git
https://wiki.dwj601.cn/ds-and-algo/templates-py/
课程(带刷)【假期逆袭!算法竞赛入门速成】蓝桥杯、天梯赛(python组)第一章 基础练习_哔哩哔哩_bilibili
课程(带刷力扣)算法路飞的个人空间-算法路飞个人主页-哔哩哔哩视频
灵神https://github.com/EndlessCheng/codeforces-go/blob/master/leetcode/README.md



1# int 整数2# float 浮点数3# str 字符串 不可变序列 s="Hello"4# list 列表,增删改查,'list=[1,2,3]'5# tuble 元组 不可变序列 'tub=(1,2,3)'6# set 集合 无序不重复 支持集合运算 's={1,2,3}'7# dict 字典 类似于C++map 'd={"key","value"}'1import sys2def main():3 data = list(map(int, sys.stdin.read().split()))4
5
6if __name__ == "__main__":7 main()8# Python 固定写法:当直接运行这个 py 文件时,执行 main () 函数。导入系统模块,用来一次性读取全部输入。竞赛里sys.stdin.read()是高速读入,比循环input()快很多,处理 2e5 大数据不会超时
定义主函数,把所有逻辑包进去。Python 推荐写在函数里,运行速度比全局代码更快
sys.stdin.read():一次性读取全部输入文本,把所有输入当成一整个长字符串。.split():按空白(空格、换行、回车)切分成一串字符串,不管有多少行。map(int, ...):把每一段字符串转成整数。list(...):转为整数列表,全部输入数字顺序存到data。举例样例输入:
1625 431 2 3 4 4
data会变成:[6,5,4,1,2,3,4,4, ...] 好处:不用一行一行读,规避多次 IO 带来的巨大耗时
1import sys2
3def main():4 data = list(map(int, sys.stdin.read().split()))5 # `p`是**指针(索引)**,标记我们现在读到`data`列表第几个数字。初始从第 0 位开始6 p = 07
8 t = data[p]9 p += 110 for _ in range(t):11 n = data[p]12 m = data[p+1]13 p += 214
15 stx = [0] * (m + 1) # stx[0 ~ m),多开一位防止越界16 for __ in range(n):17 val = data[p]18 p += 119 stx[val] += 120
21 # 后缀和 stx1[x] = sum_{i >= x} stx[i]22 stx1 = [0] * (m + 2)23 for x in range(m, 0, -1):24 stx1[x] = stx1[x + 1] + stx[x]25
26 ans = 027 for x in range(1, m + 1):28 l1 = stx1[x + 1]29 l2 = 030 if 2 * x <= m:31 l2 = stx[2 * x]32 cnt = stx[x] + l1 + l233 if cnt > ans:34 ans = cnt35 print(ans)36
37if __name__ == "__main__":38 main()1import sys2input = sys.stdin.readline3
4def main():5 t = int(input())6 for _ in range(t):7 n, m = map(int, input().split())8 arr = list(map(int, input().split()))9 stx = [0]*(m+1)10 for v in arr:11 stx[v] += 112 stx1 = [0]*(m+2)13 for x in range(m,0,-1):14 stx1[x] = stx1[x+1] + stx[x]15 ans = 016 for x in range(1, m+1):17 l1 = stx1[x+1]18 l2 = 019 if 2*x <= m:20 l2 = stx[2*x]21 cnt = stx[x] + l1 + l222 ans = max(ans, cnt)23 print(ans)24
25if __name__ == "__main__":26 main()对标C++
1#include<bits/stdc++.h>2
3using namespace std;4
5
6int main(){7 int t;8 cin>>t;9
10 while(t--){11 int n,m;12 cin>>n>>m;13
14
15 vector<int> stx(m+1,0);16 vector<int> stx1(m+2,0);17 //vector<int> stx2(2*m);18
19 for(int i=0;i<n;i++){20 int x;21 cin>>x;22
23 stx[x]++;24 }25
26 for(int x=m;x>=1;x--){27 stx1[x]=stx1[x+1]+stx[x];28 }29
30 int ans=0;31
32 for(int x=1;x<=m;x++){33 int l1=stx1[x+1];34
35 int l2=0;36
37 if(2*x<=m){38 l2=stx[2*x];39 }40
41 int cnt=stx[x]+l1+l2;42 ans=max(ans,cnt);43 }44
45 cout<<ans<<endl;46 }47
48 return 0;49}1import sys2input = lambda: sys.stdin.readline().strip()1n=int(input())2print(n)3# a b 输入以空格分割4a,b=map(int ,input().split())5print(a+b)6
7print(n,a,b)8
9# Python print 默认自动换行10
11# 手动取消换行12print("输出列表:",end=' ')
对标vector
1# list2# 它的作用:**读入一行空格隔开的数字,转成整数列表**3lis=list(map(int,input().split()))4print("输出列表:",end=' ')5print(lis)6# 尾部添加元素7lis.append(19)8print("输出列表:",end=' ')9print(lis)10
11print("不带括号版:",end=' ')12print(*lis)13
14# 输出某个元素15print("第一和第二个元素:",end=' ');16print(lis[0],lis[1])17
18# 计算总会19sum(lit)
1# list 列表 里面可以放不同的数据类型2
3# listext = ["string",2,3,4,5]4
5list1 =[1,2,3,4,5]6
7# print(list1[0])8# 无索引默认删第一个,有索引按索引删9list1.pop()10print(list1)11list1.pop(0)12print(list1)13
14# append 末尾添加15
16list1.append(5)17print(list1)18print("list1的长度为 ",end='')19print(len(list1))20
21# insert 插入 在对应位置插入对应元素22list1.insert(0,1) #前面是索引位置,后面是位数据23print(list1)
1list1=list(map(int ,input().split()))2# 排序3list1.sort()4print(list1)5
6# 翻转7list1.reverse()8print(list1)9
10# 删除指定值 remove(只删第一个) ||| pop 是删除指定索引值11
12list1.remove(1)13print(list1)
1list1=list(map(int ,input().split()))2# 排序 默认从小到大3list1.sort()4print(list1)5# 从大到小6# 法17list1.sort(reverse=True)8print(list1)9# 法210b = sorted(list1, reverse=True)11print(b)12# 翻转13list1.reverse()14print(list1)15
16# 删除指定值 remove(只删第一个) ||| pop 是删除指定索引值17
18list1.remove(1)19print(list1)
不变的列表
1# 操作 和列表不变的部分一样2# 输出,列表[],元组 ()3tuple1=(1,2,3)4
5print (tuple1)6# 转化为list 操作7print (list(tuple1))8list1 = list(tuple1)9list1[0]=010print(list1)11
12tub2=tuple(list1)13print(tub2)
Python 里字符串str是不可变类型,不能直接写 s[i] = '.' 修改字符串里某个字符!
1str1="hello"2str2=" Selina"3
4print(str1+str2)5# [l:r]:左闭右开 [l,r)6print(str1[0:4])
1s1="hello boy"2s2="Oh No"3//加号4print(s1+s2)
1s1="hello boy"2
3# len length4
5print(len(s1))6
7
8# capitalize 首字母大写9
10print (s1.capitalize())11
12# upper 全部大写13
14print(s1.upper())15
16s1="OH BOY"17# lower 全部小写18
19print(s1.lower())20
21# replace 把第一个参数替换为第二个22
23print(s1.replace("BOY","Selina ,I miss you"))24
25# find 查找 报告第一个出现的索引26
27print(s1.find("BOY"))
1s1="hello boy"2s2="HELLO WORLD"3# bool4# a = True5# b = False6
7# isupper 判断是否都是大写8
9print(s1.isupper())10print(s2.isupper())
1s1="hello boy"2s2="HELLO WORLD"3
4print(s1.split('o',1))5# 判断结尾是否匹配6print(s1.endswith("boy"))
1s = input() # 读取一行,回车结束;得到字符串,包含空格,**自动去掉末尾换行符**2
3print(s)
1# 输入:hi python2lst = input().split()3print(lst) # ['hi', 'python']
strip()#的作用是:删除字符串开头和结尾的空白字符,包括空格、换行 \n、制表符 \t 等。
1s = input().strip()
1import sys2input = sys.stdin.readline3
4def main():5 t=int(input())6 for _ in range(t):7
8 n,k=map(int,input().split())9 s=input().strip()10
11 cnt=[0] * k12
13 for i in range(n):14 if(s[i]=='1'):15 cnt[i%k]+=116
17 ok=True18
19 for i in range(k):20 if(cnt[i]%2!=0):21 ok=False22 break23
24 print("YES" if ok else "NO")25
26if __name__ == "__main__":27 main()1import sys;2input=lambda:sys.stdin.readline().strip()3
4n=input()5print(f"I am {n} and I am studying Python in Nowcoder!")
1class Solution:2 def lengthOfLastWord(self, s: str) -> int:3 asd=s.split()4 return len(asd[-1])s.split() 默认按空白(空格、换行、多个空格)切分字符串,得到单词列表。 asd[-1] 取最后一个单词,len()求它的长度。
功能:返回字符串最后一个单词的长度(LeetCode 58. 最后一个单词的长度
index() 用来查找元素在列表中的下标。

1# 函数2# 定义 def3def get_sum(sum1,sum2):4 return sum1+sum25
6a,b=map(int,input().split())7
8print(get_sum(a,b))
在上面的实践中可以发现,除法运算(/)永远返回浮点类型(在 Python 2 中返回整数).如果你想要整数或向下取整的结果的话,可以使用整数除法(//).同样的,你也可以像 C++ 中一样,使用模(%)来计算余数,科学计数法的形式也相同.
1# 数字2
3a=94b=25c=a+16print(a/b)7print(c/b)8# 强转9print(int(a/b))10print(a//b)11
12print(a%b)13
14# abs15a=-916print(a/2)17
18print(abs(a/2))
1import math2# round:四舍五入3a=3.44print(round(a))5a=3.56print(round(a))7
8# pow 幂9
10print(pow(a,2))11
12#ceil 引入math模块 向上取整13print(math.ceil(a))
重点 后续要打磨
kiys / values 键值对
Python dict 等价 C++ unordered_map(哈希表);C++ map 是有序版本,Python 里想要有序要额外 sorted
1# dict 键值对,通过键查找值2dict1={"name":"老张","height":170,"weight":100}3
4print(dict1["name"])5
6print(len(dict1))7# 获得键8print(dict1.keys())9#获得值10print(dict1.values())11
12# 添加或修改13dict1["name"]="Aurora"14print(dict1["name"])15
16dict1["gender"]="man"17print(dict1.keys())18
19# 删除20dict1.pop("name")21print(dict1.keys())
1map<string,int> cnt;1cnt = dict() # 字典,等价C++ map
1n = int(input())2st = []3for _ in range(n):4 s = input()5 st.append(s)6
7cnt = dict() # 字典,等价C++ map8
9for s in st:10 s_lower = s.lower() # 全部转小写,和C++里^32效果一样11 if s_lower in cnt:12 cnt[s_lower] += 113 else:14 cnt[s_lower] = 115
16ans = 017for v in cnt.values():18 ans = max(ans, v)19
20print(ans)对标C++
1#include<bits/stdc++.h>2using namespace std;3int main(){4 int n;5 cin>>n;6
7 vector<string> st(n);8
9 for(int i=0;i<n;i++){10 cin>>st[i];11 }12
13 map<string,int> cnt;14
15 for(int i=0;i<n;i++){16 for(int j=0;j<st[i].size();j++){17 if(st[i][j]>='A'&&st[i][j]<='Z'){18 st[i][j]^=32;19 }20 }21
22 cnt[st[i]]++;23 }24
25 int ans=0;26 for(auto & p:cnt){27 int v=p.second;28 ans=max(ans,v);29 }30 cout<<ans<<endl;31}set 无重复元素,无顺序 无法索引查找
1# set 无重复元素,无顺序 无法索引查找2set1={1,3,5,2,2}3set2=set((3,4,7,5,6))4print(set1)5print(set2)6
7# 添加元素8set1.add(10)9print(set1)10
11# 删除元素12
13set1.discard(2)14print(set1)15
16# 公有的元素17print(set1.intersection(set2))18# 不同的 1有2没有19print(set1.difference(set2))
1# set 无重复元素,无顺序 无法索引查找2set1={1,3,5,2,2}3set2=set((3,4,7,5,6))4print(set1)5print(set2)6
7# 判断2是不是1的子集8print(set2.issubset(set1))
1# 从 Python 自带的 `collections` 模块里面,导入 `deque`(双端队列)这个类,**这样你后面代码才能直接写 `deque()` 创建队列**。2from collections import deque3
4# 创建空队列5q = deque()6
7# 入队(队尾添加) append8q.append(1)9q.append(2)10q.append(3)11
12# 出队(队头弹出) popleft13x = q.popleft()14print(x) # 115
16# 查看队首元素(不取)17print(q[0]) # 218
19# 判断队列是否为空20if q:21 print("队列不为空")22else:23 print("空队列")24
25# 获取长度26print(len(q))
1homework_finished=False2
3if(homework_finished):4 print("over")5else:6 print("go work")7
8a=int(input())9
10if(a==100):11 print("good")12elif (a==1000):13 print("fuck")14else :15 print("NNNN")1x=int(input())2list1=[]3while x>0 :4 p=x%105 list1.append(p)6 x//=107print(*list1)
1int n = 5;2for(int i = 0; i < n; i++){3 cout << i << endl;4}5// 输出:0 1 2 3 41n = 52for i in range(n):3 print(i)range(n):产生 0,1,2,...,n-1,左闭右开,取不到 ni++,Python 自动帮 i+11// i从1到5,包含52for(int i = 1; i <= 5; i++){3 cout << i << endl;4}1# range(起点, 终点),终点取不到!所以要写5+1=62for i in range(1, 6):3 print(i)1for(int i = 1; i <= 10; i += 2){2 cout << i; //1,3,5,7,93}1# range(起始,终止,步长)2for i in range(1, 11, 2):3 print(i)1for(int i = 5; i >= 1; i--){2 cout << i; //5 4 3 2 13}1# range(开始,结束,-1);结束值取不到,所以写02for i in range(5, 0, -1):3 print(i)1int arr[] = {10,20,30};2for(int i = 0; i < 3; i++){3 cout << arr[i];4}5// 或者C++11范围for6for(auto num : arr){7 cout << num;8}1lst = [10,20,30]2for num in lst:3 print(num)1lst = [10,20,30]2for i in range(len(lst)):3 print(lst[i])_#(不需要用到循环变量的值,只需要循环跑 n 次)
1for(int i=0; i<3; i++){2 cout << "hello";3}1for _ in range(3):2 print("hello")1for(int i = 0; i < 3; i++){2 for(int j = 0; j < 3; j++){3 cout << i*j << " ";4 }5 cout << endl;6}1for i in range(3):2 for j in range(3):3 print(i*j, end=" ")4 print() #内层循环跑完一行,换行break:直接跳出整个循环continue:跳过本次循环剩下代码,直接进入下一轮| 功能 | C++ 写法 | Python 写法 | 坑点 |
|---|---|---|---|
| 循环 0~4 | for(int i=0;i<5;i++) | for i in range(5) | range 终点取不到 |
| 循环 1~5 | for(int i=1;i<=5;i++) | for i in range(1,6) | 很多人忘记 + 1 |
| 倒序 5~1 | for(int i=5;i>=1;i--) | for i in range(5,0,-1) | 结束写 0,不是 1 |
| 遍历数组元素 | for(auto x:a) | for x in lst: | Python 不用下标 |
| 循环 n 次不用 i | for(int i=0;i<n;i++) | for _ in range(n) | _只是约定,不是关键字 |
1#include <iostream>2using namespace std;3int main(){4 int n;5 cin >> n; //输入6 for(int i=0;i<n;i++){7 for(int j=0;j<n;j++){8 cout << i*j << " ";9 }10 cout << endl; //换行11 }12 return 0;13}end=" ":print 默认会换行,end=" "改成用空格隔开,不换行
1# 1. 输入:读取一个整数n2n = int(input())3
4# 2. 嵌套循环,n行n列5for i in range(n):6 for j in range(n):7 print(i*j, end=" ")8 print()py的字符串是不可变的(阴间)
操作先转列表,再转字符串
1# 1.输入一串字符2s = input("请输入一串字符:")3# 2.转为列表,每个字符单独放进去4lst = list(s)5
6# ==========中间操作在这里写==========7# 举几个常见操作例子,你可以按需修改8# 例1:把下标0的字符改成大写9lst[0] = lst[0].upper()10# 例2:反转整个字符列表11lst.reverse()12# 例3:删除第2个字符(下标1)13# del lst[1]14# ====================================15
16# 3.列表转回字符串17result = ''.join(lst)18print("处理后的字符串:", result)蓝桥杯py常用语法(面向小白,便于速成)_哔哩哔哩_bilibili
1lis=list(map(int,input().split()))2
3print(lis)
[P16235 蓝桥杯 2026 省 B] 蓝桥竞技 - 洛谷
1t = int(input())2
3for _ in range(t):4
5 n = int(input())6
7 a=list(map(int,input().split()))8
9 total=sum(a)10
11 if(total%5!=0):12 #print(" 该轮失败: total ")13 print("F")14 continue15
16 k=total//517 flag=True18
19 print(k)20
21 for num in a:22 if num>k:23 flag=False24 print(" 该轮失败: k ")25 print(num)26 break27
28 print("T" if flag else "F")1# 列表字符串2s=list(input().strip())3print(s)
1# 创建分配列表2lis=[0]*1003# 创造n行m列4lit = [[0 for i in range(m)] for j in range(n)]5
6lit = [[0 for _ in range(m)] for _ in range(n)]7
8lit = [[0] * m for _ in range(n)]9#这是**列表推导式**,一次性生成包含 2 个列表的二维列表(2 行网格),等价于下面完整循环写法:10grid = [list(input().strip()) for _ in range(2)]11
12# 列表叠加器创造列表13lit=[[0 for i in range(3)] for j in range(3)]14lit[1][1]=115print(lit)
1import sys2
3input = sys.stdin.readline4
5# 读取 n 和 m6n, m = map(int, input().split())7
8# 读取 n 个字符串 S 一行一行读9s = [input().strip() for _ in range(n)]10
11# 读取 m 个字符串 T12t = [input().strip() for _ in range(m)]13
14print(s)15print(t)1# 创建分配列表2lis=[1]*63
4# 列表叠加器创造列表5lit=[[0 for i in range(3)] for j in range(3)]6lit[1][1]=17print(lit)8
9# 以空格为分格符10print(" ".join(map(str,lit)))11print(*lit)12print(*lis)13print(" ".join(map(str,lis)))
1a=1.2291782b=03
4print(f"{a:.2f}")5print(f"{b:.3f}")6print(round(a,2))7print(round(b,2))
s.find(sub, start=0, end=len(s))#sub 在字符串s中第一次出现的下标start起始位置,end终止位置(左闭右开)python
运行
1"abcabc".find("bc") # 12"abcabc".find("xx") # -1s.index(sub, start=0, end=len(s))#find几乎一样,查找子串第一次出现下标python
运行
1"abcabc".index("bc") # 12"abcabc".index("xx") # ValueError: substring not found一句话区分 find vs index:找不到时,find 返回 - 1,index 报错
s.count(sub, start=0, end=len(s))#sub在指定区间不重叠出现的次数python
运行
1"aaaa".count("aa") # 2 (位置0、2,不会重叠计数)Python 字符串底层是朴素匹配(没有 KMP,CPython 实现)
设主串长度 n,子串长度 m
表格
| 方法 | 时间复杂度 | 说明 |
|---|---|---|
find() | (O(n\cdot m)) | 最坏情况逐位置比对 |
index() | (O(n\cdot m)) | 和 find 底层代码几乎一样,仅异常处理不同 |
count() | (O(n\cdot m)) | 遍历整串,每次尝试匹配子串 |
补充:
- 日常短字符串感受不出来差异;超大文本 + 长子串才会明显变慢
- 列表的
list.count():(O(n)),遍历一次列表逐个相等判断- 列表的
list.index():(O(n)),找到第一个匹配元素就停止⚠️ 列表没有 find ()!很多人容易混淆字符串和列表 API。
表格
| 函数 | 功能 | 未找到行为 | 复杂度 (字符串) | 复杂度 (列表) |
|---|---|---|---|---|
| find | 查找首次子串位置 | return -1 | (O(nm)) | 不存在 |
| index | 查找首次子串 / 元素位置 | 抛 ValueError | (O(nm)) | (O(n)) |
| count | 统计匹配次数 | 返回 0 |
1s.add(x) # 添加元素,存在则无变化2s.remove(x) # 删除元素,不存在抛KeyError3s.discard(x) # 删除元素,不存在不报错4s.pop() # 随机删除一个元素并返回5s.clear() # 清空集合6
7# 集合运算8a & b # 交集 a.intersection(b)9a | b # 并集 a.union(b)10a - b # 差集 a.difference(b)11a ^ b # 对称差集(只在其中一个里面的元素)判断元素 a 是否存在于集合中,存在返回 True,不存在返回 False
1s = {1,2,3}2print(2 in s) # True3print(5 in s) # FalseO(log(n))
返回最小值,py 里面只要小分堆,大分堆加负号使用
1import heapq2q=[]3heapq.heappush(q,2)4heapq.heappush(q,1)5print(q)6# 弹出并返回堆顶最小值,7print(heapq.heappop(q))8print(q)9print(len(q))
1a=bin(3)2print(a)3print(a[2:])
1a=92lis=list(map(int,bin(a)[2:].zfill(10).strip()))3print(lis)
bin(a)#bin() 把整数转二进制字符串,自带前缀 0b
python
运行
1bin(9) # '0b1001'9 的二进制:(8+1 = 1001_2)
bin(a)[2:]#切片从下标 2 开始,切掉前面的 0b
python
运行
1bin(9)[2:] # '1001'.zfill(10)#zfill(n):在字符串左侧补 0,让总长度等于 n
'1001' 长度是 4,左边补 6 个 0 →
python
运行
1'1001'.zfill(10) # '0000001001'.strip()#strip ():删除字符串首尾空白字符(空格、换行等)
这里字符串
'0000001001'首尾没有空格,strip 在这里等于没作用,多余代码
map(int, 字符串)#字符串是'0000001001',遍历每一个字符,逐个转 int
1'0'→0, '0'→0 ... '1'→1list(...)#把 map 对象转为列表,得到最终:
python
运行
1[0, 0, 0, 0, 0, 0, 1, 0, 0, 1]把数字 9 转为10 位定长二进制列表(高位补 0)
注意:
strip()在这里是无效冗余代码,可以删掉。
python
运行
1a=92lis=list(map(int,bin(a)[2:].zfill(10)))3print(lis)zfill 是左边补 0;rjust 也可以实现同样效果bin(a)[2:][::-1]1lis=[1,3,2,4,5]2lis.sort()3print(lis)4lis.sort(reverse=True)5print(lis)
1lis=[[1,2],2 [3,4],3 [7,1]4 ]5# 根据第二个值对整个列表排序6lis.sort(key=lambda x : x[1])7print(lis)
1lis=[[1,2],2 [3,4],3 [7,4]4 ]5# 先根据第二个值,再根据第一个值对整个列表排序6lst.sort(key=lambda x: (x[1],x[0]))7lis.sort(key=lambda x : (x[1],x[0]))8print(lis)
1import sys2
3d = list(map(int, sys.stdin.buffer.read().split()))4
5n, k = d[0], d[1]6a = d[2:]7
8
9def key(x):10 # 转成二进制字符串,例如 13 -> "1101"11 s = bin(x)[2:]12
13 # 统计二进制中 1 的个数14 cnt = s.count('1')15
16 # 0 特殊处理17 if x == 0:18 low = 3119 else:20 # 从右往左查找第一个 121 # 位置从 0 开始22 low = s[::-1].index('1')23
24 # Python 会依次比较 cnt、low、x25 return cnt, low, x26
27
28a.sort(key=key)29
30print(a[k - 1])1import bisect2
3lis=[1,2,4,3,5,4]4 # 查找第一个大于等于4的下标5print(bisect.bisect_left(lis,4))
1import bisect2
3lis=[1,5,4,3,5,4]4 # 查找第一个大于4的下标5print(bisect.bisect_right(lis,4))
1a="A"2
3print(ord(a))
1a=652
3print(chr(a))
1import sys2
3input = lambda: sys.stdin.readline().strip()4
5n = input()6print(int(n, 16))1bin(n)e.g
1bin(16) # '0b10000'1import math2# 找最小公倍数3print(math.gcd(4,6))
1import math2# kai'f3print(math.sqrt(4))
1s[start:end:step]
1class Solution:2 def repeatedSubstringPattern(self, s: str) -> bool:3 # s拼接后去掉首尾4 return s in (s+s)[1:-1][:-1] 是 Python 的切片写法,表示:
从开头开始,取到倒数第一个元素之前,不包含倒数第一个元素。

1b=lst[::-1]库函数
1#`isalnum()` 用于判断字符是否是:2
3- 英文字母4- 数字
1class Solution:2 def isPalindrome(self, s: str) -> bool:3 n=len(s)4 l=05 r=n-16 while(l<r):7 if not s[l].isalnum():8 l+=19 elif not s[r].isalnum():10 r-=111 elif(s[l].lower()==s[r].lower()):12 l+=113 r-=114 else:15 return False16 return True
1(suc+c-1)//c二分

1def lower_bound(pot: list[int], suc1: int) -> list[int]:2 l=03 r=len(pot)-14
5 while(l<=r):6 m=(l+r)//27 if(pot[m]>=suc1):8 r=m-19 else:10 l=m+111 return l12
13class Solution:14 def successfulPairs(self, spells: list[int], potions: list[int], suc: int) -> list[int]:15 pairs=[]16 potions.sort()17 for c in spells:18 #cnt=019 k1=(suc+c-1)//c20 st=lower_bound(potions,k1)21 pairs.append(len(potions)-st)22
23 return(pairs)在 Python 中,“逆元”通常指模逆元:

直接使用:
Python
1y = 32mod = 73
4inv_y = pow(y, -1, mod)5print(inv_y) # 5因为:


Python
1y_inv = pow(y, -1, mod)注意:只有当 gcd(y, mod) == 1 时逆元存在,否则会报错。
Python
1pow(2, -1, 4) # ValueError,因为 2 和 4 不互质如果模数是质数 MOD,根据费马小定理:
Python
1inv_y = pow(y, MOD - 2, MOD)例如:
Python
1MOD = 10**9 + 72y = 33
4inv_y = pow(y, MOD - 2, MOD)模逆元的核心应用是:在模运算中实现“除法”。

1MOD = 10**9 + 72
3def combination(n, k):4 if k < 0 or k > n:5 return 06
7 fact = [1] * (n + 1)8
9 for i in range(1, n + 1):10 fact[i] = fact[i - 1] * i % MOD11
12 numerator = fact[n]13 denominator = fact[k] * fact[n - k] % MOD14
15 # denominator 的逆元16 denominator_inv = pow(denominator, MOD - 2, MOD)17
18 return numerator * denominator_inv % MOD
1MOD = 10**9 + 72
3def combination(n, k):4 if k < 0 or k > n:5 return 06
7 fact = [1] * (n + 1)8
9 for i in range(1, n + 1):10 fact[i] = fact[i - 1] * i % MOD11
12 numerator = fact[n]13 denominator = fact[k] * fact[n - k] % MOD14
15 # denominator 的逆元16 denominator_inv = pow(denominator, MOD - 2, MOD)17
18 return numerator * denominator_inv % MOD
1MOD = 10**9 + 72
3x1, y1 = 1, 24x2, y2 = 4, 85
6dy = (y2 - y1) % MOD7dx = (x2 - x1) % MOD8
9slope = dy * pow(dx, MOD - 2, MOD) % MOD
1print(''.join(ans))表示:把列表 ans 中的所有字符串拼接起来,中间不添加任何字符,然后输出。
例如:
1ans = ['a', 'b', 'c']2print(''.join(ans))输出:
1abc这里:
1''是一个空字符串,表示拼接时不加分隔符。
如果写成:
1print(' '.join(ans))则会在元素之间加空格:
1ans = ['a', 'b', 'c']2print(' '.join(ans))输出:
1a b c如果写成:
1print(','.join(ans))输出:
1a,b,c在你前面的代码中:
1ans = ['1', '3', 'a']2print(''.join(ans))输出:
113a如果题目要求字符之间有空格,就使用:
1print(' '.join(ans))输出:
11 3 a1import sys2
3input = sys.stdin.readline4
5
6def solve():7 n = int(input())8 s = input().strip()9
10 r = []11
12 p = s[0]13 c = 114
15 # 连续相同字符压缩16 for i in range(1, n):17 if s[i] == p:18 c += 119 else:20 r.append(p + str(c))21 p = s[i]22 c = 123
24 r.append(p + str(c))25 r1=''.join(r)26 # 统计压缩后字符串中每个字符出现的次数27 cnt = {}28 for ch in r1:29 cnt[ch]=cnt.get(ch,0)+130
31
32 mx = max(cnt.values())33
34 # sorted 默认按照 ASCII 码从小到大排序35 ans = []36
37 for ch in sorted(cnt):38 if cnt[ch] == mx:39 print(ch,end=' ')40
41
42if __name__ == "__main__":43 solve()1import sys2import math3import bisect4import heapq5from collections import deque, Counter, defaultdict6
7#sys.set_int_max_str_digits(0)8
9input = sys.stdin.readline10
11INF = 10**1812mod = 99824435313
14directions = [15 (-1, 0),16 (1, 0),17 (0, -1),18 (0, 1),19]20
21X4 = [1, 0, -1, 0]22Y4 = [0, 1, 0, -1]23
24X8 = [0, 1, 1, 1, 0, -1, -1, -1]25Y8 = [1, 1, 0, -1, -1, -1, 0, 1]26
27Xh = [1, 2, 2, 1, -1, -2, -2, -1]28Yh = [2, 1, -1, -2, -2, -1, 1, 2]29
30
31def solve():32 n = int(input())33 s=input().strip()34 s+=' '35 st=[]36 l=137 for i in range(1,len(s)):38 if(s[i]==s[i-1]):39 l+=140 else:41 st.append(s[i-1])42 st.append(str(l))43 l=144 #print(''.join(st))45 # 将列表拼接成完整压缩字符串46 r = ''.join(st)47 cnt1=[0]*2648 cnt2=[0]*1049
50 for ch in r:51 if 'a'<=ch<='z':52 cnt1[ord(ch)-ord('a')]+=153 elif '0' <= ch <= '9':54 cnt2[ord(ch) - ord('0')] += 155
56 mx1=max(cnt1)57 mx2=max(cnt2)58 # print(mx1)59 # print(mx2)60 if(mx1==mx2):61 for i in range(10):62 if(cnt2[i]==mx2):63 print(chr(i+ord('0')),end=' ')64 for i in range(26):65 if(cnt1[i]==mx1):66 print(chr(i+ord('a')),end=' ')67 elif(mx1>mx2):68 for i in range(26):69 if(cnt1[i]==mx1):70 print(chr(i+ord('a')),end=' ')71 else:72 for i in range(10):73 if(cnt2[i]==mx2):74 print(chr(i+ord('0')),end=' ')75
76if __name__ == "__main__":77 solve()78
79"""80 @@@ @ @ @ @@ @ @@81 @@@ @ @ @ @ @ @@@ @@ @@82 @@ @ @@@ @ @ @ @ @ @ @ @ @ @@83 @@ @@ @@ @ @ @ @ @ @ @ @ @ @@ @ @ @ @@84 @@ @ @ @@@ @ @ @@@ @ @ @ @ @ @ @ @ @ @@ @@85@@ @ @ @ @ @ @ @ @ @ @ @ @ @ @@ @ @ @@86@ @ @ @ @ @ @ @ @ @ @ @ @ @@@ @ @ @ @ @@87 @ @ @ @ @ @ @ @ @ @ @ @@@@@@@@ @ @@ @ @ @ @ @ @88@ @ @ @ @ @ @@ @ @ @ @ @ @ @ @@@@@ @ @ @ @89 @ @ @ @ @ @ @ @ @ @ @ @@ @@@@@@@@ @ @ @ @ @ @ @ @@90 @ @ @ @ @ @ @ @ @@@@ @ @@ @ @ @@@ @ @ @ @ @@91 @ @ @ @ @ @ @ @ @@ @ @ @ @ @ @ @ @ @ @92@ @@ @ @ @ @ @@ @ @@@ @ @ @ @@ @ @ @ @ @ @ @ @ @93@ @ @ @ @ @ @@ @ @@@ @ @ @ @ @@@@@@@@@@@ @ @ @ @ @ @ @94@ @ @ @ @ @ @@ @ @ @ @ @ @ @ @ @@@ @ @@ @ @ @ @ @ @ @95 @ @ @ @ @ @ @ @ @ @ @ @ @ @@@ @ @ @ @ @ @ @96@@@ @ @ @ @ @ @@@@@@@@@ @ @ @ @@ @ @ @ @ @ @ @ @ @ @97@ @ @ @ @ @ @@ @ @ @ @ @ @ @ @@ @ @@ @ @ @ @ @ @98 @ @ @ @ @ @@ @ @ @@@ @ @ @ @@ @ @ @@ @ @@ @ @ @ @ @99 @ @ @ @ @ @ @ @ @@ @ @ @ @ @ @ @@ @@ @ @ @ @ @ @ @100 @ @ @ @@ @ @@ @@ @ @ @ @ @ @@ @ @ @@ @@ @ @ @ @ @ @101 @ @ @ @ @ @ @ @ @@ @@@@@ @ @ @ @@ @@@@ @@ @ @@ @ @ @ @ @ @102 @ @@ @ @ @@ @ @ @@@ @ @ @@ @ @@ @@ @ @ @ @ @ @ @103@@ @ @ @@ @ @ @ @ @@ @ @ @ @ @ @ @ @ @ @ @ @104@ @ @ @ @@ @ @ @@ @ @@@@@ @@ @ @ @ @ @ @105@ @ @ @ @ @ @ @@@ @ @ @ @ @ @106@ @@ @ @ @@@ @ @ @@ @ @ @ @ @107 @ @ @ @ @ @ @@ @ @ @ @ @@ @108 @ @ @ @ @ @ @ @@@ @@ @ @ @ @ @ @@109 @@@ @ @ @@ @ @ @@@ @ @ @ @ @110 @ @ @ @ @ @ @@@@ @@ @ @ @ @ @ @111 @ @ @ @ @@@@ @@ @@ @@@ @ @ @112 @ @ @ @ @@ @ @@ @ @ @ @113 @ @ @ @ @ @ @ @ @@@@@@@@ @@@ @ @ @ @ @ @ @@114 @ @ @ @ @ @ @ @@ @@@@@@@@ @@@ @ @ @ @ @@ @@115 @ @ @ @ @ @ @ @@ @@@@@@ @ @ @ @ @ @@ @ @116 @ @ @ @ @ @ @@@ @ @ @@ @ @ @@ @ @ @ @ @ @@117 @ @@ @ @ @ @ @ @@ @ @@ @ @ @ @ @@118 @@ @@@ @ @@@@@ @ @@ @@@@ @@@@ @@ @ @ @@ @ @ @@119 @@ @ @@ @ @ @ @@ @@ @@ @ @ @@@ @@@@120 @@ @ @ @ @@ @@ @@@ @ @ @@ @@121 @@ @@ @ @ @ @@@@ @ @ @@@@@ @@ @ @ @ @ @@@@122 @@ @ @ @ @ @@ @ @@@@ @ @ @ @@123 @ @@ @ @ @ @@@ @@ @ @@ @ @ @ @124 @ @ @ @ @@ @ @ @ @ @ @@ @ @ @@ @ @@@125"""增减性单调的情况

1class Solution:2 def peakIndexInMountainArray(self, arr: List[int]) -> int:3 l=04 r=len(arr)-15 mid=06 while(l<r):7 mid=(l+r)//28 if(arr[mid-1]<arr[mid] and arr[mid]>arr[mid+1]):9 break10 #下降段:mid可能就是r11 elif(arr[mid]>arr[mid+1]):12 r=mid13 #上升段:mid一定不是l14 elif(arr[mid]<arr[mid+1]):15 l=mid+116 return mid1class Solution:2 def peakIndexInMountainArray(self, arr: List[int]) -> int:3 l=04 r=len(arr)-25 while(l<=r):6 m=(l+r)//27 if(arr[m]<arr[m+1]):8 l=m+19 else:10 r=m-111 return l34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)


最后一个 ≤ x = 第一个 > x 的位置 - 1 最后一个 < x = 第一个 ≥ x 的位置 - 1
1#[] 左右闭区间2def lower_bound(nums: list[int], target: int) -> list[int]:3 l=04 n=len(nums)5 r=n-16 while(l<=r):7 #写在循环里面8 m=(l+r)//29 if(nums[m]<target):10 l=m+111 else:12 r=m-113 return l14
15class Solution:16 def searchRange(self, nums: list[int], target: int) -> list[int]:17 start=lower_bound(nums,target)18 if(start>=len(nums) or nums[start]!=target):19 return [-1,-1]20 end=lower_bound(nums,target+1)-121 return [start,end]1class Solution:2 # lower_bound 返回最小的满足 nums[i] >= target 的下标 i3 # 如果数组为空,或者所有数都 < target,则返回 len(nums)4 # 要求 nums 是非递减的,即 nums[i] <= nums[i + 1]5 def lower_bound(self, nums: List[int], target: int) -> int:6 left, right = 0, len(nums) - 1 # 闭区间 [left, right]7 while left <= right: # 区间不为空8 # 循环不变量:9 # nums[left-1] < target10 # nums[right+1] >= target11 mid = (left + right) // 212 if nums[mid] >= target:13 right = mid - 1 # 范围缩小到 [left, mid-1]14 else:15 left = mid + 1 # 范围缩小到 [mid+1, right]16 # 循环结束后 left = right+117 # 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target18 # 所以 left 就是第一个 >= target 的元素下标19 return left20
21 def searchRange(self, nums: List[int], target: int) -> List[int]:22 start = self.lower_bound(nums, target)23 if start == len(nums) or nums[start] != target:24 return [-1, -1] # nums 中没有 target25 # 如果 start 存在,那么 end 必定存在26 end = self.lower_bound(nums, target + 1) - 127 return [start, end]28
29#[)左闭右开30
31class Solution:32 # lower_bound 返回最小的满足 nums[i] >= target 的下标 i33 # 如果数组为空,或者所有数都 < target,则返回 len(nums)34 # 要求 nums 是非递减的,即 nums[i] <= nums[i + 1]35 def lower_bound(self, nums: List[int], target: int) -> int:36 left, right = 0, len(nums) # 左闭右开区间 [left, right)37 # 有开区间不等于38 while left < right: # 区间不为空39 # 循环不变量:40 # nums[left-1] < target41 # nums[right] >= target42 mid = (left + right) // 243 if nums[mid] >= target:44 right = mid # 范围缩小到 [left, mid)45 else:46 left = mid + 1 # 范围缩小到 [mid+1, right)47 # 循环结束后 left = right48 # 此时 nums[left-1] < target 而 nums[left] = nums[right] >= target49 # 所以 left 就是第一个 >= target 的元素下标50 return left51
52 def searchRange(self, nums: List[int], target: int) -> List[int]:53 start = self.lower_bound(nums, target) # 选择其中一种写法即可54 if start == len(nums) or nums[start] != target:55 return [-1, -1] # nums 中没有 target56 # 如果 start 存在,那么 end 必定存在57 end = self.lower_bound(nums, target + 1) - 158 return [start, end]59
60#() 左右开区间61class Solution:62 # lower_bound 返回最小的满足 nums[i] >= target 的下标 i63 # 如果数组为空,或者所有数都 < target,则返回 len(nums)64 # 要求 nums 是非递减的,即 nums[i] <= nums[i + 1]65 def lower_bound(self, nums: List[int], target: int) -> int:66 left, right = -1, len(nums) # 开区间 (left, right)67 while left + 1 < right: # 区间不为空68 mid = (left + right) // 269 # 循环不变量:70 # nums[left] < target71 # nums[right] >= target72 if nums[mid] >= target:73 right = mid # 范围缩小到 (left, mid)74 else:75 left = mid # 范围缩小到 (mid, right)76 # 循环结束后 left+1 = right77 # 此时 nums[left] < target 而 nums[right] >= target78 # 所以 right 就是第一个 >= target 的元素下标79 return right80
81 def searchRange(self, nums: List[int], target: int) -> List[int]:82 start = self.lower_bound(nums, target) # 选择其中一种写法即可83 if start == len(nums) or nums[start] != target:84 return [-1, -1] # nums 中没有 target85 # 如果 start 存在,那么 end 必定存在86 end = self.lower_bound(nums, target + 1) - 187 return [start, end]

1class Solution:2 def maximumCount(self, nums: List[int]) -> int:3 neg = bisect_left(nums, 0)4 pos = len(nums) - bisect_right(nums, 0)5 return max(neg, pos)6
7作者:灵茶山艾府8链接:https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/solutions/2050916/mo-ni-by-endlesscheng-8e43/9来源:力扣(LeetCode)10著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


最重要的不是看到“两根指针”就套模板,而是证明:
为什么移动这个指针是安全的?被跳过的情况为什么不可能再成为答案?
这类双指针题目不能死记“固定左边”或“固定右边”,核心是看:
固定一个变量后,剩下两个变量是否具有单调性,能否用两个指针一次遍历完成

这不是双指针做法!
1class Solution:2 def moveZeroes(self, nums: list[int]) -> None:3 """4 Do not return anything, modify nums in-place instead.5 """6 n=len(nums)7 k=08 for i in range(n):9 if(nums[i]!=0):10 nums[k]=nums[i]11 k+=112
13 for i in range(k,n):14 nums[i]=0双指针+快排做法
left指针指0
1class Solution:2 def moveZeroes(self, nums: list[int]) -> None:3 """4 Do not return anything, modify nums in-place instead.5 """6 n=len(nums)7 left=right=08
9 while right<n:10 if(nums[right]!=0):11 nums[right],nums[left]=nums[left],nums[right]12 left+=113
14 right+=1167. 两数之和 II - 输入有序数组 - 力扣(LeetCode)

1class Solution:2 def twoSum(self, nums: list[int], target: int) -> list[int]:3 nums.sort()4 left=05 right=len(nums)-16
7 while(left<right):8 lst=[]9 if(nums[left]+nums[right]==target):10 lst.append(left+1)11 lst.append(right+1)12 return lst13 elif(nums[left]+nums[right]>target):14 right-=115 else:16 left+=1三数之和

1class Solution:2 def threeSum(self, nums: list[int]) -> list[list[int]]:3 nums.sort()4 res=[]5 n=len(nums)6 for i in range(0,n-2):7 x=nums[i]8
9
10 j=i+111 k=n-112 if (i>0 and x==nums[i-1]):13 continue14 while(j<k):15 if(nums[i]+nums[j]+nums[k]>0):16 k-=117 elif(nums[i]+nums[j]+nums[k]<0):18 j+=119 else:20 res.append([nums[i],nums[j],nums[k]])21 j+=122 while(j<k and nums[j]==nums[j-1]):23 j+=124 k-=125 while(k>j and nums[k]==nums[k+1]):26 k-=127
28 return res

1class Solution:2 def trap(self, height: list[int]) -> int:3 #由一段区间的较小部分决定,区间范围到下一个比初始大的结束4 #怎么统计面积5 # 前后缀 min(pre_max,suf_max)-helight->每单位木桶的水6 ans=07 n=len(height)8
9 pre_max=[0]*n10 suf_max=[0]*n11
12 pre_max[0]=height[0]13 suf_max[-1]=height[-1]14
15 for i in range(1,n):16 pre_max[i]=max(pre_max[i-1],height[i])17 for i in range(n-2,-1,-1):18 suf_max[i]=max(suf_max[i+1],height[i])19 for pre,suf,h in zip(pre_max,suf_max,height):20 ans+=min(pre,suf)-h21 return ans双指针
单调栈
enumerate() 用于遍历序列时同时获取下标和值
1enumerate(iterable, start=0)iterable:可迭代对象,如列表、字符串、元组start:下标起始值,默认是 01items = ["apple", "banana", "orange"]2
3for index, value in enumerate(items):4 print(index, value)等价于
1for index in range(len(items)):2 print(index, items[index])输出
10 apple21 banana32 orange转换成了列表
1items = ["apple", "banana", "orange"]2result=list(enumerate(items))3print(result)
1names = ["Tom", "Jerry", "Alice"]2
3for index, name in enumerate(names, start=1):4 print(index, name)输出
11 Tom22 Jerry33 Alice1for index, char in enumerate("Python"):2 print(index, char)
哈希法
1class Solution:2 def twoSum(self, nums: List[int], target: int) -> List[int]:3 idx = {} # 创建一个空哈希表(字典)4 for j, x in enumerate(nums): # x=nums[j]5 #`in idx` 默认检查的是**字典的键**6 if target - x in idx: # 在左边找 nums[i],满足 nums[i]+x=target7 return [idx[target - x], j] # 返回两个数的下标8 idx[x] = j # 保存 nums[j] 和 j9 #放在判断后,防止自己和自己配对10
11作者:灵茶山艾府12链接:https://leetcode.cn/problems/two-sum/solutions/2326193/dong-hua-cong-liang-shu-zhi-he-zhong-wo-0yvmj/13来源:力扣(LeetCode)14著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。collections 模块中的一个计数器,本质上是字典的子类,专门用来统计元素出现次数。
1from collections import Counter2
3nums = [1, 2, 1, 3, 2, 1]4
5count = Counter(nums)6
7print(count)输出
1Counter({1: 3, 2: 2, 3: 1})11 出现 3 次22 出现 2 次33 出现 1 次统计字符串的字符
1from collections import Counter2
3s = "hello"4
5count = Counter(s)6
7print(count)cnt.items() 是什么
先回顾:cnt = Counter(st) Counter 是 collections 里的计数容器,本质是字典(dict)的子类:
👉 cnt.items() 返回一个可迭代对象,里面每一项是 (key, value) 二元组 格式:(单词, 出现次数)
1#访问:2for i ,x in cnt.items():
1class Solution:2 def minSubArrayLen(self, target: int, nums: list[int]) -> int:3 n=len(nums)4 size=n+15 left=06 sum=07 for right,x in enumerate(nums):8 sum+=x9 while sum-nums[left]>=target:10 sum-=nums[left]11 left+=112
13 if sum>=target:14 size=min(size,right-left+1)15
16 return 0 if size==n+1 else size
1class Solution:2 def lengthOfLongestSubstring(self, s: str) -> int:3 ans=04 left=05 #创建一个空的 `Counter`,它可以当作一个“自动计数的字典”使用6
7 cnt=Counter() #hashmap char int8 #cnt[char]=int cnt内部包裹9
10 for right,x in enumerate(s):11 cnt[x]+=112 while cnt[x]>1:13 cnt[s[left]]-=114 left+=115 ans=max(ans,right-left+1)16 return ans哈希集合
1class Solution:2 def lengthOfLongestSubstring(self, s: str) -> int:3 ans=04 left=05 windows=set()6 for r,c in enumerate(s):7 while c in windows:8 windows.remove(s[left])9 left+=110 windows.add(c)11 ans=max(ans,r-left+1)12 return ans如果 d 是 n 的正因数,那么:
d 和 -d 都可能是因数。

1import sys2from math import isqrt3input=lambda:sys.stdin.readline().strip()4
5def ysh(n):6 result=[]7 # 枚举因数,平方根优化8 limit=isqrt(abs(n))9
10 for d in range(1,limit+1):11 if(n%d==0):12 # e.g 3 -313 result.append(d)14 result.append(-d)15 # 枚举另一半的因数 e.g(12/3=4)16 other=abs(n)//d17 if(other!=d):18 result.append(other)19 result.append(-other)20
21 return result22
23t=int(input())24
25for _ in range(t):26 a,b,c=map(int,input().split())27
28 #a!=029 flag=0 # 有没有解 初始化无解30
31 for a1 in ysh(a):32 a2=a//a133
34 # c!=0 b!=035 if(c!=0):36 for b2 in ysh(c):37 b1=c//b238 if(a1*b2+a2*b1==b):39 print(a1,b1,a2,b2)40 flag=141 break42 # c=0 b1=0/b2=043 else:44 # b1=0 a1*b2=b45 if(b%a1==0):46 b1=047 b2=b//a148 print(a1,b1,a2,b2)49 flag=150
51 # b2=0 a2*b1=b52 elif(b%a2==0):53 b2=054 b1=b//a255 print(a1,b1,a2,b2)56 flag=157 if(flag==1):58 break59
60 if(flag==0):61 print("NO")判定条件:

1import sys2from math import isqrt3input=lambda:sys.stdin.readline().strip()4
5def pdss(t):6 if(t<2):7 return False8 elif(t==2):9 return True10 elif(t%2==0):11 return False12 else:13 t1=isqrt(t)14 for i in range(3,t1+1,2):15 if(t%i==0):16 return False17 return True(找出质数)
段代码是在用埃拉托斯特尼筛法,一次性找出 2 ~ 10005 之间的所有质数。
1m = 100052vis = [False] * (m + 1)3pri = []m:筛选范围上限。vis[i]:表示数字 i 是否已经被确定为合数。
False:暂时没被标记,可能是质数。True:一定是合数。pri:保存找到的质数。核心代码:
1for i in range(2, m + 1):2 if not vis[i]:3 pri.append(i)4
5 for j in range(i * i, m + 1, i):6 vis[j] = True具体过程:
i 没被标记#1if not vis[i]:说明 i 是质数。
例如开始时:
1i = 22 没有被标记,所以 2 是质数。
1pri.append(2)把 2 加入质数数组。
i 的倍数#1for j in range(i * i, m + 1, i):2 vis[j] = True当 i = 2 时,会标记:
14, 6, 8, 10, 12, ...因为它们都是 2 的倍数,一定不是质数。
当 i = 3 时,会标记:
19, 12, 15, 18, ...当 i = 5 时,会标记:
125, 30, 35, ...最终,所有没有被标记的数就是质数。
为什么从 i * i 开始?
以 i = 5 为例:
15 * 2 = 1025 * 3 = 1535 * 4 = 20这些数已经分别被 2、3、4 标记过了,所以不需要重复标记。第一个可能还没被标记的倍数就是:
15 * 5 = 25因此从 i * i 开始可以提高效率。
例如最终:
1pri[:10]大致是:
1[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]你看到的:
1[i \* i]其中的反斜杠只是网页显示时的转义,实际 Python 代码应写成:
1[i * i]
取模
1(a % m + b % m) % m = (a + b) % m2(a % m × b % m) % m = (a × b) % m
1.定义状态
1dp[i]=以s[i]结尾的最长合法的偶子串长度2.找状态转移
如果最后两个相同
1s[i]==s[i-1]可以组成一对偶子串
1dp[i]=当前长度+2即
1dp[i]=dp[i-2]+2如果不相同
1dp[i]=0求最终答案
1ans=max(dp[i])1import sys2input=lambda:sys.stdin.readline().strip()3
4s=input()5n=len(s)6ans=07dp=[0]*n8for i in range(1,n):9 if(s[i]==s[i-1]):10 if(i>=2):11 dp[i]=dp[i-2]+212 else:13 dp[i]=214 ans=max(ans,dp[i])15
16print(ans)D - Installation of Street Lights


核心公式:
1dp[right + 1] = min(dp[right + 1], dp[left] + cost)意思是:
用当前这盏灯覆盖一段房子后,更新 dp[right + 1],取原来的方案和新方案中花费较小的那个。
假设当前灯覆盖下标:
Plain text
1left 到 right例如:
Plain text
1left = 22right = 4说明当前灯覆盖第 2、3、4 栋房子。
Python
1dp[right + 1]也就是:
Python
1dp[5]表示:
照亮前 5 栋房子的最小花费。
因为下标 0, 1, 2, 3, 4 一共是 5 栋。
当前灯覆盖:
Plain text
1left 到 right那么在使用当前灯之前,前面的 left 栋房子已经被照亮:
Python
1dp[left]当前灯花费:
Python
1cost所以新方案总花费是:
Python
1dp[left] + costPython
1dp[right + 1] = min(2 dp[right + 1],3 dp[left] + cost4)可以读成:
Plain text
1dp[right + 1] 等于以下两个数中较小的一个:2
31. dp[right + 1]:原来的最优方案42. dp[left] + cost:先照亮前 left 栋,再安装当前灯假设:
Python
1left = 22right = 43dp[2] = 54cost = 95dp[5] = 20当前灯覆盖第 2 到第 4 栋房子。
新方案花费:
Python
1dp[2] + 9 = 5 + 9 = 14原来照亮前 5 栋房子需要:
Python
1dp[5] = 20所以更新为:
Python
1dp[5] = min(20, 14)结果:
Python
1dp[5] = 14也就是找到了一种更便宜的方案。
你只需要记住这一句:
Python
1dp[右端点 + 1] = min(原来的花费, 前面的花费 + 当前灯的花费)right + 1 不是“多覆盖一栋房子”,而是因为下标从 0 开始,前 right + 1 栋房子的最后下标正好是 right。
假设有 5 栋房子,下标是:
Plain text
1房子下标: 0 1 2 3 42房子数量: 1 2 3 4 5所以:
0,一共覆盖 1 栋;0~1,一共覆盖 2 栋;0~2,一共覆盖 3 栋;0~4,一共覆盖 5 栋。规律就是:
Plain text
1覆盖到下标 right2=> 一共覆盖 right + 1 栋房子因此要记录到:
Python
1dp[right + 1]dp[i] 的含义#我们规定:
Python
1dp[i] = 照亮前 i 栋房子的最小花费这里的“前 i 栋”是:
Plain text
1下标 0 到 i-1例如:
Python
1dp[3]表示照亮:
Plain text
1下标 0、1、2一共 3 栋房子。
不是表示下标为 3 的那一栋房子。
假设当前灯覆盖:
Plain text
1left = 22right = 4也就是覆盖:
Plain text
1下标 2、3、4前面已经覆盖的是:
Plain text
1下标 0、1一共 2 栋,所以之前的状态是:
Python
1dp[left] = dp[2]使用当前灯后,覆盖范围变成:
Plain text
1下标 0、1、2、3、4一共 5 栋房子,所以应该更新:
Python
1dp[5]而:
Python
1right + 1 = 4 + 1 = 5所以代码是:
Python
1dp[right + 1] = min(dp[right + 1], dp[left] + cost)Plain text
1下标: 0 1 2 3 42 |----|----|----|----|3前两栋: 已覆盖 已覆盖4
5当前灯覆盖: [---- 2、3、4 ----]6
7最终覆盖: [0、1、2、3、4]8 一共 5 栋所以最终状态是:
Python
1dp[5]而不是 dp[4]。
dp[right]?#如果写成:
Python
1dp[right]例如 right = 4,那表示:
Python
1dp[4]也就是只表示前 4 栋房子:
Plain text
1下标 0、1、2、3它漏掉了下标为 4 的那栋房子。
所以必须写:
Python
1dp[right + 1]如果当前灯覆盖:
Plain text
1left 到 right那么:
Python
1dp[left]表示覆盖当前灯之前的房子;
Python
1dp[right + 1]表示覆盖当前灯之后的房子。
完整转移:
Python
1dp[right + 1] = min(2 dp[right + 1],3 dp[left] + cost4)读作:
覆盖到下标 right,实际上已经覆盖了前 right + 1 栋房子。新的花费等于“前面的花费 + 当前灯的花费”。
和原来的方案比较,取较小值。
现在换一种枚举方式。
我们枚举当前灯覆盖的最右边房子 right。
假设:
houses[right]radius如果它最早覆盖到 left,必须满足:

Python
1min_position = houses[right] - 2 * radius我们要找:
第一个坐标大于等于 min_position 的房子。
因为房子坐标已经排序,所以可以用二分查找:
左闭右开
1bisect_left(数组, 目标值, 起始位置, 结束位置)Python
1left = bisect_left(houses,min_position,0,right + 1)这里限制到 right + 1,是因为不能让 left 跑到 right 后面。
1import sys2from bisect import bisect_left3
4input = sys.stdin.readline5# n房屋数量,m路灯种类6n, m = map(int, input().split())7
8# 房屋坐标9x = list(map(int, input().split()))10x.sort()11
12# lp[i] = (照明半径, 安装费用)13lp = []14
15for _ in range(m):16 r, c = map(int, input().split())17 lp.append((r, c))18
19INF = 10 ** 3020
21# dp[i]:照亮前 i 栋房子的最小费用22dp = [INF] * (n + 1)23dp[0] = 024
25# 枚举当前灯覆盖的最右边房子26for i in range(n):27 # 枚举每种路灯28 # r照亮半径,c范围29 for r, c in lp:30 # 当前路灯最左能够覆盖到的坐标31 p = x[i] - 2 * r32
33 # 找到第一个坐标 >= p 的房子下标34 # bisect_left(数组, 目标值, 起始位置, 结束位置)35 l = bisect_left(x, p, 0, i + 1)36
37 # 当前路灯覆盖第 l 到第 i 栋房子38 # 前 l 栋房子已经被照亮39 dp[i + 1] = min(dp[i + 1], dp[l] + c)40
41print(dp[n])他妈的,我头要炸了,这dp 我晕了


https://gist.github.com/xue120754/d78ce0fa023c8590a540da77ae216aa9
1import sys2input = sys.stdin.buffer.readline3# N:阶段数量4# C:两个相邻阶段都通过时获得的额外奖励5N, C = map(int, input().split())6
7# 每个阶段单独通过时获得的分数8scores = list(map(int, input().split()))9
10# dp0:11# 处理完前面的阶段后,最后一个阶段不通过时的最大分数12dp0 = 013
14# dp1:15# 处理完前面的阶段后,最后一个阶段通过时的最大分数16# 一开始没有阶段,不可能处于“最后一个阶段通过”的状态17dp1 = -10**3018
19for score in scores:20 # 当前阶段不通过:21 # 上一个阶段无论通过还是不通过,都不会产生新的分数22 new_dp0 = max(dp0, dp1)23
24 # 当前阶段通过:25 # 1. 上一个阶段不通过:增加 score26 # 2. 上一个阶段通过:增加 score + C27 new_dp1 = max(28 dp0 + score,29 dp1 + score + C30 )31
32 # 进入下一阶段33 dp0 = new_dp034 dp1 = new_dp135
36# 最后一个阶段可以通过,也可以不通过37print(max(dp0, dp1))不重复加减,只维护变化的部分
差分数组不记录“当前位置有多少”,而记录“从这里开始增加或减少多少”。
1位置: 1 2 3 4 52数值: 0 0 0 0 0现在给区间 [2, 4] 每个位置加 1,结果应该是:
1位置: 1 2 3 4 52数值: 0 1 1 1 0如果暴力修改,需要:
1a[2] += 12a[3] += 13a[4] += 1差分的想法是:
1从位置 2 开始,后面都增加 12从位置 5 开始,取消这次增加所以只记录:
1d[2] += 12d[5] -= 1此时差分数组是:
1位置: 1 2 3 4 52差分: 0 1 0 0 -1注意:差分数组本身还不是最终答案。
再前缀和后就得到答案:
从左到右累加差分
1位置 1:02位置 2:0 + 1 = 13位置 3:1 + 0 = 14位置 4:1 + 0 = 15位置 5:1 + (-1) = 0这正好是我们想要的结果。
因此:
1d[l] += 12d[r + 1] -= 1含义是:
d[l] += 1:从 l 开始,覆盖次数增加;d[r + 1] -= 1:从 r + 1 开始,覆盖次数取消。

前缀和
1s = [0] * len(x)2now = 03
4for i in range(len(x)):5 #表示把当前位置的“变化量”累加到当前覆盖次数6 now += d[i]7 #表示保存当前位置最终的覆盖次数8 s[i] = now
https://gist.github.com/xue120754/dee866808065682018b29fa3b045a4e3
差分数组不记录“当前位置有多少”,而记录“从这里开始增加或减少多少”。
区间、集合、字典、离散化、差分数组、前缀和
这段代码里的离散化,目的是:
原坐标可能很大,不能直接用坐标当数组下标;于是把真正出现的坐标压缩成连续的小下标。

1import sys2
3input = sys.stdin.readline4
5n, p = map(int, input().split())6
7# 保存所有区间8a = []9
10# 保存所有需要离散化的坐标11x = set()12
13for _ in range(n):14 l, r = map(int, input().split())15
16 a.append((l, r))17
18 x.add(l)19 x.add(r)20 x.add(r + 1)21
22# 排序、去重23x = sorted(x)24
25# 建立:原坐标 -> 离散下标26mp = {}27
28for i in range(len(x)):29 mp[x[i]] = i30
31# 差分数组32d = [0] * (len(x) + 1)33
34# 处理每个区间 [l, r]35for l, r in a:36 d[mp[l]] += 137 d[mp[r + 1]] -= 138
39# 求前缀和,得到每个坐标的覆盖次数40s = [0] * len(x)41now = 042
43for i in range(len(x)):44 now += d[i]45 s[i] = now46
47# 统计答案48ans = 049
50for l, r in a:51 v1 = s[mp[l]]52 v2 = s[mp[r]]53
54 if abs(v1 - v2) >= p:55 ans += 156
57print(ans)1import sys2
3input = sys.stdin.readline4
5# 读取区间数量 n,以及判断条件 p6n, p = map(int, input().split())7
8# 保存所有区间9lr = []10
11# 差分字典12d = {}13
14for _ in range(n):15 l, r = map(int, input().split())16 lr.append((l, r))17
18 # 保证这些坐标之后可以被查询19 #如果键不存在,就添加这个键并设置默认值;如果键已经存在,就保持原值不变。20 d.setdefault(l, 0)21 d.setdefault(r, 0)22 d.setdefault(r + 1, 0)23# e.g d.setdefault(5, 0)24# {5: 0}25# d[5] = 026 # 区间 [l, r] 覆盖次数加 127 d[l] += 128
29 # 从 r + 1 开始取消覆盖30 d[r + 1] -= 131
32# 按坐标从小到大进行前缀累加33now = 034#dx是d前缀和后的结果35dx = {}36
37for x in sorted(d):38 now += d[x]39 dx[x] = now40
41# 统计答案42ans = 043
44for l, r in lr:45 # 查询 l 和 r 位置的覆盖次数46 if abs(dx[l] - dx[r]) >= p:47 ans += 148
49print(ans)复盘版
1import sys2input=lambda:sys.stdin.readline().strip()3
4n,p=map(int,input().split())5
6lr=[]7
8d={}9for _ in range(n):10
11 l,r=map(int,input().split())12 lr.append((l,r))13
14 d.setdefault(l,0)15 d.setdefault(r,0)16 d.setdefault(r+1,0)17
18 d[l]+=119 d[r+1]-=120
21now=022#对dx进行d的前缀和操作23dx={}24#25#对字典直接使用 `sorted`,排序的是**字典的键**.26# 把字典中所有坐标从小到大取出来,27# 每次取一个坐标放到变量 `x` 中。28for x in sorted(d):29 now+=d[x]30 #不可以写dx[x]+=now y因为最开始dx是空字典31 dx[x]=now32cnt=033#应该从 `lr` 中取出每一个区间:34#for i in range(n):35for l,r in lr:36 if(abs(dx[r]-dx[l])>=p):37 cnt+=138print(cnt)
1import sys2input=lambda:sys.stdin.readline().strip()3
4n=int(input())5l1=[]6r1=[]7
8for _ in range(n):9 l2,r2=map(int,input().split())10 l1.append(l2)11 r1.append(r2)12
13k=max(r1)14d=[0]*(k+1)15for i in range(n):16 d[l1[i]]+=117 d[r1[i]]-=118
19st=[0]*k20now=021for i in range(k):22 now+=d[i]23 st[i]=now24
25
26ans1=027ans2=028cnt1=029cnt2=030
31l=min(l1)32
33for i in range(min(l1),max(r1)):34 if(st[i]>=1):35 cnt2=036 cnt1+=137 ans1=max(cnt1,ans1)38 else:39 cnt1=040 cnt2+=141 ans2=max(cnt2,ans2)42print(ans1,ans2)

1import sys2
3input = sys.stdin.readline4
5t = int(input())6
7for _ in range(t):8 n = int(input())9 a = [0] + list(map(int, input().split()))10
11 d = [0] * (n + 1)12
13 for i in range(2, n + 1):14 d[i] = a[i] - a[i - 1]15
16 # suf[i] 表示 d[i] 到 d[n] 是否全部 >= 017 suf = [True] * (n + 2)18
19 for i in range(n, 1, -1):20 suf[i] = suf[i + 1] and d[i] >= 021
22 ans = 023 left_ok = True24 #不要每次重新计算全部内容,25 #而是记录之前的结果,只更新刚刚变化的部分26 for k in range(1, n + 1):27 # 维护 d[2] 到 d[k] 是否全部 <= 028 # 如果k=1没有前缀就只需要判断后缀29 if k >= 2:30 left_ok = left_ok and d[k] <= 031
32 # 前缀反转后是非递减的33 if not left_ok:34 continue35
36 # 后缀 a[k+1], ..., a[n] 非递减37 if k < n and not suf[k + 2]:38 continue39
40 # 反转后的前缀与后缀可以连接41 if k < n and a[1] > a[k + 1]:42 continue43
44 ans += 145
46 print(ans)
1import sys2
3# 使用 readline 读取输入,速度更快4input = sys.stdin.readline5
6# 读取菜品数量 n 和午餐盒最大容量 w7n, w = map(int, input().split())8
9# delicious[i] 表示第 i 道菜的美味度10delicious = []11
12# volume[i] 表示第 i 道菜的体积13volume = []14
15# 读取 n 道菜的信息16for _ in range(n):17 a, b = map(int, input().split())18
19 # a 是美味度20 delicious.append(a)21
22 # b 是体积23 volume.append(b)24
25# answer 表示目前找到的最大美味度26answer = 027
28# 一共有 2^n 种选择方案29#30# mask 可以理解为一个二进制数:31# mask 的第 i 位为 1,表示选择第 i 道菜;32# mask 的第 i 位为 0,表示不选择第 i 道菜。33#34# 例如 n = 3 时:35#36# mask = 0 -> 000 -> 一道菜都不选37# mask = 1 -> 001 -> 选择第 0 道菜38# mask = 2 -> 010 -> 选择第 1 道菜39# mask = 3 -> 011 -> 选择第 0、1 道菜40# mask = 4 -> 100 -> 选择第 2 道菜41#42for mask in range(1 << n):43
44 # 当前选择方案的总美味度45 total_delicious = 046
47 # 当前选择方案的总体积48 total_volume = 049
50 # 检查每一道菜是否被选择51 for i in range(n):52
53 # 1 << i 表示只有第 i 位是 1 的二进制数54 #55 # 例如:56 # i = 0 时,1 << i = 00157 # i = 1 时,1 << i = 01058 # i = 2 时,1 << i = 10059 #60 # mask & (1 << i) 不等于 0,61 # 说明 mask 的第 i 位是 1,62 # 也就是选择了第 i 道菜。63 #如果 `mask` 的第 `i` 位是 `1`,说明第 `i` 道菜被选择了。64 if mask & (1 << i):65
66 # 加上第 i 道菜的美味度67 total_delicious += delicious[i]68
69 # 加上第 i 道菜的体积70 total_volume += volume[i]71
72 # 如果总体积没有超过午餐盒容量73 if total_volume <= w:74
75 # 更新最大美味度76 answer = max(answer, total_delicious)77
78# 输出所有合法选择方案中的最大美味度79print(answer)1<<i:

&
&是按位与运算:两个比特都为 1,结果才是 1;否则为 0。
https://gist.github.com/xue120754/15855f0bc75928820651af2395b68eec
global answer 的意思是:
告诉 Python:函数里的 answer 使用函数外面定义的那个变量。
1import sys2input = lambda:sys.stdin.readline().strip()3
4n,w=map(int,input().split())5
6a=[]7b=[]8
9for _ in range(n):10 a1,b1=map(int,input().split())11 a.append(a1)12 b.append(b1)13
14ans=015
16def dfs(i,total_a,total_b):17 global ans18
19 if(total_b>w):20 return21 if(i==n):22 ans=max(ans,total_a)23 return24
25 dfs(i+1,total_a,total_b)26
27 dfs(i+1,total_a+a[i],total_b+b[i])28
29dfs(0,0,0)30
31print(ans)sum[i]=sum[i-1]+a[i];
a[l]~a[r]=sum[r]-sum[l-1]
前缀和+哈希:
1mp = {}2
3for i in range(1, n + 1):4 s[i] = s[i - 1] + a[i]5 #这个和s[i]对应的位置i6 mp[s[i]] = i1mp[某个前缀和] = 这个前缀和对应的下标

1import sys2
3
4def solve():5 input = sys.stdin.buffer.readline6
7 n = int(input())8 a = [0] + list(map(int, input().split()))9
10 # s[i] 表示前 i 个元素的前缀和11 s = [0] * (n + 1)12
13 # mp[前缀和] = 对应的下标14 mp = {}15
16 # 计算前缀和,并记录前缀和对应的位置17 for i in range(1, n + 1):18 s[i] = s[i - 1] + a[i]19 mp[s[i]] = i20 #记录个数21 ans = 022
23 # 枚举左端点 l24 for l in range(1, n + 1):25
26 # 枚举右端点元素 a[r] 的可能值27 # 由于 1 <= a[i] <= 30,所以只需要枚举 1~3028 for ar in range(1, 31):29
30 # 由:31 # a[l] * a[r] = s[r - 1] - s[l]32 #33 # 得到:34 # s[r - 1] = a[l] * a[r] + s[l]35 target = ar * a[l] + s[l]36
37 # 如果不存在这样的前缀和,跳过38 if target not in mp:39 continue40
41 # mp[target] 对应的是 r - 142 r = mp[target] + 143
44 # 右端点不能越界45 if r > n:46 continue47
48 # 确保右端点元素值就是当前枚举的 ar49 if a[r] != ar:50 continue51
52 # 区间长度必须至少为 353 if r - l + 1 < 3:54 continue55
56 # 找到一个合法区间57 ans += 158
59 print(ans)60
61
62if __name__ == "__main__":63 solve()1两个对应位置都是 1,结果才是 1
下面用 Python 讲解图片中的三种基础位运算:&、|、^
常见用途:判断奇偶
一个数的二进制最低位:
01所以可以这样判断
1x=72
3if(x&1):4 print("奇数")5else:6 print("偶数")7 = 111
111 & 001 = 001
|#1两个对应位置只要有一个是 1,结果就是 1^#1两个对应位置不同,结果是 12两个对应位置相同,结果是 0Python
1print(5 ^ 5) # 0二进制:
Plain text
11012^1013---4000也就是:
Plain text
1a ^ a = 0Python
1print(5 ^ 0) # 5即:
Plain text
1a ^ 0 = aPython
1print(1 ^ 2 ^ 3)2print(3 ^ 1 ^ 2)两个结果相同。
即:
Plain text
1a ^ b ^ c = c ^ a ^ bPython 本身可以直接交换:
Python
1a, b = b, a也可以利用异或:
Python
1a = 52b = 33
4a = a ^ b5b = a ^ b6a = a ^ b7
8print(a) # 39print(b) # 5过程如下:
Plain text
1a = 5 ^ 32b = (5 ^ 3) ^ 3 = 53a = (5 ^ 3) ^ 5 = 3不过在 Python 中,推荐使用:
Python
1a, b = b, a异或交换主要是帮助理解异或性质。
假设数组中除了一个数只出现一次,其他数都出现两次:
Python
1nums = [4, 1, 2, 1, 2, 4, 7]答案是 7。
利用:
Plain text
1a ^ a = 02a ^ 0 = a代码:
Python
1nums = [4, 1, 2, 1, 2, 4, 7]2
3answer = 04
5for x in nums:6 answer ^= x7
8print(answer) # 7展开为:
Plain text
10 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2 ^ 4 ^ 7相同的数会抵消:
Plain text
14 ^ 4 = 021 ^ 1 = 032 ^ 2 = 0最后只剩:
Plain text
17M-小苯的异或疑惑(hard)_北京信息科技大学第十五届程序设计竞赛(同步赛)

1import sys2input = lambda:sys.stdin.readline().strip()3
4n=int(input())5a=list(map(int,input().split()))6f=a[0]7if(n%2!=0):8 print(0)9else:10 for i in range(1,n):11 f^=a[i]12 print(f)优化思路:统计每个数出现了几次
考虑某个 a[k]:
n - 1 个元素进行异或a[k] 一共出现 n - 1 次而异或有性质:
Plain text
1x ^ x = 0所以:
n - 1 是偶数,a[k] 出现偶数次,会全部抵消n - 1 是奇数,a[k] 会保留一次因此:
当 n 为奇数
Plain text
1n - 1 为偶数所有元素都抵消,答案是:
Plain text
10当 n 为偶数
Plain text
1n - 1 为奇数每个元素保留一次,答案是:
Plain text
1a[0] ^ a[1] ^ ... ^ a[n-1]例如:
Python
1print(5 ^ 3 ^ 6)二进制:
Plain text
15 = 10123 = 01136 = 110逐位统计:
Plain text
1第 1 位:1、0、1,有两个 1,结果为 02第 2 位:0、1、1,有两个 1,结果为 03第 3 位:1、1、0,有两个 1,结果为 0所以:
Plain text
15 ^ 3 ^ 6 = 0异或某一位上出现奇数个 1,结果该位就是 1;出现偶数个 1,结果就是 0。
Python
1a = 5 # 1012b = 3 # 0113
4print(a & b) # 1,两个位置都为 15print(a | b) # 7,只要一个位置为 16print(a ^ b) # 6,两个位置不同对应关系:
| 运算 | 规则 | 示例 |
|---|---|---|
& | 都是 1 才是 1 | 5 & 3 = 1 |
| ` | ` | 有一个 1 就是 1 |
^ | 不同为 1,相同为 0 | 5 ^ 3 = 6 |
位运算:
Python
1& | ^逻辑运算:
Python
1and or not例如:
Python
1a = True2b = False3
4print(a and b) # False而位运算是对整数的二进制位进行操作:
Python
1print(5 & 3) # 1不要混淆:
Python
1if x > 0 and y > 0:2 print("都大于 0")这里应该使用逻辑运算 and,不是 &。
Plain text
1&:都为 1 才为 12|:有 1 就为 13^:不同为 1,相同为 0最重要的异或性质:
Python
1a ^ a == 02a ^ 0 == a这也是“找只出现一次的数”这类题目的基础。
I-快速夺取_苏州工学院 2026 ACM新生程序设计竞赛同步赛(重现赛)@AuroraSean

BFS 的全称是:
Breadth First Search,广度优先搜索
它的思想是:
先走距离为 1 的所有位置,再走距离为 2 的所有位置,再走距离为 3 的所有位置……
就像水波纹一样,一层一层向外扩散。
例如地图:
Plain text
1起点 . . .2 . # .3 . . 终点从起点开始:
Plain text
1第 0 层:起点2第 1 层:起点周围能走的位置3第 2 层:再向外扩展一层4第 3 层:继续扩展只要最终扩展到了终点,就说明可以到达。
BFS 通常需要三个东西:
Python
1queue # 队列,保存待处理的位置2visited # 记录某个位置是否访问过3directions # 上下左右四个方向队列有一个特点:
先进先出。
就像排队买饭:
Plain text
1先来的人先离开Python 中使用:
Python
1from collections import deque2
3queue = deque()加入元素:
Python
1queue.append((x, y))取出最前面的元素:
Python
1x, y = queue.popleft()不能使用:
Python
1list.pop(0)因为列表头部删除元素很慢,BFS 应该使用 deque。
为什么需要 visited?
因为地图中可能有环。
例如:
Plain text
1A -> B -> C2 ↑ ↓3 └────┘如果不记录访问过的位置,就可能一直绕圈。
Python
1visited = [[False] * n for _ in range(2)]当访问一个位置时:
Python
1visited[x][y] = True从一个格子可以向:
因此可以写:
Python
1因为二维数组的行号是**从上到下增加**的。2directions = [3 (-1, 0), # 上4 (1, 0), # 下5 (0, -1), # 左6 (0, 1) # 右7]8 行号变小9 ↑10 |11列号变小 ←──── (x, y) ────→ 列号变大12 |13 ↓14 行号变大如果当前位置是:
Python
1(x, y)那么下一个位置是:
Python
1nx = x + dx2ny = y + dy下面是一个最基础的 BFS:
Python
1from collections import deque2
3def bfs(start_x, start_y, target_x, target_y, grid):4 rows = len(grid)5 cols = len(grid[0])6
7 # visited[x][y] 表示位置 (x, y) 是否访问过8 visited = [[False] * cols for _ in range(rows)]9
10 # 创建队列,并把起点加入队列11 queue = deque()12 queue.append((start_x, start_y))13 #表示起点访问过14 visited[start_x][start_y] = True15
16 # 上、下、左、右17 directions = [18 (-1, 0),19 (1, 0),20 (0, -1),21 (0, 1)22 ]23
24 while queue:25 # 取出队头位置26 x, y = queue.popleft()27
28 # 如果到达终点,说明可以到达29 if x == target_x and y == target_y:30 return True31
32 # 尝试向四个方向走33 for dx, dy in directions:34 nx = x + dx35 ny = y + dy36
37 # 判断是否越界38 if nx < 0 or nx >= rows:39 continue40
41 if ny < 0 or ny >= cols:42 continue43
44 # 判断是否是机器人45 if grid[nx][ny] == 1:46 continue47
48 # 判断是否已经访问过49 if visited[nx][ny]:50 continue51
52 # 可以走到这个位置53 visited[nx][ny] = True54 queue.append((nx, ny))55
56 # 队列为空,仍然没有找到终点57 return False重点看这部分:
Python
1while queue:2 x, y = queue.popleft()只要队列不为空,就不断取出一个位置。
然后:
Python
1for dx, dy in directions:尝试从当前位置走向四个方向。
如果新位置合法:
Python
1visited[nx][ny] = True2queue.append((nx, ny))就把它标记为已访问,并放入队列等待处理。
本题有两个重要位置:
Plain text
1起点:(1, 1)2铂金条:(r1, c1)3收集箱:(r2, c2)需要完成:
Plain text
1起点 -> 铂金条 -> 收集箱所以可以分成两次 BFS:
如果两次都可以到达,输出:
Plain text
1YES否则输出:
Plain text
1NO为什么可以分成两次?
因为机器人不能移动,地图不会发生变化。
如果:
Plain text
1起点可以到达铂金条2铂金条可以到达收集箱那么我们就可以先走到铂金条,再继续走到收集箱。
Python
1import sys2from collections import deque3
4
5def bfs(grid, start, target):6 """7 判断从 start 是否可以走到 target。8
9 参数:10 grid : 地图,0 表示可以走,1 表示机器人11 start : 起点坐标 (行, 列)12 target : 终点坐标 (行, 列)13
14 返回:15 True : 可以到达16 False : 无法到达17 """18
19 rows = 220 cols = len(grid[0])21
22 start_x, start_y = start23 target_x, target_y = target24
25 # visited[x][y] 表示位置 (x, y) 是否访问过26 visited = [[False] * cols for _ in range(rows)]27
28 # 使用队列保存待搜索的位置29 queue = deque()30
31 # 从 start 开始搜索32 queue.append((start_x, start_y))33 visited[start_x][start_y] = True34
35 # 上、下、左、右36 directions = [37 (-1, 0), # 上38 (1, 0), # 下39 (0, -1), # 左40 (0, 1) # 右41 ]42
43 while queue:44 # 取出队头位置45 x, y = queue.popleft()46
47 # 到达目标48 if x == target_x and y == target_y:49 return True50
51 # 尝试四个方向52 for dx, dy in directions:53 nx = x + dx54 ny = y + dy55
56 # 不能越界57 if nx < 0 or nx >= rows:58 continue59
60 if ny < 0 or ny >= cols:61 continue62
63 # 不能走到机器人所在的位置64 if grid[nx][ny] == 1:65 continue66
67 # 已经访问过的位置不再访问68 if visited[nx][ny]:69 continue70
71 # 标记并加入队列72 visited[nx][ny] = True73 queue.append((nx, ny))74
75 # 搜索结束仍未找到目标76 return False77
78
79# 读取所有输入80data = list(map(int, sys.stdin.buffer.read().split()))81
82# 读取列数83n = data[0]84
85# 读取两个目标的位置86r1, c1, r2, c2 = data[1:5]87
88# 转成 Python 的 0-based 下标89r1 -= 190c1 -= 191r2 -= 192c2 -= 193
94# 读取地图95grid = [96 data[5:5 + n],97 data[5 + n:5 + 2 * n]98]99
100# 起点是 (1, 1),转换成 0-based 后是 (0, 0)101start = (0, 0)102
103# 铂金条位置104gold = (r1, c1)105
106# 收集箱位置107box = (r2, c2)108
109# 第一步:起点能否到达铂金条110can_reach_gold = bfs(grid, start, gold)111
112# 第二步:铂金条能否到达收集箱113can_reach_box = bfs(grid, gold, box)114
115if can_reach_gold and can_reach_box:116 print("YES")117else:118 print("NO")假设:
Plain text
1n = 52铂金条 = (1, 3)3收集箱 = (2, 5)地图:
Plain text
10 0 0 1 020 1 0 0 0起点:
Plain text
1(1, 1)第一次 BFS:
Plain text
1(1,1) -> (1,2) -> (1,3)可以拿到铂金条。
第二次 BFS:
Plain text
1(1,3) -> (2,3) -> (2,4) -> (2,5)可以到达收集箱。
因此输出:
Plain text
1YES代码中:
Python
1queue.append((start_x, start_y))2visited[start_x][start_y] = True必须立刻标记。
如果不立刻标记,可能出现:
Plain text
1起点 -> 右边 -> 起点然后起点又被重复加入队列。
正确做法是:
一个位置第一次加入队列时,就标记为访问过。
而不是等它从队列取出来时再标记。
以后遇到网格搜索题,可以按这五步想:
本题中一个位置是:
Python
1(row, col)也就是:
Python
1(行号, 列号)本题可以上下左右移动:
Python
1directions = [2 (-1, 0),3 (1, 0),4 (0, -1),5 (0, 1)6]有三种:
使用:
Python
1visited当前位置等于目标位置:
Python
1if (x, y) == target:2 return True| 方法 | 搜索方式 | 常用数据结构 |
|---|---|---|
| BFS | 一层一层搜索 | 队列 |
| DFS | 一条路走到底 | 栈或递归 |
如果题目问:
最少走多少步?
在每一步代价相同的情况下,优先使用 BFS,因为 BFS 第一次到达终点时,一定是最短路。
本题只问:
能不能到达?
BFS 和 DFS 都可以,但 BFS 更适合练习网格搜索。
1m, n = len(maze), len(maze[0])2vis = [[False] * n for _ in range(m)]3dirc = [(1, 0), (-1, 0), (0, 1), (0, -1)]4
5def InArea(x, y):6 return 0 <= x < m and 0 <= y < n7
8def dfs(x, y):9 if not InArea(x, y) or vis[x][y] == True:10 return11 vis[x][y] = True12 for dx, dy in dirc:13 dfs(x + dx, y + dy)14 return1class Solution:2 def numIslands(self, grid: List[List[str]]) -> int:3 n=len(grid)4 m=len(grid[0])5 ans=06 vis=[[False]*m for _ in range(n)]#先列后行7 dirc =[(1,0),(-1,0),(0,1),(0,-1)]8 def inarea(x,y):9 return 0<=x<n and 0<=y<m10 # 深度优先搜索,标记同一个岛屿11 def dfs(x,y):12 # 越界、访问过、或者是水,直接返回13 if not inarea(x,y) or vis[x][y]==True or grid[x][y]=="0":# “0” 要加""号14 return15 # 标记当前位置16 vis[x][y]=True17 # 搜索上下左右18 for dx,dy in dirc:19 dfs(x+dx,y+dy)20 return21
22 for i in range(n):23 for j in range(m):24 # 找到一个未访问的陆地,说明发现了一个新岛屿25 if(grid[i][j]=="1" and vis[i][j]==False):26 ans+=127 dfs(i,j)28 return ans每次进入一个新的陆地格子后,又会执行:
1for dx, dy in dirc:2 dfs(新的坐标)所以它不是只检查起点附近,而是:
1当前格子2 -> 邻居格子3 -> 邻居的邻居4 -> 更外层的格子这就是递归不断向外扩展的过程。
当它尝试走到水、越界或已经访问过的位置时,触发:
1if not inarea(x, y) or vis[x][y] or grid[x][y] == "0":2 return此时这一次递归调用结束,返回上一个格子,继续检查上一个格子的其他方向。
例如遇到水:
11 1 120 0 1从 (0, 0) 可以走到 (0, 1),再到 (0, 2),再到 (1, 2)。尝试走到 (1, 1) 时发现是水:
1grid[1][1] == "0"于是:
1return但这只代表当前这条方向停止,不是整个 DFS 停止。程序会回到上一级,继续尝试其他方向。
可以把它理解为走迷宫:
dfs:沿着一条路继续走所以 return 只结束当前递归调用,不会立即结束所有搜索。
所以一次 dfs 实际上会标记:
从起点出发,所有能够通过上下左右走到的陆地。
而题目中规定:
上下左右相连的一整块陆地称为一个岛屿。
因此,一次 dfs 标记的所有陆地,恰好就是一整座岛屿。
外层循环负责寻找新的岛屿:
1for i in range(n):2 for j in range(m):3 if grid[i][j] == "1" and not vis[i][j]:4 ans += 15 dfs(i, j)I-快速夺取_苏州工学院 2026 ACM新生程序设计竞赛同步赛(重现赛)@AuroraSean
当然可以。DFS 和 BFS 都是“搜索地图”,区别是:
这道题只问“能不能到达”,所以 DFS 可以解决。
假设现在在位置 (x, y):
True;True。核心代码:
Python
1def dfs(x, y):2 if 到达终点:3 return True4
5 标记当前位置已经访问6
7 for 四个方向:8 if 这个方向可以走:9 if dfs(下一个位置):10 return True11
12 return Falsevisited?#地图中可能有环:
Plain text
1A -> B2↑ ↓3D <- C如果不记录访问过的位置,就可能:
Plain text
1A -> B -> C -> D -> A -> B -> ...无限循环。
所以当前位置第一次进入 DFS 时,就要立刻标记:
Python
1visited[x][y] = True注意:判断能不能到达时,不需要取消标记。
Python
1def dfs(x, y):2 # 如果到达目标,搜索成功3 if (x, y) == target:4 return True5
6 # 标记当前位置已经访问过7 visited[x][y] = True8
9 # 尝试上、下、左、右四个方向10 for dx, dy in directions:11 nx = x + dx12 ny = y + dy13
14 # 越界,跳过15 if nx < 0 or nx >= 2 or ny < 0 or ny >= n:16 continue17
18 # 有机器人,跳过19 if grid[nx][ny] == 1:20 continue21
22 # 已经访问过,跳过23 if visited[nx][ny]:24 continue25
26 # 递归搜索下一个位置27 if dfs(nx, ny):28 return True29
30 # 四个方向都走不到目标31 return False这里最重要的是这一句:
Python
1if dfs(nx, ny):2 return True意思是:
如果从下一个位置出发能够到达终点,那么当前搜索也成功。
Python
1import sys2
3
4def can_reach(grid, start, target):5 """6 判断从 start 是否可以走到 target。7
8 grid 中:9 0 表示可以走10 1 表示有机器人,不能走11 """12
13 rows = 214 cols = len(grid[0])15
16 # visited[x][y] 表示位置 (x, y) 是否访问过17 visited = [[False] * cols for _ in range(rows)]18
19 # 上、下、左、右20 directions = [21 (-1, 0), # 上22 (1, 0), # 下23 (0, -1), # 左24 (0, 1) # 右25 ]26
27 def dfs(x, y):28 # 到达目标29 if (x, y) == target:30 return True31
32 # 标记当前位置,防止重复搜索33 visited[x][y] = True34
35 # 尝试四个方向36 for dx, dy in directions:37 nx = x + dx38 ny = y + dy39
40 # 不能越界41 if nx < 0 or nx >= rows:42 continue43
44 if ny < 0 or ny >= cols:45 continue46
47 # 不能走到机器人位置48 if grid[nx][ny] == 1:49 continue50
51 # 已经访问过的位置不再搜索52 if visited[nx][ny]:53 continue54
55 # 如果从下一个位置能到达目标,搜索成功56 if dfs(nx, ny):57 return True58
59 # 四个方向都无法到达目标60 return False61
62 # 从 start 开始搜索63 return dfs(start[0], start[1])64
65
66# 读取所有输入67data = list(map(int, sys.stdin.buffer.read().split()))68
69# 读取列数70n = data[0]71
72# 读取铂金条和收集箱的位置73r1, c1, r2, c2 = data[1:5]74
75# 题目坐标从 1 开始,Python 下标从 0 开始76r1 -= 177c1 -= 178r2 -= 179c2 -= 180
81# 读取两行地图82grid = [83 data[5:5 + n],84 data[5 + n:5 + 2 * n]85]86
87# 起点 (1, 1) 转换成 Python 下标后是 (0, 0)88start = (0, 0)89
90# 铂金条位置91gold = (r1, c1)92
93# 收集箱位置94box = (r2, c2)95
96# 第一步:起点能否到达铂金条97if not can_reach(grid, start, gold):98 print("NO")99else:100 # 第二步:拿到铂金条后,能否到达收集箱101 if can_reach(grid, gold, box):102 print("YES")103 else:104 print("NO")假设当前地图是:
Plain text
10 0 121 0 0从左上角开始:
Plain text
1(0, 0)DFS 可能这样搜索:
Plain text
1dfs(0, 0)2 尝试上:越界3 尝试下:机器人4 尝试左:越界5 尝试右:进入 (0, 1)6
7 dfs(0, 1)8 尝试下:进入 (1, 1)9
10 dfs(1, 1)11 尝试右:进入 (1, 2)12
13 dfs(1, 2)14 到达目标15 返回 True返回过程:
Plain text
1dfs(1, 2) 返回 True2dfs(1, 1) 返回 True3dfs(0, 1) 返回 True4dfs(0, 0) 返回 True所以最终判断可以到达。
例如:
Plain text
10 0 121 0 130 1 0如果某个方向走不通,递归函数会执行:
Python
1return False然后回到上一个位置,继续尝试其他方向。
这就叫:
回溯。
但要注意:
Python
1visited[nx][ny] = False在本题中不需要写。
因为我们只是判断“是否存在一条路”。一个位置如果已经搜索过,并且从它出发到不了目标,那么之后再次来到它,也不会有新的结果。
Python
1queue.append(start)2
3while queue:4 x, y = queue.popleft()5 ...使用队列,一层一层搜索。
Python
1def dfs(x, y):2 ...3 dfs(nx, ny)使用递归,一条路走到底。
| 对比 | BFS | DFS |
|---|---|---|
| 主要结构 | 队列 | 递归/栈 |
| 搜索特点 | 一层一层 | 一条路走到底 |
| 能否判断可达 | 可以 | 可以 |
| 是否保证最短路 | 可以 | 不保证 |
| 本题能否使用 | 可以 | 可以 |
题目只要求输出:
Plain text
1YES 或 NO也就是只关心:
是否存在一条合法路径。
DFS 会尝试所有可能路线:
True;False。因此完全符合题目要求。
时间复杂度为:
Plain text
1O(行数 × 列数) = O(2n) = O(n)因为每个位置最多访问一次。
暂未播放
全站壁纸和首页壁纸可分别设置,默认亮暗主题壁纸保持不变;图片仅保存在本机浏览器。
保存后首页立即生效,仅保存在本机浏览器。
评论 0
还没有评论,来说第一句吧。