找一个网站做优化分析,怎么把网站做的好看,wordpress如何批量发布文章,微信开放平台是干什么的目录 744. 寻找比目标字母大的最小字母题目链接标签思路代码 49. 字母异位词分组题目链接标签思路代码 207. 课程表题目链接标签思路代码 744. 寻找比目标字母大的最小字母
题目链接
744. 寻找比目标字母大的最小字母
标签
数组 二分查找
思路
本题比 基础二分查找 难的一… 目录 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. 字母异位词分组
标签
数组 哈希表 字符串 排序
思路
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。所以字母异位词不关心字符的顺序只关心 字符的出现次数。
所以可以 将字符串中的字符出现次数作为字符串的键将这个字符串存储到 这个键对应的字符串链表中即有如此结构MapCnt, ListString。这里的Cnt是自己实现的数据类型它内部存储着字符的出现次数并重写了equals hashCode方法可以作为HashMap的键。
将字符串根据不同的字符出现此时分配完之后将Map的values()作为构建ArrayList的参数构建一个ListListString并将其返回。
代码
class Solution {public ListListString groupAnagrams(String[] strs) {MapCnt, ListString map new HashMap();for (String str : strs) {Cnt cnt new Cnt(str); // 获取这个字符串的字符出现次数// 获取cnt对应的字符串链表如果没有则创建一个新链表ListString list map.computeIfAbsent(cnt, k - new ArrayList());list.add(str); // 将这个字符串放入cnt对应的字符串链表中}// 由map的多个 字符串链表ListString 构建一个 ListListString 并返回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。
图实际上就是一堆边和一堆节点的集合不过本题解不使用这样的集合而是将图理解为一堆节点连接的一堆节点即为ListListInteger结构外层的List包含了所有的节点内层的List包含的这个节点指向的所有节点。在构建图时获取图中的每条边将边的终点加入 边的始点所指向的节点集合 中。
获取图中每个节点的入度很简单只需要在构建图时对于每条边将终点的入度加一即可。
现在的问题就只剩下如何寻找边了题目中提到prerequisites[i] [a, b] 表示如果要学习课程 a 则 必须 先学习课程 b这句话说明prerequisites[i]数组为图中的一条边第一个元素为 终点第二个元素为 始点。
代码
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 初始化存储图的数据结构ListListInteger 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]; // 终点ListInteger toList graph.get(start); // 获取 始点的 指向节点集合toList.add(end); // 将 终点 加入 始点的 指向节点集合 中inDegree[end]; // 让终点的入度加一}// 寻找入度为0的节点初始化队列LinkedListInteger 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中的索引ListInteger toList graph.get(start); // 获取始点指向的所有终点的索引for (int end : toList) { // 将始点指向的所有终点的入度减一if (--inDegree[end] 0) { // 当终点的入度减到0时queue.offer(end); // 将其加入队列}}}return cnt numCourses; // 返回移出队列的节点数 是否等于 节点总数}
}
