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']++;}}@Overridepublic 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);}@Overridepublic int hashCode() { // 以统计数组key作为本对象生成的hashCodereturn 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的节点的入度为0queue.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; // 返回移出队列的节点数 是否等于 节点总数}
}