题目是牛仔裤的意思,不过看不出题意和Blue Jeans有什么关系。 本题的数据是很水的,数据量小,故此可以使用非常暴力的方法过,也可以使用不那么暴力的KMP过。 这里使用更加不暴力的Trie后缀树过,这种解法就一点都不水了,呵呵。 思路: 1 建立所有字符串的后缀Trie树 2 增加额外信息,看每过路径是否是所有的字符串都经过了,如果是,那么就是合法的字符串了,查找最长的这样的字符串 3 优化一下:如果不是所有字符串的经过的路径,那么就可以直接返回,不往下搜索了 最后,我发现删除Trie都是很耗时的,不释放Tri…

2014年8月3日 0条评论 0点热度 阅读全文

字典树的删除操作: 1 没找到直接返回 2 找到叶子节点的时候,叶子节点的count标志清零,代表不是叶子节点了 3 如果当前节点没有其他孩子节点的时候,可以删除这个节点 判断是否需是叶子节点,就检查叶子节点的count标志就可以了。 判断是否有其他孩子节点就需要循环26个节点了,如果都为空,那么就没有其他孩子节点了。 #include <stdio.h> #include <stdlib.h> #include <iostream> #include <vector>…

2014年5月30日 0条评论 0点热度 阅读全文

最短路径的O(ElgV)的解法。 使用邻接表存储图,使用堆操作选取下一个最小路径点。 本题的难度并不在最短路径本身这个算法,而是在于堆的操作: 1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好做。 2 使用一个数组记录当前顶点在堆中的位置,相当于一个hash表了,可以需要的时候,直接从表中查找表示顶点的堆节点在堆中的位置,要记得更新节点时维护好这个表。 3 释放内存的时候注意,弹出堆的节点可以马上释放,不过注意不要双重释…

2014年5月29日 0条评论 2点热度 阅读全文

AVL可以保证搜索达到O(lgn)的时间效率,因为两边的树高都差不多。不会出现搜索是线性的最坏情况。 但是AVL在插入和删除节点的时候需要做较多的旋转操作,所以如果修改节点多的时候,最好使用红黑树,但是如果搜索多的时候,就最好使用AVL了。 参考:http://www.geeksforgeeks.org/avl-tree-set-1-insertion/ 注意点: 1 判断关键字和节点的孩子节点的大小判断应该是左转还是右转 2 利用递归就不需要记录父母节点了 3 注意更新balance和判断balance的顺序 #…

2014年5月26日 0条评论 1点热度 阅读全文

Trie是非常高效的信息检索数据结构, 时间效率会是O(m),其中m是需要搜索的关键字的长度。缺点就是需要的存储空间大。 Trie的特点: 1. 每个Trie的节点都由多个分支构成 2. 每个分支代表可能的关键字的一个字符 3. 需要mark(标志)每个关键字的最后一个字符为leaf node(叶子节点) 英文字母的节点数据结构可以表示如下: struct TrieNode { int value; /* Used to mark leaf nodes */ TrieNode *children[ALPHABET_…

2014年4月25日 0条评论 0点热度 阅读全文