经常有面试问题是二维网格问题，比如迷宫问题、迷宫最短路径问题、N皇后问题等等。求解时主要有以下要素：

• 遍历：对每个格子（位置）进行遍历。
• 搜索相邻的格子。

总体的搜索可以有深度优先（DFS）和广度优先（BFS）之分。

根据我自己的经验，在有限的时间内解答这类问题时，要注意以下几点：

二维数组的行列顺序

二维数组是按照先行后列的顺序存储的：

void func(int[][] data) {
    if (data == null || data.length = 0 || data[0].length == 0) {
        // ...
        return;
    }

    int rows = data.length;
    int cols = data[0].length;

    for (int r = 0; i < rows; ++r) {
        // 或者更好的写法是：c < data[r].length
        // 但这类问题一般都是个矩形区域，因此把cols提前定好，代码更简洁
        for (int c = 0; c < cols; ++c) {
            data[r][c] = 0;
        }
    }

    // ...
}

循环变量名称

循环变量名称似乎根本不是个问题，一般会用i和j来表示。但在有限时间而且缺乏IDE帮助debug的情况下，对于二维格子问题，很容易引起思维混乱。我自己就有一次在线测试时，因为把行和列弄颠倒了，导致时间到了还无法把程序调通。后来自己“复盘”的时候，才发现原因所在。

因此，建议把变量名称弄得一看就懂：

• 行数和列数：rows，cols
• 表示行和列的循环变量名：r，c

例如：

for (int r = 0; r < rows; ++r) {
    for (int c = 0; c < cols; ++c) {
        data[r][c] = 0;
    }
}

搜索相邻的格子

一般我会按东西南北四个方向编写：

// N
if (r > 0) {
    backtrack(r - 1, c);
}

// S
if (r < rows - 1) {
    backtrack(r + 1, c);
}

// W
if (c > 0) {
    backtrack(r, c - 1);
}

// E
if (c < cols - 1) {
    backtrack(r, c + 1);
}

这样看似很有效率，但很啰嗦，而且在情急之下容易犯错。我经常会因为拷贝粘贴的代码中没改完全而导致程序不能通过，而之后要用肉眼去观察一遍来找出错误的话，很费时间。因此，在效率没有多少区别的情况下，程序越简短越好。

//                                        N   S   W   E
private static final int[] rowOffsets = {-1,  1,  0,  0};
private static final int[] colOffsets = { 0,  0, -1,  1};

private void backtrack(int[][] data, int[][] visited, int r, int c) {
    // ...

    int rows = data.length;
    int cols = data[0].length;
    BiPredicate<Integer, Integer> isValid = (row, col) ->
            row >= 0 && row < rows && col >= 0 && col < cols;

    // 尝试搜索相邻的格子
    for (int i = 0; i < rowOffsets.length; ++i) {
        int r1 = r + rowOffset[i];
        int c1 = c + colOffset[i];

        if (isValid.test(r1, c1) && !visited[r1][c1]) {
            backtrack(data, visited, r1, c1);
        }
    }

    // ...
}

有人喜欢在枚举相邻格子时，按东南西北的顺序转一圈。在我看来似乎没什么必要。最重要的是简单且不易弄错，所以我都是选择按北、南、东、西的顺序轮转。当然，每个人习惯不同，可以选择自己最舒适的顺序。

总结：对于编程来说，最好是从一开始就不要把bug放进去，否则要找出来就需要花费成倍的时间。因此，要选择各种一看就懂的方式写代码，防止写到中间自己都迷糊了。另外，为了避免查找bug的时间过长，应该尽量写简短的代码（当然不是那种为了短而短的十分缺乏可读性的那种）。

Array & List

// 排序
int[] array = {3, 4, 1, 2, 5};
Arrays.sort(array);    // T = O(n * log2(n))
List<Integer> list = Arrays.asList(array);
Collections.sort(list);  // 使用ArrayList的话，T = O(n * log2(n))
list.sort(null);         // 上面的函数调用这个函数，其内部实现方法是先把列表转换为数组再排序
                         // 因为如果是链表，直接排序的时间复杂度为O((n ^ 2) * log2(n))。

