算法背景 有时候,可能会遇到这样的表:整个表中的元素未必有序,但若划分为若干块后,每一块中的所有元素均小于(或大于)其后面块中的所有元素。我们称这种为分块有序。 对于分块有序表的查找 首先,我们需要先建立一个索引表,索引表中为每一块都设置–索引项,每一个索引项都包含两个内容: 该块的起始地址 该块中最大(或最小)的元素 显然,索引表是按关键字递增或递减次序排列的。如下图所示: . 查找过程 在前面建立的索引表的基础上,我们查找一个关键字需要两个步骤: 在索引表中查找,目的是找出关键所属的块的位置。这里如果索引表较大…

2017年12月14日 0条评论 5点热度 阅读全文

#1014 : Trie树 时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述 小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。 这一天,他们遇到了一本词典,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能对于每一个我给出的字符串,都在这个词典里面找到以这个字符串开头的所有单词呢?” 身经百战的小Ho答道:“怎么会不能呢!你每给我一个字符串,我就依次遍历词典里的所有单词,检查你给我的字符串是不是这个…

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

#1015 : KMP算法 时间限制: 1000ms 单点时限: 1000ms 内存限制: 256MB 描述 小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。 这一天,他们遇到了一只河蟹,于是河蟹就向小Hi和小Ho提出了那个经典的问题:“小Hi和小Ho,你们能不能够判断一段文字(原串)里面是不是存在那么一些……特殊……的文字(模式串)?” 小Hi和小Ho仔细思考了一下,觉得只能想到很简单的做法,但是又觉得既然河蟹先生这么说了,就肯定不会这么容…

2016年7月31日 0条评论 1点热度 阅读全文

转载地址:http://www.cnblogs.com/yyangblog/archive/2010/12/31/1923128.html 查找算法    一、查找的基本概念 查找,也可称检索,是在大量的数据元素中找到某个特定的数据元素而进行的工作。查找是一种操作。   二、顺序查找 针对无序序列的一种最简单的查找方式。 时间复杂度为O(n)。   三、折半查找 针对已排序序列的一种查找方式。并且只适用于顺序存储结构的序列。要求序列中的元素基本不变,在需要做删除和插入操作的时…

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

Phone List Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7265    Accepted Submission(s): 2501 Problem Description Given a list of phone numbers, determine if it is consist…

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

学习字典树一段时间 了,个人觉得字典树比较容易掌握,但是ACM中题目变化多端,我们只有多练习,才能对字典树的应用有更深的把握。 下面讲解一下字典树。 其实掌握字典树,只需要写过一个关于字典树的程序,记住它的结构就可以了。先看看字典树的定义 struct Trie { Trie *next[MAX]; bool isword; }; 其实上面那个字典树结点的定义只是来自我做的一个题目,里面的元素视你做的题目而定,不过 Trie *next[] 这个数组就是一定的了,只不过他的大小也视你的题目而定。(可能是26个小写字…

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

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents           by---cxlove 平衡二叉树,调整包括左旋转和右旋转,其中有直接旋转和组合旋转,不好画图,具体的SBT可以看http://blog.csdn.net/acceptedxukai/article/details/6921334 自己敲一个,留作模板,稍微改一下就能…

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