java算法day26

java算法day26

• 207 课程表
• 208 实现Trie(前缀树)

---

207 课程表

这题对应的知识是图论里的拓扑排序的知识。从题意就可以感受出来了。题目说如果要学习某课程，那么就需要先完成某课程。
这里我描述比较复杂的情况：课程与课程之间也有可能是多对一的场景或者是1对多的场景。

对于多对1来说，就是要想学习某一门课，就必须要完成前面的好几门课程。
比如类比这样：

对于一对多来说

那么这样的思想，就和图论里的拓扑排序的思想不谋而合了。拓扑排序是不断的将入度为0的节点删除（对应没有前置节点的课程）。当某课程的前置课程被学完了，那么就相当于此时变成了入度为0的节点，那么这节课可以被学（节点可以被删除）。

总结：
这个课不断的被学习的过程，与拓扑排序的过程一模一样。都是需要入度为0，才能够被删除（课程被学习）。当如果图中存在环，那么就会导致删除到一定状态的时候，图中不存在入度为0的节点，此时不能够再继续删除。那么对应着课程就是不可能被学习完。如果不存在环，就算图不连通也好，也肯定能够删的完。

---

现在可以总结写代码的思路了。
明确核心就是拓扑排序的思想。
1、上来先找图中所有入度为0的节点，然后将节点放入队列当中。（为什么要用队列，其实这里感觉很像层序遍历，因为一开始，你把图想的大一点，肯定存在着很多入度为0的节点，而第一轮肯定想着把所有入度为0的节点全删了，删完之后会暴露出新的一轮入度为0的节点。之后删节点就靠这个队列了）
2、不断的从队列中取出节点，将其邻节点（依赖于它的课程）的入度-1。（这里邻节点关系怎么找，回答是自己写一个邻接表，注意这个邻接表的节点上存的是该课程的后续课程组成的链表）（入度怎么记录？用一个入度数组来记录）。
3、如果-1之后相邻节点的入度变为0，则将其加入队列（也就是-1和判断加入队列是在一轮完成的。不在一轮完成那后续队列中哪来节点）
4、重复这个过程，直到队列为空。

---

具体步骤：
a.构建邻接表和入度数组
b. 将所有入度为0的节点加入队列
c. 当队列不为空时，不断取出节点进行处理：
1.将当前节点的所有相邻节点的入度减1
2.如果相邻节点入度变为0，将其加入队列

d. 检查是否所有节点都被处理过