// array和list转换
List<String> list = Arrays.asList(array);
String[] array = list.toArray(new String[0]);

// max & min
Map<String, Integer> map = ...;
// 找出具有最大value值的key
String max = Collections.max(
        map.entrySet(),
        Comparator.comparingInt(Map.Entry<String, Integer>::getValue)).getKey();
// 或者
max = Collections.max(
        map.entrySet(),
        Map.Entry.comparingByValue()).getKey();
// 这些其实没什么必要，面试时记不住就用循环解决

// string
String str = "aaa bbb ccc";
String[] parts = str.split(" ");      // {"aaa", "bbb", "ccc"}
String[] parts1 = str.split(" ", 2);  // {"aaa", "bbb ccc"}
String[] parts2 = str.split(" ", -1); // -1的意思是不要删除最后面的空字符

另外，Java的Collection由于只接受对象形式的元素（就是说不能用基本数据类型的元素），加上其维护代码的开销，性能往往比数组差。比如int[]比ArrayList<Integer>要快，尤其是在比拼算法所用时间的情况下尤为明显。

Stack

“Stack”是Java中关于栈的旧API。现在应该使用Deque。LIFO。

Deque<String> stack = new ArrayDeque<>();
stack.push("abc");
String s1 = stack.peek();
String s2 = stack.pop();

Queue

普通的队列，在Java中一般是以LinkedList的方式实现的。Queue常用于广度优先搜索算法。FIFO。

Queue<String> queue = new LinkedList<>();
queue.offer("abc");       // enqueue
String s = queue.poll();  // dequeue

Priority Queue

Priority Queue常被用来在不排序的情况下取最大的或最小的几个值。如果有n个数据元素，要取前k个（k<n）最小的元素，用排序法的话T=O(n * log2(n))，而用Priority Queue的话，则为T=O(n * log2(k))，这样就能快一些。方法是往queue里逐个放入数据元素，如果queue的长度大于k，则把一个元素移出（也就是最大的那个或最小的那个，取决于Priority Queue的设定方式。这样，剩下的就是k个最小的或最大的元素。

Priority Queue的时间复杂度：enqueue和dequeue操作为O(log2(k))，查看（peek）最前面的元素为O(1)。

PriorityQueue<Elem> queue = new PriorityQueue<>(Comparator.comparingInt(Elem::getValue)); 

for (Elem elem : list) {
    queue.offer(elem);
    if (queue.size() > k) {
        queue.poll();
    }
}

上面的代码中的queue.poll()会把Elem.getValue()返回值最小的元素移出。要想移出最大的，则改为Comparator.comparingInt(elem -> -elem.getValue())。

另一个应用的例子：合并k个有序列表。一般的算法为取各列表的第一个元素，找到最小的那个，加入新列表，然后把最小元素的下一个元素作为它原所属列表的第一个元素。不断重复，直到用完所有列表的元素。这样做的话，T=O(N * k)，其中N为所有列表中的元素总数，k为列表个数。因为每次从k各元素中取最小值为O(k)，而对所有元素都要进行一次这样的操作，故为O(N * k)。

可以用Priority Queue进行优化：把各列表的第一个元素加入queue；取出最前面的元素加入新列表，并把它的下一个元素加入queue。这样的话，每次enqueue和dequeue操作为O(log2(k))，对所有元素做这种操作，总体的时间复杂度T=O(N * log2(k))，比上述的O(N * k)要快。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }

    if (lists.length == 1) {
        return lists[0];
    }

    PriorityQueue queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));

    for (ListNode node : lists) {
        if (node == null) {
            continue;
        }

        queue.offer(node);
    }

    ListNode dummyHead = new ListNode(0);
    ListNode prev = dummyHead;

    while (!queue.isEmpty()) {
        ListNode node = queue.poll();

        prev.next = node;
        prev = node;

        if (node.next != null) {
            queue.offer(node.next);
            node.next = null;
        }
    }

    return dummyHead.next;
}

