算法类型小记
链表问题[*]翻转、回文、相交、倒数第k个：一般都用双指针（快慢指针）
[*]倒序打印、操作：后序遍历即可
数组问题
[*]翻转、回文、相交、n-sum：一般都用双指针
[*]区域和：一般使用前缀和数组
[*]区间增减：一般使用差分数组
[*]矩阵旋转：先按照对角线镜像对称，再对每一行进行翻转
[*]矩阵的螺旋遍历：利用边界移动实现
[*]满足条件的最短区间：滑动窗口（先移动右，满足条件后移动左，满足条件后再移动右）（通过while里面套while实现）
[*]田忌赛马：将对手用优先队列排序（用pair存位置），自己也排序，然后将自己和对手从最大的开始比较，若自己大于则使用，不大于则用最小的
[*]常数时间删除/查找任意元素：用 map 存储数组的 index-value，用空间换时间
[*]左边第一个小的数：单调栈解决
二叉树问题
[*]翻转：对所有节点左右子树交换即可
[*]存在跨越父节点的问题：遍历时将 traverse(root) 改为 traverse(root->left,root->right)
[*]通过数组构造最大二叉树：每次找最大，然后二分
[*]通过前（后）序和中序遍历构造二叉树：画图，根据preorder在中序的位置获取leftsize
[*]根据前序、后序构造二叉树：画图，根据preorder在后序的位置获取leftsize
[*]计算完全二叉树的节点数：不要一个一个加，用判断满二叉树方法计算数量
数据结构问题
[*]栈实现队列：用两个栈换下顺序即可
[*]队列实现栈：队尾进队头，然后弹出队尾
[*]单调栈问题：反向遍历+栈只存比前面大的数
[*]单调队列：可使用deque实现单调队列
图问题
[*]图结构：邻接表/邻接矩阵 实现
[*]图遍历、环检测：用visited和onpath记录遍历状态
动态规划
[*]核心思想是穷举，目标是找出正确的状态转移方程
三要素：重叠子问题、最优子结构、状态转移方程
四步走：① 确定base case ② 确定状态，也就是原问题和子问题中会变化的变量 ③ 确定选择，也就是导致状态变化的行为 ④ 明确dp函数/数组的定义
[*]框架
# 自顶向下递归的动态规划
def dp(state1, state2, ...):
for choose in all_choose:
result = max(result, dp(state1, state2, ...))
return result
# 自底向上迭代的动态规划
dp[...] = base case
for state1 in all_state1:
for state2 in all_state2:
for ...
dp[...] = max(state1，state2...)
[*]最长递增子序列：dp 表示以 nums 这个数结尾的最长递增子序列的长度
[*]信封俄罗斯套娃问题：先按宽度升序排列，如果宽度一样，则按高度降序排列；然后再在高度序列上找最长递增子序列
实战注意
[*]小数偏差：比如 x 和 y 是两个六位小数，那么不能直接 x>y 而是 x-y>1e-8（一般往后多两位）
[*]离散化：这个知识点还是需要重新做，比较绕
[*]位运算：&（与）、^（异或）、|（或）、~（取反）
①x&-x 得到的是 x 二进制第一个非0的最小位所代表的数的大小，这个叫做 lowbit 操作
②获取 n 的二进制第k位：n>>k&1
[*]最大公约数：int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
[*]求组合数：\(C^i_j=C^{i-1}_{j}+C^{i-1}_{j-1}\)
[*]int转string：to_string，string转int：stoi
[*]贪心：定义比较规则
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]