基础算法学习笔记

保持算法手感但不必过度投入确保能熟练解决 LeetCode Hot 100 中的动态规划、二叉树、链表类中等难度题目即可足以应对国内大厂的“手撕”环节。核心精力投入“手写组件”这是你的差异化优势所在。你能理解推荐系统中的序列建模就一定能理解 Attention 的本质。重点练习用 PyTorch 手写 MHA、KV Cache 的逻辑、以及 PPO/DPO/GRPO 的 Loss 计算。这不仅是面试考点更是你深入理解 Agent 策略优化与你推荐的序列决策直接相关的必经之路。在Python中函数入参是否可被修改取决于参数类型不可变对象‌整数、字符串、元组‌等不可变类型函数无法修改其值。 ‌可变对象‌ 列表、字典、集合‌等可变类型函数内部修改会影响原始对象。 ‌解决算法问题的思路1、枚举核心问题1.避免无用的组合可以减少枚举的次数 2.找到枚举的规律 3.是否存在一个局部一旦这个局部确定其他部分也确定了2、递归核心问题1.后一项依赖前一项的结果如等差、等比数列 2.从大到小考虑 3.本身问题的定义包含递归如A的定义用到了自身A并且包含终止条件 4.将递归问题分解成更小的字问题求解可以用递归的写法一般都可以用死循环while 写3、二分查找核心问题1.凡事按顺序大小查找的程序都可以用二分查找优化只要看到面试题里给出的数组是有序数组都可以想一想是否可以使用二分法。明确区间定义【】左闭右闭 while (left right) 要使用 因为left right是有意义的所以使用 if (nums[middle] target) right 要赋值为 middle - 1因为当前这个nums[middle]一定不是target那么接下来要查找的左区间结束下标位置就是 middle - 1如果想确定中间的插入位置就是right1如果想确定左右上界排除初始值-2开始分别为 left1 和 right-1也可以局部遍历4、移动元素双指针法1、快慢指针(遍历快指针逐个赋值遇到特殊情况跳过)移除元素可以直接交换仅去除重复在后1个位置交换移除或删除回退可以反向变量数组可以避免数组长度变化的问题 del nums[index]或新申请一个数组保留结果renums []renums.append(val)nums[:len(renums)] renums2、相向指针遍历left指针遇到特殊情况赋值写起来比快慢指针要复杂3、双指针还可以用于滑动窗口、比如求和求乘积等如果两个循环的复杂度跟一个循环相同尽量用两个循环写。逻辑更简单字典声明dict()带默认值的字典函数defaultdict(int)判断是否存在 x in d1 或 not in 元素个数len(),删除元素 del my_dict[‘a’] 或 my_dict.pop(x)数组操作python 数组需要 数组间赋值不能直接改为一个值https://blog.csdn.net/m0_73633088/article/details/128859556旋转数组保证循环不变量原则里面每次是减少2反向循环尽量写的简单。按顺序循环**一维数组声明 [0] * n[0 for _ in range(n)]二维数组声明 [ [0] * n for i in range(m) ]二维数组赋值用for循环dp[:][0]1不能用二维数组取最大值 max(dp)不能用二维数组行列求和用for循环用乘法声明数组是引用更改数组内容可能出问题matrix [[0]*2]*2字符不可以直接当成list改变需要先转成数组长度可以直接取word_list list(word)word_list[i] x数组转字符串 “”.join(word_list)字符串转小写 s.lower()判断字符串是否为字母和数字 s.isalnum()数组声明 [] renums.append(val)列表合并 [] []一维数组复制如果不想是引用 res nums[:]二维列表元素放入[].append(list([1])) 或 [].append(L[:]) 或 [].append(L.copy())L1 [‘a’, ‘b’]L2 [‘c’, ‘d’]L1.append(L2) # 结果: [‘a’, ‘b’, [‘c’, ‘d’]]L1.extend(L2) # 结果: [‘a’, ‘b’, ‘c’, ‘d’]字典声明 dict() 或 {1:‘a’,2:‘b’ } 或 defaultdict(int) 或 defaultdict(list)获取dict[x] ,dict.get(x,unknown) 使用get可以避免空值报错删除 del my_dict[x] 或 my_dict.pop(x)获取dic 的dic,keys() 或dic,values() 如果放到list里就是list(dic,keys())也可以直接放入指针节点最为key比如dict[ListNode]字典中放入list内存引用不可切换复制在引用中操作 index_dict[key].append(value)集合声明 set() 增加set1.add() 删除set1.remove()for num in nums_set: # ← 正在遍历 nums_setnums_set.remove(num) # ← 同时又在修改它 ❌不可以一遍遍历一遍修改可以使用while nums_set:nums_set.pop()队列 from collections import dequedeque[0] deque[-1] 可以用list代替堆操作 import heapq ,第一个输入是listheapq.heappop([])heapq.heappush([],x)随机默认是小数包含头尾节点int类型i random.randint(0, len(self.l)-1)列表内随机返回元素random.choice(self.l)5、链表虚拟头需要遍历的指针指向head如果是反转直接虚拟头为None 就可以链表头直接是直接赋值别名需要赋值后直接更新之前的节点需要判空处理如果是空节点查询其中的值会报错差不到5、排序python 默认排序函数 sorted(x) 字符串排序完是数组快速排序复习下可以用多key排序lambda表达式arr.sort(keylambda x:(count_bits(x),x))6、分治核心问题1.把一个任务分成形式和原任务相同但规模更小的一个或几个部分任务分别完成处理完成后的结果归并排序、快速排序5、动态规划类型 1记忆递归型动归程序直观简单递归转动规的一般转化方法从边界值向前推导递归函数的逆过程。 速度更快使用滚动数组节省空间1、递归的分析问题分解成若干子问题子问题和原问题形势相同子问题保存结果避免重复计算。2、确定状态某个状态下的值对应字问题的解3、确定一些初始状态边界状态的值4、确定状态转移方程能用动态规划解决的问题的特点。1、问题具有最优子结构性质 2、无后效性6.深度优先搜索寻找图上到一些节点的路径或多种可能性遍历相邻节点记录状态递归遍历可能性的去除状态剪枝对已经知道结果的枝不在探索记录下目前最优结果进行比较可行性剪枝和最优性剪枝1.深度优先搜索确定枚举2.搜索的范围3.搜索的顺序4.如何剪枝7.广度优先搜索1.初始节点放入open队列2.判断是否为空为空没达到则无解3.取出点放入close表4.判断是否为目标节点5.是否可扩展不可扩展则返回第2步6.可扩展则判重后放入open表尾部返回第2步8.贪心算法在问题求解时总是作出当前看来最好的选择。贪心算法要求贪心策略具备无后效性某个之前的状态不会影响以后的状态及局部最优解为全局最优解先排序在遍历9、算法题概率论https://www.cnblogs.com/xianbin7/p/10690064.html赛马比赛https://zhuanlan.zhihu.com/p/79971028