💻技术

LeetCode Hot 100 精练🥸(1) 记忆中的东西一定会消退，真正留下的才是学到的，一定要及时回顾。 题目表 (序号) 标题 (1) 160. 相交链表 (2) 236. 二叉树的最近公共祖先 (3) 234. 回文链表 (4) 739. 每日温度 (5) 226. 翻转二叉树 (6) 221. 最大正方形 (7) 215. 数组中的第K个最大元素 (8) 208. 实现 Trie (前缀树) (9) 207. 课程表 (10) 206. 反转链表 (11) 200. 岛屿数量 (12) 198. 打家劫舍 (13) 169. 多数元素 (14) 238. 除自身以外数组的乘积 (15) 155. 最小栈 (16) 152. 乘积最大子数组 (17) 148. 排序链表 (18) 146. LRU 缓存 (19) 142. 环形链表 II (20) 141. 环形链表 (21) 139. 单词拆分 (22) 136. 只出现一次的数字 (23) 647. 回文子串 (24) 128. 最长连续序列 (25) 124. 二叉树中的最大路径和 (26) 322. 零钱兑换 (27) 494. 目标和 (28) 461. 汉明距离 (29) 448. 找到所有数组中消失的数字 (30) 438. 找到字符串中所有字母异位词 (31) 437. 路径总和 III (32) 416. 分割等和子集 (33) 406. 根据身高重建队列 (34) 399. 除法求值 (35) 394. 字符串解码 (36) 347. 前 K 个高频元素 (37) 338. 比特位计数 (38) 337. 打家劫舍 III (39) 121. 买卖股票的最佳时机 (40) 312. 戳气球 (41) 309. 买卖股票的最佳时机含冷冻期 (42) 301. 删除无效的括号 (43) 300. 最长递增子序列 (44) 297. 二叉树的序列化与反序列化 (45) 287. 寻找重复数 (46) 283. 移动零 (47) 279. 完全平方数 (48) 253. 会议室 II (49) 240. 搜索二维矩阵 II (50) 239. 滑动窗口最大值 (51) 22. 括号生成 (52) 49. 字母异位词分组 (53) 48. 旋转图像 (54) 46. 全排列 (55) 42. 接雨水 (56) 39. 组合总和 (57) 543. 二叉树的直径 (58) 34. 在排序数组中查找元素的第一个和最后一个位置 (59) 33. 搜索旋转排序数组 (60) 32. 最长有效括号 (61) 31. 下一个排列 (62) 538. 把二叉搜索树转换为累加树 (63) 23. 合并 K 个升序链表 (64) 560. 和为 K 的子数组 (65) 21. 合并两个有序链表 (66) 20. 有效的括号 (67) 19. 删除链表的倒数第 N 个结点 (68) 17. 电话号码的字母组合 (69) 15. 三数之和 (70) 11. 盛最多水的容器 (71) 10. 正则表达式匹配 (72) 5. 最长回文子串 (73) 4. 寻找两个正序数组的中位数 (74) 3. 无重复字符的最长子串 (75) 2. 两数相加 (76) 79. 单词搜索 (77) 114. 二叉树展开为链表 (78) 621. 任务调度器 (79) 617. 合并二叉树 (80) 105. 从前序与中序遍历序列构造二叉树 (81) 104. 二叉树的最大深度 (82) 102. 二叉树的层序遍历 (83) 101. 对称二叉树 (84) 98. 验证二叉搜索树 (85) 96. 不同的二叉搜索树 (86) 94. 二叉树的中序遍历 (87) 85. 最大矩形 (88) 84. 柱状图中最大的矩形 (89) 1. 两数之和 (90) 78. 子集 (91) 76. 最小覆盖子串 (92) 75. 颜色分类 (93) 72. 编辑距离 (94) 70. 爬楼梯 (95) 581. 最短无序连续子数组 (96) 64. 最小路径和 (97) 62. 不同路径 (98) 56. 合并区间 (99) 55. 跳跃游戏 (100) 53. 最大子数组和 (1)160. 相交链表 题目大意： ...

