算法类型小记

链表问题

• 翻转、回文、相交、倒数第k个：一般都用双指针（快慢指针）
  
• 倒序打印、操作：后序遍历即可
  

数组问题

• 翻转、回文、相交、n-sum：一般都用双指针
  
• 区域和：一般使用前缀和数组
  
• 区间增减：一般使用差分数组
  
• 矩阵旋转：先按照对角线镜像对称，再对每一行进行翻转
  
• 矩阵的螺旋遍历：利用边界移动实现
  
• 满足条件的最短区间：滑动窗口（先移动右，满足条件后移动左，满足条件后再移动右）（通过while里面套while实现）
  
• 田忌赛马：将对手用优先队列排序（用pair存位置），自己也排序，然后将自己和对手从最大的开始比较，若自己大于则使用，不大于则用最小的
  
• 常数时间删除/查找任意元素：用 map 存储数组的 index-value，用空间换时间
  
• 左边第一个小的数：单调栈解决
  

二叉树问题

• 翻转：对所有节点左右子树交换即可
  
• 存在跨越父节点的问题：遍历时将 traverse(root) 改为 traverse(root->left,root->right)
  
• 通过数组构造最大二叉树：每次找最大，然后二分
  
• 通过前（后）序和中序遍历构造二叉树：画图，根据preorder[prestart]在中序的位置获取leftsize
  
• 根据前序、后序构造二叉树：画图，根据preorder[prestart+1]在后序的位置获取leftsize
  
• 计算完全二叉树的节点数：不要一个一个加，用判断满二叉树方法计算数量
  

数据结构问题

• 栈实现队列：用两个栈换下顺序即可
  
• 队列实现栈：队尾进队头，然后弹出队尾
  
• 单调栈问题：反向遍历+栈只存比前面大的数
  
• 单调队列：可使用deque实现单调队列
  

图问题

• 图结构：邻接表/邻接矩阵 实现
  
• 图遍历、环检测：用visited和onpath记录遍历状态
  

动态规划

• 核心思想是穷举，目标是找出正确的状态转移方程
  三要素：重叠子问题、最优子结构、状态转移方程
  四步走：① 确定base case ② 确定状态，也就是原问题和子问题中会变化的变量 ③ 确定选择，也就是导致状态变化的行为 ④ 明确dp函数/数组的定义
  
• 框架
  1. # 自顶向下递归的动态规划
  2. def dp(state1, state2, ...):
  3.     for choose in all_choose:
  4.         result = max(result, dp(state1, state2, ...))
  5.     return result
  7. # 自底向上迭代的动态规划
  8. dp[0][0][...] = base case
  9. for state1 in all_state1:
  10.     for state2 in all_state2:
  11.         for ...
  12.             dp[state1][state2][...] = 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
  
• 贪心：定义比较规则
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！