class Solution {  public boolean canFinish(int numCourses, int[][] prerequisites) {  // 1. 创建图的邻接表，表示每个门课的后续的课。这是为了方便进行后续节点入度-1.//下标就代表了课的编号  List<List<Integer>> graph = new ArrayList<>();  for (int i = 0; i < numCourses; i++) {  graph.add(new ArrayList<>());  }  // 2. 创建入度数组，方便快速定位入度为0的点  int[] inDegree = new int[numCourses];  // 3. 遍历给的点和点之间的关系，构建图的出度和入度。  for (int[] prereq : prerequisites) {  //后续课程int course = prereq[0];//前置课程  int prerequisite = prereq[1]; //获取前置课程的下标，其表示链表，然后把其后续课程挂到该链表上 graph.get(prerequisite).add(course);  //后续课程的入度++inDegree[course]++;  }  // 4. 创建队列，将所有入度为0的课程加入队列  Queue<Integer> queue = new LinkedList<>();  for (int i = 0; i < numCourses; i++) {  if (inDegree[i] == 0) {  queue.offer(i);  }  }  // 5. 记录已学习的课程数量。这里进行统计是有好处的，方便返回结果时的判断  int count = 0;  // 6. BFS  //将入度为0的可删除节点不断的进行扩展。BFS的思想。while (!queue.isEmpty()) {//队头出队，表示 当前 这节课学了。然后课程统计++  int course = queue.poll();  count++;  // 将当前课程的所有后续课程的入度减1  for (int nextCourse : graph.get(course)) {  //入度表成功匹配的进行--inDegree[nextCourse]--;  // 如果入度变为0，加入队列//这里我之前还想着要每次如何把入度为0的点加入队列，一开始以为每次都要遍历入度数组//其实在进行删除的时候，就可以判断当前点是不是即将要成为入度为0的点，然后被删除。  if (inDegree[nextCourse] == 0) {  queue.offer(nextCourse);  }  }  }  // 7. 判断是否所有课程都已学习//什么时候会不成立？那当然是能删的都删完了，最后还有剩下没学的课程。//所以如果课程全部学完了，count肯定为numCourses。  return count == numCourses;  }  
}

做的时候是否产生这样的疑问，这个疑问决定了你真的模拟理解了这个题。

每次都要遍历当前课程的邻接表里面的链表，对里面的课程进行入度–。那么某节点的度数会被减成负数吗？

回答是不会。因为链表上面的课程是后续课程，我们处理课程是从前面进行处理的。所以其入度实际上是代表了该节点前面还有多少前序节点。

---

208 实现Trie（前缀树）

先了解什么是前缀树：

就像这样，如果两字符串他们前缀相同，则他们后面的字符都挂在同一节点下面。可以看到，这样存储的效率很高，查找效率也并不差。

然后来看例题。这个掌握这个例题，就是掌握了字典树的基本使用。
1、如何定义字典树？
2、字典树的插入操作？
3、字典树的查找操作？
4、判断某前缀在字典树中是否存在？

我们逐个击破
1、如何定义字典树？
目前我们遇见的这个题目对于字典树的要求，存的仅仅只是小写字母。
对于字典树而言，他的定义和我们之前见到的树的定义非常的不相同，并不是像我们所想的，有节点值，然后还有后驱指针。

定义字典树就要从这个图中来观察，我们任取一个节点，比如a来进行观察，那么可以理解目前有一个字符串，它的前缀为ca。如果之后我们插入更多前缀为ca的字符串，那么从节点a往后来想。这个节点a的最大分叉应该是26分叉对吧。所以，对于任意一个节点。它都有可能最大能取到26分叉。对于根节点而言，字符串首字母肯定也是26种可能性。
因此现在可以总结。这个字典树定义的结构里，肯定有一个TrieNode数组。长度为26。用来存储它的26分叉。

还需要什么结构？需要一个末尾节点的表示判断。在定义中加上一个isWord。可以非常方便我们进行很多操作的完成，比如查找操作。

现在就可以总结出定义怎么写了：

class TrieNode {boolean isWord;TrieNode[] children = new TrieNode[26];
}

对于初始化来说，想象你正在初始化一个字典树，根节点为root。那么这个初始化显而易见。因为从这个root开始，那么肯定也是26分叉。所以说就是直接创建一个Trie作为root节点。

class Trie {TrieNode root;public Trie() {root = new TrieNode();}
}

简单总结就是，26分叉树。
这里相当于用字母下标存储了26个字母，可以这么理解，里面的数组不为空的地方的就是该节点之后的节点。

class TrieNode {boolean isWord;TrieNode[] children = new TrieNode[26];
}class Trie {TrieNode root;public Trie() {root = new TrieNode();}//插入操作//实际上就是遍历字符串，然后将每个字符加入到字典树中,始终结合图来想。public void insert(String word) {//创建一个遍历指针，这个遍历指针专门用来检查每个节点的后续数组，cur的起点为root，因为要从root开始检查分支是否存在，字符串是从root开始挂字符的。TrieNode cur = root;for(int i = 0;i<word.length();i++){//寻找当前遍历字符对应的数组下标int c = word.charAt(i)-'a';//判断该节点的后续数组里有没有这个字符//如果为null，表示这个字符在这个节点的分支上并不存在，那么就要新开一个分支了，所以new一个TrieNode。//如果往后都是null，那么这其实就是插入新字符串的过程。//总结就是如果节点存在，那么就用存在的，如果不存在，那么就加新分支if(cur.children[c] == null){cur.children[c] = new TrieNode();}//如果存在，或者是刚刚开了一个新分支，那么就沿着这个分支往下面走。cur = cur.children[c];}//由于指针一开始在root，都是每次构造完毕指针才进行后移，因此最后构造完毕的时候，指针就在指在最后一个节点上。所以把最后一个节点的判断赋值为true。cur.isWord = true;}//搜索操作，搜索该字符串是否存在。//思想还是遍历字符串，但是如果遍历的过程中，发现遍历的字符在后续分支上不存在（也就是null），那么直接返回false。//如果能把这个字符串完整的遍历完，那么最后肯定就是会停留在最后一个节点上。此时返回该点是否是最后一个节点就行了，或者直接返回true也行。public boolean search(String word) {TrieNode cur = root;for(int i = 0;i<word.length();i++){//计算当前字符在哪个分支。int c = word.charAt(i)-'a';//看看该分支是否为null，为null说明不存在直接返回false。if(cur.children[c]==null){return false;}//向下一个点遍历cur = cur.children[c];}//能遍历完说明字符都存在了，返回这个最后的节点的isWord属性也可以，直接返回true也可以return cur.isWord;}//判断某字符串前缀是否存在，还是和上面的思路意义，不过就是变成了遍历前缀字符串。public boolean startsWith(String prefix) {TrieNode cur = root;for(int i = 0;i<prefix.length();i++){int c = prefix.charAt(i)-'a';if(cur.children[c] == null){return false;}cur = cur.children[c];}return true;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/