分类目录:

二维网格问题的解法

经常有面试问题是二维网格问题,比如迷宫问题、迷宫最短路径问题、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的时间过长,应该尽量写简短的代码(当然不是那种为了短而短的十分缺乏可读性的那种)。

用于算法题的常用Java工具

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);
    }

回溯算法

回溯算法是一种可以找到全部或部分解的通用算法。跟暴力穷举法相比,由于可以对搜索域剪枝,因此效率要高。所谓回溯,就是走到某处后如果发现此路不通,会立即退回到上一步,而不是像暴力法那样仍不管不顾地都试一次。因此,回溯法是一种选优搜索法,又称为试探法。

回溯算法的编写格式:

boolean backtrack(candidate) {
    // 递归终止条件
    if (isSolution(candidate)) {
        output(solution);
        return true;
    }

    // 标记当前结点(比如把当前结点标记在路径里)
    place(candidate);

    // 遍历和尝试所有下一级的结点
    for (nextCandidate : listOfCandidates) {
        // 剪枝:对于不合适的结点,直接跳过
        if (isValid(nextCandidate)) {
            // 继续深入到下一层。如果最终能找到解,返回;否则尝试下一个下级结点
            if (backtrack(nextCandidate)) {
                return true;
            }
        }
    }

    // 清除当前结点的标记(比如把当前结点从路径上移除,这意味着从其他结点还能继续来这里)
    remove(candidate);
    return false;
}

说明:

  • backtrack函数是一个调用自己的递归函数,所以要有终止递归的条件
  • 里面有一个循环,用于尝试所有下一级的结点。比如迷宫问题,当走到了某点后,继续尝试相邻的三个结点(前一个结点除外)。循环里应该有剪枝,避免不必要的递归调用开销。
  • 经常需要标记当前结点,并在尝试完从这里开始的所有可能性后清除标记。(比如,不要重复访问已标记的地方)

例题:N皇后问题(八皇后问题)

暴力穷举法:把第一个皇后放置在第一行的每个位置,然后搜索所有的解(尝试把第二个皇后放在其他所有位置,再尝试把第三个皇后放在其他所有位置……)。其实这已经不太“暴力”了,因为完全的“暴力搜索”应该是把第一个皇后也放在棋盘的所有位置,最后再去掉重复的解。

回溯法:把第一个皇后放在第一行的每个位置,由于第一行肯定不能再放置皇后,因此,尝试把第二个皇后放在第二行的每个位置,判断一下是否满足条件,把不满足条件的跳过,然后再在第三行尝试放置第三个皇后……

进一步优化:保存一个长度为N的数组,在某一列放置过皇后的话,就把相应的数组位置设置为true。这样,在下一行放置下一个皇后时,先跳过所有置为true的各列,然后再判断某位置是否符合条件(因为还有斜向的攻击)。在退出前从数组中把其列标志清除。

总结:女人真可怕……我本人的话,性格应该跟“车”比较相似。