题外话：另一种十分简单的解法是Divide & Conquer：合并两个有序列表（按第一种思路）的时间复杂度是O(n)，n是两个列表中的元素总和。可以把k个列表两两分组，并将其合并成一组更长的列表；然后继续两两分组合并，直到最后只剩一个列表为止。这看起来跟体育比赛分组类似，没什么特别的，但观察一下的话，一共有log2(k)轮的分组，每轮都要遍历所有N个元素，因此，时间复杂度也是O(N * log2(k))。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }

    if (lists.length == 1) {
        return lists[0];
    }

    int i = 0;
    List mergedList = new ArrayList<>();

    // 两两分组合并。merge2()的作用是普通的合并两个有序列表。
    while (i < lists.length) {
        ListNode node1 = lists[i];

        if (++i < lists.length) {
            mergedList.add(merge2(node1, lists[i++]));
        } else {
            mergedList.add(node1);
        }
    }

    return mergeKLists(mergedList.toArray(new ListNode[0]));
}

Map

HashMap经常用来提高程序的效率。写入（put）、查找（contains）和取值（get）都为O(1)。这里有一些简单写法：

// 计数：记录相同词语出现的次数
Map<String, Integer> map = new HashMap<>();

for (String s : list) {
    map.merge(s, 1, Integer::sum); // 如果没有，值设为1；否则，在原来的基础上加1
}

// map的值为一个列表。如果不存在，创建列表。
// key为字符串，value为储存字符串索引位置的列表
Map<String, List<Integer>> map = new HashMap<>();

for (int i = 0; i < list.size(); ++i) {
    map.computeIfAbsent(list.get(i), k -> new ArrayList<>()).add(i);
}

Bitwise & Bit Shift Operations

// Unary bitwise complement (~)
int n = ~5;  // ~0101 --> 1010

// Bitwise AND (&)
int m = 0b0001;
int result = n & m;   // 1010 -> 0000
// Bitwise inclusive OR (|)
result = n | m;   // 1011

// Bitwise exclusive OR (XOR) (^)
result = n ^ 0b1111;   // 1010 --> 0101

// Signed left shift (<<): shift once results integer x 2
result = 8 << 1;  // 16
result = -8 << 1; // -16

// Signed right shift (>>): shift to right and fill 0 on left, but keep leftmost bit.
// shift once results integer / 2
result = 8 >> 1;  // 4
result = -8 >> 1; // -4 

// Unsigned right shift (>>>): shift to right and fill 0 on left.
result = 8 >>> 1;  // 4
result = -8 >>> 1; // 2147483644

一些常用的用法：

// 乘或除2的n次方
int result = 3 << 4;  // 3 * (2 ^ 4)
result = 32 >> 3;     // 32 / (2 ^ 3)

// 判断奇偶
boolean isEven = (123 & 1) == 0;  // 注意由于优先级的原因，应使用括号

// 判断某位是否为1（比如每个位表示一种flag）
int mask = 0b0010;
boolean isSecondBitFromRightSet = (7 & mask) == mask;  // 7 = 0b0111, 7 & mask = 0b0010

// XOR:
// a XOR a = 0
// a XOR 0 = a
// a XOR b XOR c = a XOR (b XOR c)
// a XOR b XOR b = a

Trie

Trie又名“前缀树”，用于根据前缀查找词汇。典型的应用包括：自动完成、拼写检查、IP路由、解字谜等等。哈希表虽说查找的时间复杂度为O(1)，但在查找相同前缀的词汇时就缺乏效率了。而且如果输入了大量的词汇的话，还有因哈希冲突而导致的效率下降。

如果输入的词汇数量为n，查找的前缀长度为m，那么查找的时间复杂度为O(m)。

这里是一个简单的实现：

public class Trie {
    public static class Node {
        private String word;
        private final Map<Character, Node> childrenMap = new HashMap<>();

        public Node() {
            // empty
        }

        public boolean hasChild(char c) {
            return childrenMap.containsKey(c);
        }