Java20天速成——进阶课程(2) 正则表达式 符号 含义 举例 [] 匹配方括号内的任一字符 [abc] ^ 匹配除指定字符外的任意字符 [^abc] && 匹配两个字符集的交集，需作为整体出现 [a-z&&m-p] . 匹配除换行符外的任意字符 a.b （匹配 “a” 后接任意字符，再接 “b”） \ 转义字符，用于匹配特殊字符 \\d \\d 匹配数字 0-9 \\d+ \\D 匹配非数字字符 \\D+ \\s 匹配空白字符 \s匹配空格、制表符、换行符等等 \\S 匹配非空白字符 \\S+ （匹配非空白字符序列） \\w 匹配单词字符 [a-zA-Z_0-9] \\W 匹配非单词字符 [^\w] * 匹配前面的元素零次或多次，即可有可无 a*b （匹配 “b”、“ab”、“aab”、等等） ? 匹配前面的元素零次或一次，即可有可无 colou?r （匹配 “color” 或 “colour”） () 分组，将其中的字符视为一个单元 a(bc)+ \f 匹配换页符 \f | `|` | 或，用于匹配多个模式中的任意一个 | `ab\|AB` | public static void method1() { // 给定的字符串包含了电话号码和邮箱地址的信息 String data = " 来黑马程序员学习Java，\n" + " 电话：1866668888，18699997777\n" + " 或者联系邮箱：boniu@itcast.cn，\n" + " 座机电话：01036517895，010-98951256\n" + " 邮箱：bozai@itcast.cn，\n" + " 邮箱：dlei0009@163.com，\n" + " 热线电话：400-618-9090 ，400-618-4000，4006184000，4006189090"; // 定义正则表达式来匹配电话号码和邮箱地址 String regex = "(1[3-9]\\d{9})|" + "(0\\d{2,9}-?\\d{7,18})|" // 匹配固定电话号码，包括区号和分机号 + "(\\w{2,}@\\w{2,20}(\\.\\w{2,10}){1,2})|" // 匹配邮箱地址 + "(400-?\\d{3,7}-?\\d{3,7})"; // 匹配400电话号码，包括可能的分机号 // 编译正则表达式 Pattern pattern = Pattern.compile(regex); // 创建匹配器对象 Matcher matcher = pattern.matcher(data); // 循环查找匹配项并打印 while(matcher.find()){ String res = matcher.group(); // 获取匹配到的字符串 System.out.println(res); } } String s1 = "古力娜扎ai8888迪丽热巴999aa5566马尔扎哈fbbfsfs42425卡尔扎巴"; System.out.println(s1.replaceAll("\\w+", "-")); String s2 = "我我我喜欢编编编编编编编编编编编编程程程"; System.out.println(s2.replaceAll("(.)\\1+", "$1")); String s3 = "古力娜扎ai8888迪丽热巴999aa5566马尔扎哈fbbfsfs42425卡尔扎巴"; String[] names = s3.split("\\w+"); System.out.println(Arrays.toString(names)); 异常 Error： 代表的系统级别错误（属于严重问题）， 也就是说系统一旦出现问题，sun公司会把这些问题封装成Error对象给出了，即Error是Sun公司自己用的，而不是给程序员用的 ...

LeetCode第 393 场周赛 第三题3116. 单面值组合的第 K 小金额 题目大意： 给定一个整数数组coins表示不同面额的硬币，另给定一个整数k。你有无限量的每种面额的硬币，但是，你不能组合使用不同面额的硬币。要求返回使用这些硬币能制造的第kth小金额。 ...

进阶课程(1) OOP static 静态， 可以修饰成员变量，成员方法 成员变量按照有无static修饰，分为两种 类变量 ： 有static修饰，属于类，在计算机里只有一份，会被类的全部对象共享 实例变量（对象的变量）：无static修饰，属于每个对象 // 类变量推荐赋值方式 Student.name = "Java"; // 不推荐赋值方式 Student s1 = new Student(); s1.name = "True Java"; Student s2 = new Student(); s2.name = "False Java"; System.out.println(s2.name); //False Java System.out.println(Student.name); //False Java // 成员变量 s1.age = 25; s2.age = 15; System.out.println(s1.age); //25 System.out.println(s2.age); //15 //User类 public static int number; public User(){ number+=1; //类中访问自己的变量可以不写 User(). } //Test类 public static void main(String[] args) { User u1 = new User(); User u2 = new User(); User u3 = new User(); System.out.println(User.number); //3 } 类方法：有static修饰的成员方法，属于类。 实例方法：无static修饰的成员方法，属于对象 //Student double score; public static void printHelloWorld(){ System.out.println("Hello World"); System.out.println("Hello World"); } public void printPass(){ System.out.println("成绩：" + (score >= 60 ? "及格" : "不及格")); } //Test Student.printHelloWorld();//Hello World Hello World Student s = new Student(); s.score = 100; s.printPass(); //成绩：及格 类方法的常见应用案例 类方法最常见的应用场景是做工具类 工具类：工具类中的方法都是一些类方法，每个方法都是用来完成一个功能的，工具类是给开发人员共同使用的 ...

JAVA 20天速成 有志者事竟成 没有全身心的投入和检验，是学不到东西的。 自欺欺人和眼高手低毫无作用。 JAVA背景信息 JAVA是一门高级编程语言。 ...

Acwing算法学习 [TOC] 第一章 课上：学思想 课下：背代码 题目，一道题写好几遍 理解没有任何意义，体力活+脑力活 记忆力 毅力/自制力 沉下心背东西 快速排序算法模板 —— 模板题 AcWing 785. 快速排序 分治 ...

算法笔记（二）——数据结构(Python实现) 数据结构 单链表 N = int(1e5+10) e=[0]*N ne=[0]*N head=-1 idx=1 def insert(x): global idx, head e[idx]=x ne[idx]=head head=idx idx+=1 def add(k, x): global idx e[idx]=x ne[idx]=ne[k] ne[k]=idx idx+=1 def remove(k): global idx, head if k==0: head = ne[head] else: ne[k]=ne[ne[k]] n = int(input()) for _ in range(n): s = input().split() op=s[0] if op=='H': insert(int(s[1])) elif op=='I': add(int(s[1]), int(s[2])) else: remove(int(s[1])) i=head while i!=-1: print(e[i], end=' ') i=ne[i] 双链表 N = int(1e5+10) e=[0]*N l=[0]*N r=[0]*N idx=0 def init(): global idx r[2]=1 l[1]=2 idx=3 def insert(k, x): global idx e[idx]=x l[idx]=k r[idx]=r[k] l[r[k]]=idx r[k]=idx idx+=1 def remove(k): l[r[k]]=l[k] r[l[k]]=r[k] init() m=int(input()) for _ in range(m): s=input().split() if s[0]=='L': x=int(s[1]) insert(2,x) elif s[0]=='R': x=int(s[1]) insert(l[1],x) elif s[0]=='D': k=int(s[1])+2 remove(k) elif s[0]=='IL': k=int(s[1])+2 x=int(s[2]) insert(l[k],x) elif s[0]=='IR': k=int(s[1])+2 x=int(s[2]) insert(k,x) i=2 while i!=0: if i==2 or i==1: i=r[i] continue print(e[i],end=" ") i=r[i] 栈 N = int(1e5+10) # 假设N的值为100 stk = [0] * N tt = 0 # 向栈顶插入一个数 tt += 1 stk[tt] = x # 从栈顶弹出一个数 tt -= 1 # 栈顶的值 stk[tt] # 判断栈是否为空 if tt > 0: pass 队列 N = 100 # 假设N的值为100 q = [0] * N hh = 0 tt = -1 # 向队尾插入一个数 tt += 1 q[tt] = x # 从队头弹出一个数 hh += 1 # 队头的值 q[hh] # 判断队列是否为空 if hh <= tt: pass N = 100 # 假设N的值为100 q = [0] * N hh = 0 tt = 0 # 向队尾插入一个数 q[tt] = x tt += 1 if tt == N: tt = 0 # 从队头弹出一个数 hh += 1 if hh == N: hh = 0 # 队头的值 q[hh] # 判断队列是否为空 if hh != tt: pass 单调栈 tt = 0 stk = [0] * (n + 1) for i in range(1, n + 1): while tt and check(stk[tt], i): tt -= 1 stk[tt + 1] = i tt += 1 单调队列 n = 10 # 假设n的值为10 hh = 0 tt = -1 q = [0] * n for i in range(n): while hh <= tt and check_out(q[hh]): hh += 1 while hh <= tt and check(q[tt], i): tt -= 1 q[tt + 1] = i tt += 1 N = int(1e6+10) q=[0 for _ in range(N)] n,k=map(int, input().split()) a=[0]+[int(x) for x in input().split()] hh,tt=0,-1 for i in range(1,n+1): if hh<=tt and i-q[hh]+1>k: hh+=1 while hh<=tt and a[q[tt]] >= a[i]: tt-=1 tt+=1 q[tt]=i if i >= k: print(a[q[hh]], end=" ") print() hh,tt=0,-1 for i in range(1,n+1): if hh<=tt and i-q[hh]+1>k: hh+=1 while hh<=tt and a[q[tt]] <= a[i]: tt-=1 tt+=1 q[tt]=i if i>=k: print(a[q[hh]], end=" ") KMP m = len(p) # 假设p为模板串，长度为m n = len(s) # 假设s为模式串，长度为n ne = [0] * (m + 1) # 初始化ne数组 # 求Next数组 j = 0 for i in range(2, m + 1): while j and p[i] != p[j + 1]: j = ne[j] if p[i] == p[j + 1]: j += 1 ne[i] = j # 匹配 j = 0 for i in range(1, n + 1): while j and s[i] != p[j + 1]: j = ne[j] if s[i] == p[j + 1]: j += 1 if j == m: j = ne[j] # 匹配成功后的逻辑 n = int(input()) p = ' ' + input() m = int(input()) s = ' ' + input() ne = [0]*(n+1) j = 0 for i in range(2, n+1): while j and p[i]!=p[j+1]: j = ne[j] if p[i]==p[j+1]: j += 1 ne[i] = j j = 0 res = [] for i in range(1, m+1): while j and s[i]!=p[j+1]: j = ne[j] if s[i]==p[j+1]: j += 1 if j==n: res.append(i-j) j = ne[j] print(*res, sep=' ') Z函数 def z_function(s): n = len(s) z = [0] * n l, r = 0, 0 for i in range(1, n): if i <= r and z[i - l] < r - i + 1: z[i] = z[i - l] else: z[i] = max(0, r - i + 1) while i + z[i] < n and s[z[i]] == s[i + z[i]]: z[i] += 1 if i + z[i] - 1 > r: l = i r = i + z[i] - 1 return z Tire N = 100010 son = [[0] * 26 for _ in range(N)] cnt = [0] * N idx = 0 # 0号点既是根节点，又是空节点 # son[][]存储树中每个节点的子节点 # cnt[]存储以每个节点结尾的单词数量 # 插入一个字符串 def insert(s): global idx p = 0 for i in range(len(s)): u = ord(s[i]) - ord('a') if not son[p][u]: idx += 1 son[p][u] = idx p = son[p][u] cnt[p] += 1 # 查询字符串出现的次数 def query(s): p = 0 for i in range(len(s)): u = ord(s[i]) - ord('a') if not son[p][u]: return 0 p = son[p][u] return cnt[p] 马拉车（字符串回文串算法） class Solution: # 推荐教学视频 ：https://www.bilibili.com/video/BV1Sx4y1k7jG/?spm_id_from=333.337.search-card.all.click&vd_source=a4a2b56f746715b34521bfb853094cf4 def longestPalindrome(self, s: str) -> str: s = '#' + '#'.join(list(s)) + '#' n = len(s) p = [0]*n #每个点的 最长回文字串 能到的 两侧长度 c, r = 0, 0 # 右边能到达最远的蘑菇的位置 和 其最右边能达到的位置 for i in range(n): if i<=r: p[i] = min(r-i, p[c + c-i]) # 由已知条件得到当前位置能达到的最大右侧距离( 需要取min(镜像位置的值, 当前最大蘑菇能覆盖到的最大值) ) while i+p[i]+1 < n and s[i-p[i]-1] == s[i+p[i]+1]: p[i]+=1 if p[i]+i > r: r = p[i] + i c = i ma = max(p) idx = p.index(ma) return s[idx-ma+1:idx+ma+1:2] 并查集 N = 1000005 # 假设N的值为1000005 p = [0] * N # 初始化p数组 # 返回x的祖宗节点 def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] ''' 非递归写法 def find(x): while p[x]!=x: p[x] = p[p[x]] x = p[x] return x ''' # 初始化，假定节点编号是1~n for i in range(1, n + 1): p[i] = i # 合并a和b所在的两个集合 p[find(a)] = find(b) 维护size信息 ...

算法笔记（三）——图论（Python实现） 图论 树的存储 邻接矩阵 # 创建一个二维列表表示邻接矩阵 n = 10 # 顶点数量 g = [[0] * n for _ in range(n)] # 添加一条边a->b def add_edge(a, b): g[a][b] = 1 # 初始化 g = [[0] * n for _ in range(n)] 邻接表 # 创建一个列表表示邻接表 n = 10 # 顶点数量 h = [-1] * n e = [0] * n ne = [0] * n idx = 0 # 添加一条边a->b def add_edge(a, b): global idx e[idx] = b ne[idx] = h[a] h[a] = idx idx += 1 # 初始化 idx = 0 h = [-1] * n 树和图的存储 # 邻接表表示的图 N = 100010 # 根据具体需求设置合适的最大节点数量 # 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点 h = [-1] * N # 存储边的目标节点 e = [0] * N # 存储下一条边的索引 ne = [0] * N # 边的索引 idx = 0 # 添加一条边a->b def add(a, b): global idx e[idx] = b ne[idx] = h[a] h[a] = idx idx += 1 # 初始化 idx = 0 for i in range(N): h[i] = -1 树和图的遍历 DFS def dfs(u): st[u] = True i = h[u] while i!=-1: j = e[i] if not st[j]: dfs(j) i = ne[i] BFS from collections import deque q = deque() st[1] = True q.append(1) while q: t = q.popleft() i = h[t] while i!=-1: j=e[i] if not st[j]: st[j] = True q.append(j) i=ne[i] 拓扑排序 from sys import stdin from collections import deque input = lambda:stdin.readline().strip() def topsort(): q = deque() res = [] for i in range(1, n+1): if ind[i]==0: res.append(i) q.append(i) while q: u = q.popleft() for v in g[u]: ind[v] -= 1 if ind[v]==0: q.append(v) res.append(v) return res n = int(input()) ind = [0]*(n+1) g = [[] for _ in range(n+1)] for i in range(1, n+1): a = list(map(int, input().split())) for j in range(len(a)-1): g[i].append(a[j]) ind[a[j]]+=1 res = topsort() print(*res, sep=' ') 奖金 from sys import stdin from collections import deque def topsort(): res = [] q = deque() ans = 0 for i in range(1, n+1): if ind[i]==0: res.append(i) q.append((i, 100)) ans += 100 while q: u, m = q.popleft() for v in g[u]: ind[v] -= 1 if ind[v]==0: q.append((v, m+1)) res.append(v) ans += m+1 if len(res)==n: print(ans) else: print("Poor Xed") n, m = map(int, input().split()) ind = [0]*(n+1) g = [[] for _ in range(n+1)] for i in range(m): a, b = map(int, input().split()) ind[a] += 1 g[b].append(a) topsort() LCA def lca(x,y): if dep[x] < dep[y]: x,y = y,x d = dep[x]-dep[y] while d: # 循环直到深度差为 0 v = d & -d # 获取 d 的最低位的 1 所在的位置 i = v.bit_length() - 1 # 计算最低位的位置索引 x = fa[i][x] # 将节点 x 上移到和节点 y 同一深度 d -= v # 更新深度差 if x==y: return x for k in range(K-1, -1, -1): if fa[k][x] != fa[k][y]: x = fa[k][x] y = fa[k][y] return fa[0][x] # 初始化深度以及父节点信息 dep[x]=dep[val]+1 dep[y]=dep[val]+1 fa[0][x] = val fa[0][y] = val for k in range(K-1): fa[k+1][x] = fa[k][fa[k][x]] # 自己的第2^(1+1)级父亲即为 自己的第2^(1)级父亲 的第2^(1)级父亲 fa[k+1][y] = fa[k][fa[k][y]] 祖孙询问 from sys import stdin from collections import deque, defaultdict from math import inf K = 17 N = int(4*10e4) + 10 dep = [inf]*(N) fa = [[0]*N for _ in range(K)] def bfs(): dep[0] = 0; dep[root] = 1 q = deque([root]) while q: u = q.popleft() for v in g[u]: if dep[v] > dep[u] + 1: dep[v] = dep[u] + 1 q.append(v) fa[0][v] = u for k in range(1, K-1): fa[k][v] = fa[k-1][fa[k-1][v]] def lca(x, y): if dep[x] < dep[y]: x, y = y, x d = dep[x] - dep[y] while d: v = d & -d i = v.bit_length() - 1 x = fa[i][x] d -= v if x==y: return x for k in range(K-1, -1, -1): if fa[k][x] != fa[k][y]: x = fa[k][x] y = fa[k][y] return fa[0][x] n = int(input()) g = defaultdict(list) for i in range(n): a, b = map(int, input().split()) if b==-1: root = a else: g[a].append(b) g[b].append(a) bfs() # print(dep) m = int(input()) for i in range(m): x, y = map(int, input().split()) res = lca(x, y) if res == x and res != y: print(1) elif res == y and res != x: print(2) else: print(0) 最短路 单元最短路 ...

算法笔记（四）——数学（Python实现） 数学 试除法判定质数 def check(x): # 判定 if x<2: return False for i in range(2, int(x**0.5)+1): if x%i==0: return False return True n = int(input()) for i in range(n): x = int(input()) if check(x): print("Yes") else: print("No") 试除法分解质因数 def get(x): #分解 for i in range(2, int(x**0.5)+1): if x%i==0: cnt=0 while x%i==0: x//=i cnt+=1 print(i, cnt, sep=' ') if x>1: print(x, 1, sep=' ') n = int(input()) for i in range(n): x = int(input()) get(x) print() 线性筛法求素数 N = int(1e6+10) primes = [] st = [False]*N def get(n): for i in range(2, n+1): if not st[i]: primes.append(i) for j in range(len(primes)): if i*primes[j]>n: break st[i*primes[j]]=True if i%primes[j]==0: break n = int(input()) get(n) print(len(primes)) 朴素筛法求素数 N = 1000005 # 根据需要修改 primes = [] # 存储所有素数 st = [False] * N # st[x]存储x是否被筛掉 # 筛素数函数 def get_primes(n): global primes global st for i in range(2, n + 1): if not st[i]: primes.append(i) for j in range(i, n + 1, i): st[j] = True # Example usage: # get_primes(100) # print(primes) 试除法求所有约数 def get(x): res = [1] for i in range(2, int(x**0.5)+1): if x%i==0: res.append(i) if i!=x//i: res.append(x//i) if x>1: res.append(x) return sorted(res) n = int(input()) for i in range(n): x = int(input()) res = get(x) print(*res) 约数个数和约数之和 如果 N = p1^c1 * p2^c2 * ... *pk^ck 约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1) 约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck) 约数之和 题目大意：给定两个自然数 A 和 B，定义 S 为 A*B 的所有约数之和。求 S mod 9901 的值。 ...

算法笔记（五）——DP（Python实现） DP 数字三角形 f=[] n=int(input()) for _ in range(n): f.append([int(x) for x in input().split()]) for i in range(n-2,-1,-1): for j in range(i+1): f[i][j]=max(f[i+1][j], f[i+1][j+1])+f[i][j] print(f[0][0]) 背包 空间优化成1维之后，只有完全背包问题的体积是从小到大循环的 01背包 N = int(1e3+10) f=[ 0 for _ in range(N) ] n,v=map(int,input().split()) for i in range(n): vi,wi=map(int,input().split()) for j in range(v, vi-1,-1): f[j]=max(f[j],f[j-vi]+wi) print(f[v]) 多重背包 单调队列 MN = int(2e4+10) f=[0 for _ in range(MN)] q=[0 for _ in range(MN)] g=[0 for _ in range(MN)] N,V = map(int, input().split()) for i in range(N): v,w,s=map(int, input().split()) g=f[:] for j in range(v): hh,tt=0,-1 for k in range(j,V+1,v): while hh<=tt and q[hh]<k-s*v: hh+=1 while hh<=tt and g[q[tt]]+(k-q[tt])//v*w <= g[k]: tt-=1 tt+=1 q[tt]=k f[k]=g[q[hh]]+(k-q[hh])//v*w print(f[V]) 二维费用背包 N = int(1e2+10) f=[[0]*N for _ in range(N)] n,V,M = map(int , input().split()) for i in range(n): v,m,w=map(int , input().split()) for j in range(V,v-1,-1): for k in range(M, m-1, -1): f[j][k]=max(f[j][k], f[j-v][k-m]+w) print(f[V][M]) 宠物小精灵 题目大意：小智在野外捕捉宠物小精灵，他带了一些精灵球和皮卡丘，精灵球可以捕捉小精灵，但每捕捉一个小精灵都会消耗精灵球和减少皮卡丘的体力。现在给定小智拥有的精灵球数量、皮卡丘的初始体力值以及每个小精灵需要的精灵球数量和对皮卡丘造成的伤害数目，问小智最多能捕捉多少个小精灵，并且在这种情况下，皮卡丘的剩余体力值最多是多少。 ...

算法笔记（一）——基础+杂项（Python实现） 基础+杂项 快速排序 def quick_sort(q, l, r): if l>=r: return i,j,x=l-1,r+1,q[(l+r)>>1] while i<j: i+=1 while q[i]<x: i+=1 j-=1 while q[j]>x: j-=1 if i<j: q[i], q[j] = q[j], q[i] quick_sort(q, l, j) quick_sort(q, j+1, r) n=int(input()) arr=list(map(int, input().split())) quick_sort(arr,0,n-1) print(" ".join(map(str, arr))) 随机选择pivot import random class Solution: def sortArray(self, nums: List[int]) -> List[int]: def quick_sort(q, l, r): if l >= r: return # 随机选择 pivot i, j = l, r rand_idx = random.randint(l, r) x = q[rand_idx] while i <= j: while q[i] < x: i += 1 while q[j] > x: j -= 1 if i <= j: q[i], q[j] = q[j], q[i] i += 1 j -= 1 quick_sort(q, l, j) quick_sort(q, i, r) quick_sort(nums, 0, len(nums) - 1) return nums 归并排序 j = mid+1 !!! ...

周赛240407 出师不利，第一题变量名能写错，慢就是快，少就是多，提交之前一定要有万全的检查。 第二题100242. 满足距离约束且字典序最小的字符串 纯思维题，先花时间想清楚基础问题再想后面的问题。吸取教训，代码一定要写的清晰明了，自己才能更好的看懂并写下去。 ...

VP 周赛 第 389 场周赛 第三题3085. 成为 K 特殊字符串需要删除的最少字符数 双指针优化$O(n)$ 第三题做出来了但做法不优并且错的次数太多了。 题目大意：给定一个字符串word和一个整数k，定义特殊字符串为满足|freq(word[i]) - freq(word[j])| <= k对于字符串中所有下标i和j都成立的字符串。其中，freq(x)表示字符x在word中的出现频率，|y|表示y的绝对值。要求计算使word成为k特殊字符串所需删除的字符的最小数量。 ...

周赛240331 第四题 100240 最小化曼哈顿距离 题目大意：给定一个二维平面上的点集，求移除其中一个点后，剩余点集中任意两点之间的最大曼哈顿距离的最小值。 实现思路：首先，对于曼哈顿距离而言，它的定义是两点在各个坐标轴上的差的绝对值之和。所以移除一个点后，影响到最大曼哈顿距离的主要是距离移除点最近的点。我们可以将点的坐标进行转换，将其转换为(x+y)和(x-y)的形式，这样在平面上的曼哈顿距离就可以等效为在转换后的坐标系下的欧几里得距离。然后我们用两个有序集合分别维护x+y和x-y的坐标轴上的值，分别为xset和yset。然后遍历每个点，从点集中移除一个点，更新最大距离，找到最小值。 ...

周赛 24/3/24 第三题 100258 3092. 最高频率的 ID 题目大意：给定两个长度为n的整数数组nums和freq，nums中的每个元素表示一个ID，对应的freq中的元素表示这个ID在集合中此次操作后需要增加或者减少的数目。现要求在每一步操作后，返回出现频率最高的ID数目，若集合为空则为0。 SortedList实现 ...