49.

需要处理数组中的重复值另外需要提前判断目标字母target是否比字符数组letters中最大的字母letters[letters.length

1]还要大如果是则按照题目要求直接返回letters的第一个字符否则才进行二分查找。

在找到与target相同的字符时不急于返回这个字符而是继续缩小查询区间。

左子区间

查询最后的右指针right就指向小于target的元素如果要找

右子区间

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

class

循环结束后left指向letters中第一个大于target的元素return

letters[left];}

是由重新排列源单词的所有字母得到的一个新单词。

所以字母异位词不关心字符的顺序只关心

ListString。

这里的Cnt是自己实现的数据类型它内部存储着字符的出现次数并重写了equals

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

class

获取cnt对应的字符串链表如果没有则创建一个新链表ListString

list

ArrayList(map.values());}private

static

图的拓扑排序入度越小越靠前。

在排序之前先将所有入度为0的节点加入

队列然后将队列中的节点移出队列并把节点所指向的节点的入度减一当某个节点的入度被减到0时将它加入队列重复这样的操作直到队列为空。

如果需要返回拓扑排序的结果则在将节点移出队列时将其加入到结果链表中即可。

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

图实际上就是一堆边和一堆节点的集合不过本题解不使用这样的集合而是将图理解为一堆节点连接的一堆节点即为ListListInteger结构外层的List包含了所有的节点内层的List包含的这个节点指向的所有节点。

在构建图时获取图中的每条边将边的终点加入

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

现在的问题就只剩下如何寻找边了题目中提到prerequisites[i]

[a,

b这句话说明prerequisites[i]数组为图中的一条边第一个元素为

终点第二个元素为

寻找入度为0的节点初始化队列LinkedListInteger

queue

将节点移出队列获取始点在graph中的索引ListInteger

toList