        public Node getChild(char c) {
            return childrenMap.get(c);
        }

        public Node addChild(char c) {
            return childrenMap.computeIfAbsent(c, k -> new Node());
        }

        public void setWord(String str) {
            this.word = str;
        }

        public String getWord() {
            return word;
        }
    }

    private final Node root = new Node();

    public Trie() {
        // empty
    }

    // 输入一个词汇
    public void insert(String word) {
        Node node = root;

        for (char c : word.toCharArray()) {
            node = node.addChild(c);
        }

        node.setWord(word);
    }

    // 查看是否有该词汇
    public boolean search(String word) {
        Node node = root;

        for (char c : word.toCharArray()) {
            node = node.getChild(c);

            if (node == null) {
                return false;
            }
        }

        return node.getWord() != null;
    }

    // 查看是否有以该前缀开始的词汇
    public boolean startsWith(String prefix) {
        Node node = root;

        for (char c : prefix.toCharArray()) {
            node = node.getChild(c);

            if (node == null) {
                return false;
            }
        }

        return true;
    }
}

如果词汇的组成字符是有限的（比如小写英文单词由26个字母组成），另一种实现方法是用一个数组代替Trie.Node中的HashMap。我个人不太喜欢这种方法。但是用Java语言的时候，讽刺的是这种方法往往能快一点点。

public static class Node {
    private static final int N = 26;    // 字符总数
    private Node[] links = new Node[N]; // 查找时用索引 int i = c - 'a';

    // 用flag代替上面的字符串能节省点空间。
    // 用字符串的目的是在需要得到词汇时不用从头遍历到目前结点，而是能直接拿到
    private boolean end = false;

    // ...

    private int getIndex(char c) {
        return c - 'a';
    }

    public boolean contains(char c) {
        return get(c) != null;
    }

    public Node get(char c) {
        return links[getIndex(c)];
    }

    // ...
}

深度优先遍历（DFS）和广度优先遍历（BFS）是两种遍历或搜索树和图的方法，常用于，呃，面试中……

深度优先遍历（DFS：Depth First Search）

DFS的遍历顺序又分为三种。下面以N代表当前结点，L代表左侧子结点，R代表右侧子结点。

• 先序（preorder）：先处理当前结点，然后对子结点从左向右处理。NLR，从上向下，从左向右
• 中序（inorder）：先处理左侧子结点，然后处理当前结点，最后处理右侧子结点。LNR，左–>当前–>右
• 后序（postorder）：先从左向右处理子结点，然后处理当前结点。LRN，从下向上，从左向右

如果把表达式放入二叉树，那么先序遍历的结果是前缀表示法（波兰表示法，Polish Notation），中序遍历的结果是中缀表示法，后序遍历的结果是后缀表示法（逆波兰表示法，Reverse Polish Notation）。

DFS的特点天然地适合使用递归的方法实现。三种顺序仅仅通过改变处理程序片段的位置就能实现，十分简单易行。用循环来实现的话，就得自己维护一个栈，而且实现起来也比较麻烦。

private void dfsInorder(Node node) {
    if (node == null) {
       return;
    }

    // 处理左子结点
    if (node.left != null) {
        dfsInorder(node.left);
    }

    // 处理本结点
    handle(node);

    // 处理右子结点
    if (ndoe.right != null) {
        dfsInorder(node.right);
    }
}

private void dfsPreorder(Node node) {
    if (node == null) {
       return;
    }

    // 处理本结点
    handle(node);

    // 处理子结点
    if (node.left != null) {
        dfsPreorder(node.left);
    }

    if (ndoe.right != null) {
        dfsPreorder(node.right);
    }
}

private void dfsPostorder(Node node) {
    if (node == null) {
       return;
    }

    // 处理子结点
    if (node.left != null) {
        dfsPostorder(node.left);
    }

    if (ndoe.right != null) {
        dfsPostorder(node.right);
    }

    // 处理本结点
    handle(node);
}

循环的方法：估计面试时不会要求做这个吧？其中，前序比较容易，而中序比较难，后序本来更难，但鉴于它与先序的对称性，可以把结果按先序（但是改为从右向左）压入栈中，再反向逐个弹出即可。

