剑指 Offer II 114. 外星文字典【困难题】【每日一题】
思路：
跟着题解的思路走一遍，写写注释，下次遇到大概率还是不会写~
代码：
class Solution {
Map> edges = new HashMap<>();
Map indegrees = new HashMap<>();
boolean valid = true;
public String alienOrder(String[] words) {
int n = words.length;
//建图
for (String word : words) {
int wordLen = word.length();
for (int i = 0; i < wordLen; i++) {
char c = word.charAt(i);
edges.putIfAbsent(c,new ArrayList<>());
}
}
//完善拓扑图
for (int i = 1; i < n && valid; i++) {
addEdge(words[i-1],words[i]);
}
//如果valid为false 说明相邻单词中存在后面的单词是前面单词的前缀且前面单词长度大于后面单词长度，这种情况不可能存在合法字母顺序，函数直接返回 ""
if (!valid){
return "";
}
//定义queue存放待处理的拓扑节点
Queue queue = new ArrayDeque<>();
//定义letterSet存放所有的拓扑节点
Set letterSet = edges.keySet();
//将letterSet中入度为0的拓扑节点加入queue队列
for (Character u : letterSet) {
if (!indegrees.containsKey(u)){
queue.offer(u);
}
}
//定义可变长字符串 sb 用来存放拓扑排序结果
StringBuilder sb = new StringBuilder();
//对待处理的拓扑节点进行处理
while (!queue.isEmpty()){
//取出待处理拓扑节点 u
char u = queue.poll();
//sb中添加 u
sb.append(u);
//取出节点 u 的邻接节点列表 存入 adjacent
List adjacent = edges.get(u);
//遍历adjacent的所有节点
for (Character v : adjacent) {
//将邻接节点v的入度-1
indegrees.put(v,indegrees.get(v)-1);
//如果v的入度变为0，说明这个v节点前面的所有节点都已经加入拓扑排序 于是节点 v 也可以加入拓扑排序
if (indegrees.get(v) == 0){
queue.offer(v);
}
}
}
//最后，如果拓扑排序的长度等于拓扑图中字母的个数 表示这个拓扑排序是正确的，将其转为字符串后返回；否则说明拓扑图中存在环，此时不存在拓扑排序 返回 ""
return sb.length() == edges.size() ? sb.toString() : "";
}
public void addEdge(String before,String after){
int n1 = before.length(),n2 = after.length();
int n = Math.min(n1,n2);
int index = 0;
while (index < n){
char c1 = before.charAt(index),c2 = after.charAt(index);
//如果c1 ！= c2 在拓扑图中c1对应的列表中添加c2 在入度图中将c2对应的入度+1
if (c1 != c2){
edges.get(c1).add(c2);
indegrees.put(c2,indegrees.getOrDefault(c2,0)+1);
break;
}
index++;
}
//如果 before单词比after单词长度长 且 after是before的前缀(因为index==n)
if (index == n && n1 > n2){
valid = false;
}
}
}
剑指 Offer II 068. 查找插入位置【简单题】
思路：【二分查找】
定义左右指针left和right，当左指针小于等于右指针时，进入while循环。 找出中间指针mid。
如果nums[mid]小于target，说明target在mid右侧插入，此时判断target是否比nums[right]还大，如果是的，那么说明在right右侧插入，函数直接返回right+1，否则就更新左指针为mid+1
如果nums[mid]大于target，说明target在mid左侧插入，此时判断target是否比nums[left]还小，如果是的，那么说明在left左侧插入，函数直接返回left，否则就更新右指针为mid-1
如果nums[mid]等于target，说明我们找到了target在nums中的位置，函数直接返回mid。由于题目要求的特殊性，在while循环中，我们一定可以找到target的位置，或者target的插入位置，即函数必然在while循环中就直接返回结果，因此当while循环外部的函数最终返回体就无关紧要了，返回什么随你心情，不信你可以自己测试。
代码：
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0,right = nums.length-1;
while (left <= right){
int mid = left + (right-left)/2;
if (nums[mid] < target){
if (nums[right] < target){
return right+1;
}
left = mid+1;
}else if (nums[mid] > target){
if (nums[left] > target){
return left;
}
right = mid-1;
}else {
return mid;
}
}
return -1;
}
}
