二分查找

链表

反转链表

动态规划问题

例题1： 剪绳子

例题：

结论： 将总数拆分成尽可能多的3，和剩余的2，而且最后最多只有两个2。

原因：

例题2：正则表达式匹配

思路：

将情况一分为二，并写出两种情况下的状态转移。注意i和j的边界情况。

一些特殊的题目

链表中环的入口结点

1. 快慢指针
2. map

复杂链表的复刻

1. map，缺点是O(n)空间复杂度
2. 另一种方法就不需要额外的空间，代价是多遍历两次这个链表

思路就是，第一次遍历给每个节点后面加一个复制。第二次遍历给每个复制节点的random赋值。第三次遍历，把复制从这个链表中抽出来，同时还原原链表

找数组中重复出现的数字

如果数组元素大小 0< x < n-1，只要找到任一重复的元素

这个时候我们可以采用比较巧的方式，遍历这个数组，当前元素是Arr[n]，就看是否Arr[n] === Arr[Arr[n]] 如果是，那么就重复了。如果不是那么就将这两个位置的数调换。

如果是不修改数组找出重复的数字，就是利用二分查找。

找出重复k/n次的元素

遍历一次，需要使用辅助空间。对每个遍历元素存入一个map中计数出现的次数。然后再用另一个map记录已经重复这么k/n次的元素，如果已经重复这么多次就直接continue。

找出重复超过n/2次的元素

遍历一次，每次遍历维护一个当前值变量，以及当前能量变量，如果当前遍历元素和当前变量相同那么当前能量+1，如果当前能量<0。那么就直接换人，换成当前遍历元素。遍历完毕之后当前值变量就是超过n/2次的元素。这个思路像炉石传说的水晶一样。

怎么判断图中是否有环

二叉树

二叉树的遍历

前序遍历

function mid(node) {
  if (!node) return;
  console.log(node.val);
  mid(node.left);
  mid(node.right);
}

中序遍历

递归做法：

function mid(node) {
  if (!node) return;
  mid(node.left);
  console.log(node.val);
  mid(node.right);
}

后序遍历

function mid(node) {
  if (!node) return;
  mid(node.left);
  mid(node.right);
  console.log(node.val);
}

二叉树的下一个节点

找中序遍历的下一个节点。
分类讨论情况，如果有右子树，就沿左边一直往下找，找到没有为止就是下一个节点。
如果没有右子树，就往上找，知道找的途中，当前节点是父亲节点的左子节点，那么这个父亲节点就是下一个节点

重建二叉树

根据前序遍历和中序遍历去递归构建子树，最尾递归到叶子节点，然后回溯得到整棵二叉树。

二叉搜索树

二叉搜索树是什么？二叉搜索树的中序遍历就是单调递增的序列。细化到每个节点上来说就是左子节点小于父节点，右子节点大于父节点。