基础算法（一）
排序
一.剑指offer
40.最小的K个数(Top k) （一串）
一.思路
核心考点：堆排序
1.注意：维护大根堆（因为max堆顶弹出）；始终保证堆内k个最小
2.时间 o(nlogk)
二.python语法
1.导入：import heapq
2.函数使用：压入当前值：heapq.heappush；弹出最小值+压入当前值heapq.replace；弹出最小值heapq.heappop
40变形.最小的第k个数（一个）
一.思路
核心考点：快排（快选）
1.y总模板；（不同之处）多引入参数k、递归左or右 注：记得特判边界
2.时间o(nlogn)
35.数组中的逆序对
一.思路
核心考点：归并排序
1.归并：特判+确定分界点+递归+合并（比较、扫尾、物归原主）
2.难点：逆序对数量思考：三种情况：全左；全右；一左一右（res+=mid-i+1）
二.python语法
1.def与return配对使用
二.Leetcode高频
后续补充
二分+查找
一.剑指offer
4.二维数组查找
一.思路
核心考点：对象是二维
1.难点：二维数组有序–>从右上角开始找（注意先特判行；再求列；舍弃）
2.时间o(n^2) –> O(n+m) 一维
二.python语法
1.二维矩阵matrix
2.行数：rows = len(array)；列数：cols = len(array[0])
11.旋转数组的最小值
一.思路
核心考点：需要预处理的二分+特判
1.预处理：去重（如上图红圈所示）：n指针左移
2.满足二段性：二分（特判单增情况-直接返回[0]；仔细考虑l r变化）
3.时间：o(n) 因为存在重复
53-I-在排序数组中查找数字
一.思路
核心考点：端点–>区间
1.有序数组：二分
2.次数：即计算区间：右端点-左端点（求左；判断[l]?=k;存储l；求右；相减）
53-II-0-n-1中缺失的数字
一.思路
核心考点：二段性的选取+特判
1.递增数组：二分（仔细考虑l r ）
2.while循环结束之后：特判 r++（若缺的是最后一位）
二分+查找的一些总结
核心考点：在一些地方变化之后的二分
1.预处理（e.g.去重）
2.特判（e.g.二分可以走完；但未必就是答案）
二.Leetcode高频
4.寻找两个有序数组的中位数
[ x ]349.两个数组的交集（set+哈希表）
后续再补充
位运算
一.剑指offer
15-二进制中1的个数
一.思路
核心考点：位运算两个常用操作
1.有符号数–>无符号数
2.常用操作：取个位（n&1）；去个位(n>>1)
二.python语法
1.变为无符号数：python强行32位：n=n&0xFFFFFFFF
16-数值的整数次方
一.思路
核心考点：次方运算定义+二进制理解+特判
注：直接用for循环会超时
1.从次方运算定义出发+结合二进制位运算（把x^n 拆成x^2 和 x）
2.难点：指数<0，特判
二.Leetcode高频
[ X ]78-子集（位运算+DFS）
[ X ]421-数组中两个数的最大异或值(前缀树+异或)
数据结构（一）
链表
一.剑指offer
6-从尾到头打印链表
一.思路
核心考点：
1.先遍历（使用python的列表[ ]数据类型来存储）
2.再翻转（[: :-1]）
二.python语法
1.列表res=[ ]作为栈来使用，append
2.切片的几种学习：取最后一个元素[-1]；取除了最后一个元素[ : -1]；翻转[: : -1]
22-链表中倒数第k个结点
一.思路
核心考点：单链表不能“倒序”遍历–>要转换成正序
1.先遍历一次，计数链表长度n
2.转换：倒数k–>正数：n-k+1（注意下标从0开始）
二.链表语法
1.指针：但指向的值val？（return p 返回的是p节点的值？）
2.值：val存储当前值
24-反转链表
一.思路：
核心考点：反转：开一个前驱节点pre
1.初始化：cur从head开始；则pre在head前面为None （常用经验）
2.（做题要结合图理解）进行指针反转；记得先保存cur的next后续使用
25-合并两个或k个有序链表
一.思路：
核心考点：归并排序+不同之处（含有链表的指针next）
1.初始化：虚拟头节点dummy；当前尾节点cur
2.合并（cur.next赋；cur右移；L1/L2右移）+扫尾
二.python语法的使用
1.创建虚拟头节点的方法：dummy=ListNode(-1)
2.返回链表的写法：dummy.next
35-复杂链表的复制
一.思路：
核心考点：（一定要画图理解）多了random；考察对链表的理解
1.新建复制节点–>插入每个原节点后（新建np+给p赋(先存储)+更新p/np）
2.处理random（遍历）
3.串起np复制节点（操作：初始化虚头dummy/当前尾cur+给cur赋+更新cur/p）
二.python语法的使用
1.创建新的头节点：np=ListNode(p.val)
链表总结
1.常用操作：
1）打印：从尾到头；倒数K
2）反转：前驱节点
3）合并：虚拟头节点
4）复制：插入；指针变化
2.经验做法
1.新建虚拟头；新节点
2.链表常用四步：（先存next）赋值+更新两指针
二.Leetcode高频
[ X ]3（链表中）两数相加 （初等数学）
[ X ]24-两两交换链表中的节点（虚拟头+递归）
二叉树
一.剑指offer
7.重建二叉树
一.思路：
核心考点：前序/中序性质（根节点的分布）+递归
1.前序确定根节点（第一个值）+中序索引确定左右子树长度（Python中index函数）
2.递归：不断在前中之间来回，确定“当前”根 (难点：切片的取值/端点)
二.python语法的使用
1.写法细节：前序遍历（数组）preorder ；一个值preorder[0]；（以该值的）一个节点TreeNode(preorder[0])
2.index函数：返回某值的索引位置
3.python切片的包含关系：（注：下标从0开始）（含前；不含后）
[:n]第一项到第n项（不含n）；[n:]第n+1项到最后一项（含n）
26.树的子结构
一.思路
核心考点：把字符串变成放到树中进行“匹配”
1.寻找（所有可能性），枚举：main
2.匹配（严格当前值），判断：part
二.实现
注：两次递归的不同之处
1.main函数：特判空+part成立True；否则，把2放入1的左or右子树继续找
2.part函数（如何匹配当前：匹配的细节）：三种情况–>检查1 2的左/右完全相等（且）
树匹配总结：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/pi-pei-lei-er-cha-shu-ti-mu-zong-jie-by-z1m/
二叉树总结
一.常用操作
1.前/中/后序遍历；层序遍历
2.翻转，合并
二.定义理解
1.节点，叶子节点，度，深度
2.二叉搜索树，平衡树等
三.常考结合
1.dp 95/96 不同的二叉搜索树
2.栈 94 二叉树的中序遍历
3.bfs 层序遍历 从上到下打印
4.dfs 深度 平衡二叉树
二.Leetcode高频
详见上一栏
堆
哈希表
栈与队列
单调栈
一.思路
核心性质：给一个序列，求每个数，左边（右边），离它最近且比它小（大）的数
单调队列
一.思路
核心性质：对应题型：滑动窗口
基础算法（二）
DFS
一.剑指offer
二.Leetcode高频
[ ]46.全排列
012-矩阵中的路径
034-二叉树中和为某一值的路径
055-I-二叉树的深度
055 – II-平衡二叉树
BFS
一.剑指offer
13.机器人的运动范围
一.思路
核心考点：BFS（每次距离+1）+
（A）预处理1
1.get_sum函数：计算当前值的个+十位和
2.is_valid函数：判断当前点有效（在边界内+值<k）
（B）开始移动
1.特判
2.预处理2
1）标记状态（python set开一个元素集记录）
2）上下移动（难点1.向量表示）
3.开始搜索（难点2.BFS模板）
1）q <– 1
2）q为真：移动+赋值（用is_valid判断）+更新状态
二.Leetcode高频
032-I-从上往下打印二叉树
032-II-从上往下打印二叉树II
032-II-从上往下打印二叉树III
动态规划
一.剑指offer
19.正则表达式匹配
一.思路
核心考点：分情况讨论，‘’号的情况
核心思路：因为代表的是修改“前面”字符的情况，所以是根据“后面”（i+1,j+1等）的状态递推前面的情况
e.g.从后往前走，当遇到‘’时，看前一个（j）与（i）关系，从而决定0次 or 多次
1.状态表示f[i][j]
即：集合s[i…]，与集合p[j…]，从i/j相匹配
二.状态计算 （分情况讨论）
1.p[j]是正常字符：s[i]==p[j]； dp[i][j]= dp[i+1][j+1]
2.p[j]是“.”：f[i][j]=f[i+1][j+1]（跳过’.’）
3.p[j+1]是“”：分析’‘会代表的次数+’’前面的字符情况（最复杂）
1）0次，f[i][j]=f[i][j+2] （还要考虑j是否为“.”的情况）
2）>=1次，f[i+1][j]
二.Leetcode高频
三.Acwing
2.01背包问题
895.最长上升子序列
897.最长公共子序列
282.石子合并（区间DP）
动态规划总结
按照y总思路：对DP分解+画图
回溯
46.全排列
笔试遇到但不太会的
字符串处理
回文（DP）
注：647与5类似；但先求所有子串个数；再求所有子串中的最长值
647.回文子串
一.思路
核心考点：转移方程 s[i]==s[j] and (j-i<2 or dp[i+1][j-1])
1.难点：边界j-i<2的思考
注：详细分析见下5
二.结合本题
1.简化max_len,答案变成统计res+=1
2.变化之处j–>j+1（j要取到；因为ij可以相同-True）
5.最长回文子串
一.思路
核心考点：动态规划
1.状态表示 dp[j][i]
1）集合：表示以i为起始下标，j为终点下标的是回文子串
2）性质：bool
2.状态计算
1.边界：j-i<3:dp[i][j]=True （结合’aa’‘aba’理解）
2.转移方程：dp[i][j]=（s[i]==s[j]）and (dp[i+1][j-1])
二.模板/套路整理
1.初始化 dp（二维）
2.遍历：转移方程+特判（代入转移方程）
3.结合本题要求，返回相应/不同的值(本题max_len)
4.变化之处，有较多边界特判
214.最短回文串（KMP）
564.寻找最近的回文数
括号序列
20.有效的括号
一.思路
考点：栈/队列
核心思想：有效括号的，部分子表达式仍然是有效括号–>(正是栈的操作)把最小括号对出栈+判空为真
1.出栈
2.优化：用哈希表搜索能否形成括号
二.python语法的使用
1.哈希表的建立和存储
字典：d = {‘a’:1,’b’:2,’c’:3} 冒号’:’表示映射
32.最长有效括号
考点：栈+前缀和
一.思路：
核心思想：
1.每个左括号对应的右括号是一定的
2.括号序列合法 <–> （等价于）所有前缀和>=0 and 总和等于0（数量相等）
注：这两条是括号序列常用经验
二.实现
1.实现：y总三种情况分析
2.完善：翻转+建立work函数
注：因为cnt>0时一直在继续做；当左括号>右括号时，没有破除条件
三.python语法
1.括号的变化：运用ASCII+异或
s=s[::-1]
s2+=chr(ord(s[i])^1)
并查集
后续再补充
数组的处理
39-数组中出现次数超过一半的数字
一.思路
核心考点：题眼：要找的该值次数超过一半（保证下文中cnt起码多1）
1.（y总-消耗的思想）三种情况：cnt=0,把当前值x赋进val；val==x，cnt+1（计数）；val!=x，cnt-1（消耗）
