算法类型小记

链表问题

• 翻转、回文、相交、倒数第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函数/数组的定义

• 框架

  # 自顶向下递归的动态规划
  def dp(state1, state2, ...):
      for choose in all_choose:
          result = max(result, dp(state1, state2, ...))
      return result
  
  # 自底向上迭代的动态规划
  dp[0][0][...] = base case
  for state1 in all_state1:
      for state2 in all_state2:
          for ...
              dp[state1][state2][...] = max(state1，state2...)
  

• 最长递增子序列：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度

• 信封俄罗斯套娃问题：先按宽度升序排列，如果宽度一样，则按高度降序排列；然后再在高度序列上找最长递增子序列

实战注意

• 小数偏差：比如 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

• 贪心：定义比较规则