一些算法题的反思总结

1.技巧总结有序———想二分连续———①滑动窗口② DPdp[i]表示以i结尾的xxxxx③前缀和f(ij)-f(i)重复——哈希/Counter/defaultdict子问题——1️⃣递归先定义结束如何退出再考虑当前值怎么做2️⃣动态规划先想dp[i]的含义贪心——找规律找最佳处理方式BFS——优先队列DFS——优先递归2.易错/不熟悉的函数1join()不是字符串版的append()##join() res s abc res.join(s[1:3]) # 结果是 bc但没有赋值给任何变量 res # 输出 ##正确做法 ansres.join(s[1:3]) ans # 输出 bc ##append() res [] res.append(23) # 直接修改了 res 列表 res # 输出 [23] ##注意append是原地操作 res[].append(23) res # 输出 None字符串方法如join()通常返回新字符串不改变原字符串列表方法如append()通常直接修改原列表【补充】str.join()是用来连接字符串列表的比如 .join([hello, world])→hello world。2向上整除向下取整向零取整向上整除(a b - 1) // b向下整除a // b向零取整int(a/b)3两个字典比较可以键和值同时列表不能但字典也不能直接使用、、、这类比较运算符进行比较。尝试这样做会引发TypeError只能作用在key上4strip()移除字符默认移除空格和换行符其他括号里是啥去啥5正则表达式1.1 re.findall() 函数re.findall()是 Pythonre正则表达式模块中的一个常用函数用于在字符串中查找所有匹配正则表达式的子串并以列表形式返回所有匹配结果。6sort函数i.sort()是列表的方法会原地修改列表ii.sorted()是内置函数返回一个新的排序后的列表iii.list.sort(keylambda x: expression)key参数接受一个函数该函数作用于列表的每个元素上lambda是一个匿名函数x代表列表list中的每个元素简单属性排序people.sort(keylambda x: x.age)# 按年龄排序多属性排序 people.sort(keylambda x: (x.last_name, x.first_name))# 先按姓排序再按名排序逆序排序 students.sort(keylambda x: x.score, reverseTrue)# 按分数降序排序iv.字典不能直接用sort函数cntCounter(nums) hsorted(cnt,keylambda x:x.values())##错误用法这里x是字典的键而不是键值对 hsorted(cnt, keylambda x: cnt[x])##正确用法# 按键排序 sorted_keys sorted(my_dict.keys()) # 按值排序 sorted_values sorted(my_dict.values()) # 按键值对排序按键 sorted_items sorted(my_dict.items())7ord函数ord()返回一个Unicode 字符对应的整数编码值即 ASCII 码或 Unicode 码点常用于1.计算字母的序号char c position ord(char) - ord(a) 1 print(position) # 输出32.检查字符类型如数字、字母等char 7 if ord(0) ord(char) ord(9): print(这是一个数字) else: print(这不是数字)3.字符大小写转换lower_char a upper_char chr(ord(lower_char) - 32) # a → A97 → 65 print(upper_char) # 输出A4.chr()函数的关系chr()是ord()的逆操作用于将 Unicode 码点转回字符ord(A)→65chr(65)→A【补】ASCII码数字0~9 大写字母A~Z 小写字母a~z十进制字符说明0NUL空字符Null32空格48~570~9数字65~90A~Z大写字母97~122a~z小写字母126~波浪号8isalnum函数isdigit函数lower()函数upper函数isalnum函数检查字符串是否仅由字母a-z, A-Z和数字0-9组成。如果是则返回True否则返回Falseisdigit函数检查字符串是否只包含数字字符像负数、小数会返回Falsestr.lower()或str.upper()函数用于把大写转小写、小写转大写print(abc123.isalnum()) # True字母 数字 print(abc.isalnum()) # True仅字母 print(123.isalnum()) # True仅数字 print(abc 123.isalnum()) # False包含空格 print(abc-123.isalnum()) # False包含 - print(.isalnum()) # False空字符串9pairwise函数每次迭代返回当前元素和下一个元素组成的元组(a, b)。如果输入的可迭代对象少于2个元素则不会返回任何内容。from itertools import pairwise data [1, 2, 3, 4] for a, b in pairwise(data): print(a, b) #输出 #1 2 #2 3 #3 410位运算二进制下① 与两位都为1才得1其他都是0注意与1做位就是它本身与0做都是0②|或两位中只要有一个1就得1。③^异或两位不同得1相同得0。异吗异那就是1任何数与自身异或结果为 0a ^ a 0任何数与 0 异或结果为它本身a ^ 0 a注意异或有三种结果0对对碰1本身④~非单目运算0变11变0。11__lt__方法__lt__是 Python 的特殊方法magic method用于定义对象的小于比较行为当使用运算符比较两个对象时Python 会自动调用第一个对象的__lt__方法。##合并K个升序链表 class ListNode: def __init__(self, val0, nextNone): self.val val self.next next ListNode.__lt__lambda a,b:a.valb.val class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]: h[head for head in lists if head]##这里if head后测试2 3均包括了 heapify(h) dummycurListNode() while h: nodeheapq.heappop(h) cur.nextnode curcur.next if node.next: heapq.heappush(h,node.next) return dummy.next12round保留小数round()函数用于对浮点数进行四舍五入。round(number, ndigitsNone) number: 要四舍五入的数字 ndigits: 保留的小数位数可选默认为013numpy、nn、torchNumPy: 数值计算、数组操作、科学计算torch.nn: 神经网络层、损失函数、模型构建PyTorch (torch): 张量操作、自动微分、优化器14list()和[]不一样①创建空列表时功能一样②从对象创建列表时不一样[ ]里是把对象当成了一个元素# list() 可以将任何可迭代对象转换为列表 my_string hello my_tuple (1, 2, 3) my_set {4, 5, 6} my_dict {a: 1, b: 2} # list() 会遍历可迭代对象的每个元素 list_from_string list(my_string) # [h, e, l, l, o] list_from_tuple list(my_tuple) # [1, 2, 3] list_from_set list(my_set) # [4, 5, 6] (顺序可能不同) list_from_dict list(my_dict) # [a, b] (只取键) # [] 只是原样包含传入的对象 bracket_from_string [my_string] # [hello] (整个字符串作为一个元素) bracket_from_tuple [my_tuple] # [(1, 2, 3)] (整个元组作为一个元素) bracket_from_set [my_set] # [{4, 5, 6}] (整个集合作为一个元素) bracket_from_dict [my_dict] # [{a: 1, b: 2}] (整个字典作为一个元素)15数组assert函数、pop函数插入在末尾append时间复杂度 O(1)其他assert(idx,num),时间复杂度 O(N)删除pop(idx),idx默认为-1删末尾时间复杂度 O(1)删其他时间复杂度 O(N)索引arr.index()arr [] for i in range(10): # 在末尾追加元素时间复杂度 O(1) arr.append(i) # 在中间插入元素时间复杂度 O(N) # 在索引 2 的位置插入元素 666 arr.insert(2, 666) # 在头部插入元素时间复杂度 O(N) arr.insert(0, -1) # 删除末尾元素时间复杂度 O(1) arr.pop() # 删除中间元素时间复杂度 O(N) # 删除索引 2 的元素 arr.pop(2) # 根据索引查询元素时间复杂度 O(1) a arr[0] # 根据索引修改元素时间复杂度 O(1) arr[0] 100 # 根据元素值查找索引时间复杂度 O(N) index arr.index(666)(16)字典的[ ]和get函数核心区别键不存在时特性中括号d[key]d.get(key)键存在返回对应的值返回对应的值键不存在抛出KeyError异常返回None或指定的默认值d[key]可用于赋值get只能读取d.get(key)可以指定key不存在时的默认值而中括号无法做到3.模版1BFSBFS 模板双向队列 已访问集合 层级步数。from collections import deque def bfs(grid, start): rows, cols len(grid), len(grid[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上下左右 queue deque([start]) # 初始化队列存储 (i, j) 或 (i, j, steps) visited set([start]) # 记录已访问的节点避免重复 while queue: i, j queue.popleft() # 如果是带步数的 BFS可以用 i, j, steps queue.popleft() # 检查是否到达目标如边界、特定位置等 if is_target(i, j): return steps # 返回步数或操作次数 # 遍历四个方向或八个方向 for di, dj in directions: ni, nj i di, j dj # 检查是否越界、是否可访问、是否未被访问 if 0 ni rows and 0 nj cols and grid[ni][nj] . and (ni, nj) not in visited: visited.add((ni, nj)) queue.append((ni, nj)) # 如果是带步数的 BFS可以 queue.append((ni, nj, steps 1)) return -1 # 如果没有找到目标返回 -12DFSDFS 核心递归 / 栈 回溯 剪枝。4. 常用库函数collections双向队列、计数器、有序字典from collections import deque from collections import Counter from collections import OrderedDict ##deque popleft: 弹出队列首部的元素 appendleft在左侧添加元素 ##OrderedDict move_to_end(key):移到队尾lastFalse是移到队首 popitem(key):移除队尾元素lastFalse是移到队首heapq堆import heapqmath向上取整、向下取整、平方根import math math.ceil(4.2) # 5向上取整 math.floor(4.8) # 4向下取整 math.sqrt(16) # 4.0平方根bisect: bisect_left