public void dfsPreorder(Node root) {
    if (root == null) {
        return;
    }

    Deque<Node> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        handle(node);

        if (node.right!= null) {
            stack.push(node.right);
        }

        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

public void dfsInorder(Node root) {
    if (root == null) {
        return;
    }

    Deque<Node> stack = new ArrayDeque<>();
    Node node = root;

    while (node != null || !stack.isEmpty()) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            handle(node);
            node = node.right;
        }
    }
}

public void dfsPostorder(Node root) {
    if (root == null) {
        return;
    }

    Deque<Node> stack = new ArrayDeque<>();
    Deque<Node> reversedStack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        reversedStack.push(node);

        if (node.left != null) {
            stack.push(node.left);
        }

        if (node.right != null) {
            stack.push(node.right);
        }
    }

    while (!reversedStack.isEmpty()) {
        handle(reversedStack.pop());
    }
}

广度优先遍历（BFS：Breadth First Search）

BFS的访问顺序一般是从左向右，从上向下，一层一层地处理。一般用循环通过某种容器（queue、stack、set等）来实现。

public void bfs(Node root) {
    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        handle(node);

        if (node.left != null) {
            queue.offer(node.left);
        }

        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

有时候在做BFS时，需要在处理完每一层后，都做一些其他的处理。这种情况下，可以在while循环中再套一个循环来实现：

public void bfsPerLevel(Node root) {
    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    int count = 0;

    while (!queue.isEmpty()) {
        int n = queue.size();

        for (int i = 0; i < n; ++i) {
            Node node = queue.poll();
            handle(node);

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        // 此处加入处理完当前层后的代码
        log.info(">>> end of level {}", count++);
    }
}

一般来说，递归跟栈相关，所以对于DFS这种递归属性的算法，可以在循环中用栈来实现。而对于BFS这种跟栈没关系的算法，一般人就会认为不能用递归实现。但实际上还是有办法做到的：

private void recursiveBfsHelper(List<Node> nodeList) {
    if (nodeList.isEmpty()) {
        return;
    }

    List<Node> nextList = new ArrayList<>();

    for (Node node : nodeList) {
        handle(node);

        if (node.left != null) {
            nextList.add(node.left);
        }

        if (node.right != null) {
            nextList.add(node.right);
        }
    }

    recursiveBfsHelper(nextList);
}

public void recursiveBfs(Node root) {
    recursiveBfsHelper(Collections.singletonList(root));
}

DFS算法实现起来简短方便（用递归的话），因此十分适合在面试中使用。但有些问题则需要用到BFS，比如求迷宫最短路径问题（因为逐层扫描直到找到解为止，这个解一定是最优解（或最优解之一），这里的最优解是路径最短的意思。

例题：二叉树的序列化和反序列化

将二叉树序列化为一个字符串，并将字符串反序列化为二叉树。

• 需要产生压缩的结果，否则对于只有右子树的二叉树，结果会过长。
• 由于上述要求，用DFS比较恰当，因为产生的结果便于反序列化。

    // 序列化

    // DFS preorder
    private void dfs(TreeNode root, StringBuilder sb) {
        sb.append(",");

        if (root != null) {
            sb.append(root.val);
            dfs(root.left, sb);
            dfs(root.right, sb);
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }

        StringBuilder sb = new StringBuilder(root.val);
        dfs(root.left, sb);
        dfs(root.right, sb);

        return sb.toString();
    }

    // 反序列化

    private TreeNode dfs(Queue<String> queue) {
        TreeNode root = null;

        if (!queue.isEmpty()) {
            String s = queue.poll();

            if (!s.equals("")) {
                root = new TreeNode(Integer.parseInt(s));
                root.left = dfs(queue);
                root.right = dfs(queue);
            }
        }

        return root;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }

        Queue<String> queue = Arrays.stream(data.split(",", -1)
                .collect(Collectors.toCollection(LinkedList::new));

        return dfs(queue);
    }