网站建设能不能使用模板,wordpress时间,流行的网站建设技术有哪些,超市库存管理软件java算法day26
207 课程表208 实现Trie(前缀树) 207 课程表
这题对应的知识是图论里的拓扑排序的知识。从题意就可以感受出来了。题目说如果要学习某课程#xff0c;那么就需要先完成某课程。 这里我描述比较复杂的情况#xff1a;课程与课程之间也有可能是多对一的场景或者…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.//下标就代表了课的编号 ListListInteger 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的课程加入队列 QueueInteger 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;iword.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;iword.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;iprefix.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);*/
