LeetCode 744, 49, 207

744. 寻找比目标字母大的最小字母

题目链接

744. 寻找比目标字母大的最小字母

思路

本题比 基础二分查找 难的一点是 需要处理数组中的重复值，另外需要提前判断目标字母target是否比字符数组letters中最大的字母letters[letters.length - 1]还要大，如果是，则按照题目要求直接返回letters的第一个字符；否则才进行二分查找。

如何处理重复值？可以 在找到与target相同的字符时，不急于返回这个字符，而是继续缩小查询区间。

而缩小查询区间的策略与题目的要求有关，如果要找 小于target的字符，则下一轮在 左子区间 查询，最后的右指针right就指向小于target的元素；如果要找 大于target的字符，则下一轮在 右子区间 查询，最后的左指针left就指向大于target的元素。

例如对于在letters = ['a', 'a', 'b', 'b', 'c', 'c']中查找大于target = 'b'的字符，有如下的二分查找流程：

开始left = 0, right = 5, mid = 2，发现target == letters[mid]，于是下一轮查询右子区间；
此时left = 3, right = 5, mid = 4，发现target < letters[mid]，于是下一轮查询左子区间；
此时left = 3, right = 3, mid = 3，发现target == letters[mid]，于是下一轮查询右子区间；
此时left = 4, right = 3，有left > right，退出查找。

最后left为4，而letters[left]为'c'，这正是要求查找的字符。

代码

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length - 1;
        if (target >= letters[right]) { // 如果letters中没有比target大的字符
            return letters[0]; // 则返回letters的第一个字符
        }
        while (left <= right) {
            int mid = left + (right - left >> 1);
            if (target < letters[mid]) { // 若target小于mid指向的元素
                right = mid - 1; // 则下一轮查找左子区间
            } else if (target > letters[mid]) { // 若target大于mid指向的元素
                left = mid + 1; // 则下一轮查找右子区间
            } else { // 由于不确定mid是否为 最后一个等于target的字符
                left = mid + 1; // 所以下一轮查找右子区间，而不是急于返回
            }
        }
        // 循环结束后left指向letters中第一个大于target的元素
        return letters[left];
    }
}

49. 字母异位词分组

题目链接

49. 字母异位词分组

思路

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。所以字母异位词不关心字符的顺序，只关心 字符的出现次数。

所以可以 将字符串中的字符出现次数作为字符串的键，将这个字符串存储到这个键对应的字符串链表中，即有如此结构Map<Cnt, List<String>>。这里的Cnt是自己实现的数据类型，它内部存储着字符的出现次数，并重写了equals & hashCode方法，可以作为HashMap的键。

将字符串根据不同的字符出现此时分配完之后，将Map的values()作为构建ArrayList的参数，构建一个List<List<String>>，并将其返回。

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<Cnt, List<String>> map = new HashMap<>();
        for (String str : strs) {
            Cnt cnt = new Cnt(str); // 获取这个字符串的字符出现次数
            // 获取cnt对应的字符串链表，如果没有，则创建一个新链表
            List<String> list = map.computeIfAbsent(cnt, k -> new ArrayList<>());
            list.add(str); // 将这个字符串放入cnt对应的字符串链表中
        }
        // 由map的多个 字符串链表List<String> 构建一个 List<List<String>> 并返回
        return new ArrayList<>(map.values());
    }
    private static class Cnt { // 统计字符串的字符出现次数
        private int[] key = new int[26];
        public Cnt(String str) { // 计算字符串str的字符出现次数 并保存
            for (int i = 0; i < str.length(); i++) {
                key[str.charAt(i) - 'a']++;
            }
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Cnt cnt = (Cnt) o;
            return Arrays.equals(key, cnt.key);
        }
        @Override
        public int hashCode() { // 以统计数组key作为本对象生成的hashCode
            return Arrays.hashCode(key);
        }
    }
}

207. 课程表

题目链接

207. 课程表

思路

要做本题需要对图论有一定的了解：

节点：图中的一个点。
边：连通一个点到另一个点。对于 有向图 来说，指向别的节点的节点称为始点，被指向的节点称为终点。
入度：对于一个节点来说，它的入度就是它作为终点的次数。

有向图

例如对于上面这个有向图，有以下的结论：

节点1的入度为0
节点2的入度为1
节点3的入度为1
节点4的入度为1
节点5的入度为1
节点6的入度为1
节点7的入度为1
节点8的入度为1
节点9的入度为1
节点10的入度为4
节点11的入度为1

本题很像 图的拓扑排序：入度越小，越靠前。在排序之前，先将所有入度为0的节点加入队列，然后将队列中的节点移出队列，并把节点所指向的节点的入度减一，当某个节点的入度被减到0时，将它加入队列，重复这样的操作，直到队列为空。如果需要返回拓扑排序的结果，则在将节点移出队列时将其加入到结果链表中即可。

回到本题上，要使用拓扑排序得先构建图，并获取图中每个节点的入度，然后才能进行拓扑排序，在拓扑排序的时候记录移出队列的节点数，如果最终这个数字与图中的节点数不一致，则返回false，否则返回true。

图实际上就是一堆边和一堆节点的集合，不过本题解不使用这样的集合，而是将图理解为一堆节点连接的一堆节点，即为List<List<Integer>>结构，外层的List包含了所有的节点，内层的List包含的这个节点指向的所有节点。在构建图时，获取图中的每条边，将边的终点加入 边的始点所指向的节点集合 中。

获取图中每个节点的入度很简单，只需要在构建图时，对于每条边，将终点的入度加一即可。

现在的问题就只剩下如何寻找边了，题目中提到prerequisites[i] = [a, b] 表示如果要学习课程 a 则必须先学习课程 b，这句话说明prerequisites[i]数组为图中的一条边，第一个元素为终点，第二个元素为始点。

代码

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 初始化存储图的数据结构
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // 统计每个节点的入度，并构建图
        int[] inDegree = new int[numCourses]; // 存储每个节点的入度
        for (int[] pair : prerequisites) {
            int start = pair[1]; // 始点
            int end = pair[0]; // 终点
            List<Integer> toList = graph.get(start); // 获取 始点的 指向节点集合
            toList.add(end); // 将 终点 加入 始点的 指向节点集合 中
            inDegree[end]++; // 让终点的入度加一
        }

        // 寻找入度为0的节点，初始化队列
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) { // 如果索引为i的节点的入度为0
                queue.offer(i); // 则将索引i放入队列
            }
        }

        // 拓扑排序
        int cnt = 0; // 统计移出队列的节点
        while (!queue.isEmpty()) { // 直到队列为空才退出循环
            cnt++;
            int start = queue.poll(); // 将节点移出队列，获取始点在graph中的索引
            List<Integer> toList = graph.get(start); // 获取始点指向的所有终点的索引
            for (int end : toList) { // 将始点指向的所有终点的入度减一
                if (--inDegree[end] == 0) { // 当终点的入度减到0时
                    queue.offer(end); // 将其加入队列
                }
            }
        }
        
        return cnt == numCourses; // 返回移出队列的节点数 是否等于 节点总数
    }
}