总结一下面试常见算法，记住，做算法的时候要先想清楚思路，写代码的时候要慢慢写，每写一行都要确认逻辑是否正确。最后如果代码出问题了，请使用调试工具来调试

图

图，静态连通性问题，都可以使用 DFS 或者 BFS 或者并查集解决

在处理图的问题的时候一定要记录一个对应的 bool 数组，bool 数组是用来判断是否要进行下一次搜索逻辑的，是用来记录本次已经搜索过的记录的

岛屿数量 (opens new window) 课程表 (opens new window)

栈

栈的题目在算法遍历完毕之后，栈内的数据一般就是答案，同时算法在执行的过程中生产的数据一般也在栈中记录

简化路径 (opens new window) 逆波兰表达式求值 (opens new window)

当然，有一些一看就是栈做的题目，可能最后不是用栈做，需要注意：

最长回文子串 (opens new window)

哈希表

hash 表相关的题目一般配合其他算法一起使用，纯 hash 的题目比较简单，如下：

存在重复元素 II (opens new window) 字母异位词分组 (opens new window)

下面这题如果想用 O(n) 的时间复杂度处理，则需要使用 hash 表了

最长连续序列 (opens new window)

排序&区间

排序算法时空复杂度

排序方法	时间复杂度	空间复杂度
冒排、插排、选排	n^2	1
快排	nlogn	logn
二分	nlogn	n
堆排	nlogn	1

一些区间题目可能会使用到排序，比如：

最小数量的箭引爆气球 (opens new window) 插入区间(这题如果给的不是一个有序的区间，需要先排序) (opens new window)

这类题目的共性是找一个最大重叠区间

下面这个小技巧在很多题目中应该都用到了，java 中关于二维数组排序方法：Arrays.sort(meetings, Comparator.comparingInt(x -> x[0]));

动态规划

这位更是重量级，难点是看状态转移方程，思路为想如果现在拼到了最后一步，上一步是谁 需要枚举每一种情况时使用，并且每一种情况对后续考虑有帮助时使用

跳跃游戏 II (opens new window) 环形子数组的最大和 (opens new window)

比一维动态规划更逆天的是二维动态规划：

交错字符串 (opens new window) 最小路径和(这题比较简单一些，因为可以很清楚的看出动态转移方程) (opens new window) 买卖股票的最佳时机 IV (opens new window)

分发糖果，接雨水

属于数组的难题，如果你能想到左右各遍历一次，记录每个位置的左边最大值和右边最大值，这种题目就不难了

具体解法是左右各遍历一次，记录每个位置的左边最大值和右边最大值方便为 A 和 B，然后遍历数组中每个元素时，取 A、B 中较小的那个，减去当前高度，就是当前位置的接水量

分发糖果 (opens new window) 接雨水 (opens new window)

双指针

应用面较广，作为暴力遍历剪枝后的算法，有着不错的性能

盛最多水的容器（移动较小的边） (opens new window) 三数之和（排序后，将一个数定死，其他两个数用双指针处理） (opens new window)

滑动窗口

双指针进阶版，记得用 for+while 的格式写代码

无重复字符的最长子串 (opens new window)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

二叉树

要么是递归，要么是层序遍历，都挺简单的

关于递归：

从前序与中序遍历序列构造二叉树 (opens new window) 二叉树中的最大路径和 (opens new window)

关于层序遍历：

二叉树的层序遍历 (opens new window) 二叉树的锯齿形层序遍历 (opens new window)

回溯

回溯就是递归

全排列 (opens new window) N 皇后 II (opens new window)

分治

分治也是递归，注意，迭代左右边数据的时候，需要加一减一

排序链表 (opens new window) 将有序数组转换为二叉搜索树 (opens new window)

链表

重点就是你需要用很多指针，记录 start、end、pre、cur、next 等节点。一个很经典的题目就是反转链表，至少这题的代码需要背下来

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

这题的衍生题目有很多：

反转链表 II (opens new window) K 个一组翻转链表 (opens new window)

模拟

一点含金量没有的题目，纯恶心人，下面都是模拟相关提供

关于矩阵的题目，一般就是找矩阵的哪个点移动到哪个点：

旋转图像 (opens new window) 螺旋矩阵 (opens new window)

下面这个字符串相关题目也是模拟相关的题目：

Z 字形变换 (opens new window)

其他

记录一些奇奇怪怪的算法：

投票法找众数，遇到众数加一，没遇到减一

多数元素 (opens new window)

位运算，考验异或操作 ^ 按位与 & 按位或 |。比如下面这题，只出现一次的数字 II，答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数 只出现一次的数字 II (opens new window)