- 浏览: 887896 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
小宇宙_WZY:
膜拜一下大神,解决了我一个大问题,非常感谢 orz
【解惑】深入jar包:从jar包中读取资源文件 -
JKL852qaz:
感谢,遇到相同的问题!
【解惑】深入jar包:从jar包中读取资源文件 -
lgh1992314:
为什么java中调用final方法是用invokevirtua ...
【解惑】Java动态绑定机制的内幕 -
鲁曼1991:
说的都有道理,protected只能被同一级包的类所调用
【解惑】真正理解了protected的作用范围 -
鲁曼1991:
...
【总结】String in Java
1、经典最长平台算法
已知一个已经从小到大排序的数组,这个数组中的一个平台(Plateau)就是连续的一串值相同的元素
,并且这一串元素不能再延伸。例如,在
1,2,2,3,3,3,4,5,5,6中[1]、[2,2]、[3,3,3]、[4]、[5,5]、[6]都是平台。是编写一个程序,接受一个数组,把这个数组中最长的平台找出
来。在上面的例子中3,3,3就是该数组中最长的平台。
【说明】
这个程序十分简单,但是要编写好却不容易,因此在编写程序时应该考虑下面
几点:
(1) 使用的变量越少越好;
(2) 把数组的元素每一个都只查一次就得到结果;
(3) 程序语句也要越少越好。
这个问题曾经困扰过David Gries 这位知名的计算机科学家。本题与解答取自David Gries 编写的有关程序设计的专著。
#include <stdio.h> int longest_plateau() { int x[] = { 3, 4, 4, 7, 8, 9, 9, 9, 9, 10}; int n = sizeof(x)/sizeof(int); int length = 1; /* plateau length >= 1. */ int i; for (i = 1; i < n; i++) if (x[i] == x[i-length]) length++; return length; }
这是一个时间复杂度为O(n) 的经典算法,其代码十分简练。
另外,我自己也写了一个时间复杂度为O(n)的算法,原理就是找出所有平台分界位置,后一个位置减前一个位置(平台长度)的最大值。
int longest_plateau(){ int keys[] = {3, 4, 4, 7, 8, 9, 9, 9, 9, 10}; int size = sizeof(keys)/sizeof(int); int maxLength=0; //记录最大的平台长度 int maxLowBound=-1; //记录最大平台的首偏移 int maxHighBound=-1; //记录最大平台的尾偏移 int index=1; // 两个分界点位置进行一次比较,index=0或1 int bound[2]; //记录每一次比较长度的首,尾偏移 bound[0]=1;//第一个平台的首偏移在数组第0个位置 for(int i=1;i<size;i++){ if(keys[i]!=keys[i-1]){ bound[index++]=i; //当前平台的尾偏移(即下一个平台的首偏移) } if(index==2){ //比较平台长度 if(bound[1]-bound[0]>maxLength){ maxLength=bound[1]-bound[0]; maxLowBound=bound[0]; maxHighBound=bound[1]; } bound[0]=bound[1]; //当前平台的尾偏移成为下一个平台的首偏移 index=1; //准备记录下一个平台的尾偏移到Bound[1]上 } } // printf("longest plat's length is %d\n",maxLength); // printf("longest plat is "); // for(int j=maxLowBound;j<maxHighBound;j++){ // printf("%d",keys[j]); // } return maxLength; }
2、改进的最长平台算法
上面O(n)的时间复杂度级别已经很不错了,但是如果n值特别大,那么仍然要比较n次才可以出结果,我们能不能降低比较次数呢? 显然,这个问题是可以优化的。
我们再来回顾一下David Gries的经典算法(代码1的line: 9),不管当前最长平台的长度为多少,每一次比较都是i++。难道每一次比较都是必须的吗? 比如下面这个平台串:
pArr[]: 1 1 1 2 2 2 2 2 3 3 4 4 5 5
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
分析: 当pArr[2]==pArr[0]的时候,最长平台长度已经增到了3。此时继续比较pArr[3]==pArr[0]发现不相等。那么说明pArr[3]已经开始了一个新的平台。依据经典算法,我们还要继续比较pArr[4]==pArr[1],pArr[5]==pArr[2]。显然,这两个比较是不必要的,因为pArr[3]开始了新的平台,位置3之前的所有数据都不会和3之后的所有数据相等了。
根据上面的分析,我们很容易的想到可以跳跃一定的次数进行比较,跳跃多少呢?最简单的想法就是跳跃一个当前的longest(最长平台长度)。因为如果当前pArr[index]==pArr[index+longest]的话,说明当前平台长度比上一次的longest还要长,如果pArr[index]!=pArr[index+longest]的话,那么目前的平台长度绝对不会超过longest,也就没有必要再去比较小于longest的平台长度是多少了。
问题并没有想象的那么简单,跳跃longest长度之后,为了下一次还能够跳跃longest长度,有的时候是需要回溯一段距离的。 我们来看看下面的详细算法分析。
还是上面的例子,我们来一步一步的研究这个改进的算法。
(1) 首先计算第一个平台 "1 1 1" 得到了当前最长平台长度为longest=3,当前串位置index=3。
(2) 这时我们比较pArr[index]==pArr[index+longest](即比较pArr[3]<->pArr[6])。显然相等,那么longest++(即longest=4)。然后继续循环比较pArr[index]==pArr[index+longest],直到不相等为止。此时index=8, longest=5.
(3) 这一步非常重要,当前的index=8已近开始了一个新的平台, 而当前的longest=5。继续比较pArr[index]==pArr[index+longest](即比较pArr[8]<->pArr[13]),发现不相等。此时我们能不能继续从pArr[13]开始向后跳跃longest=5的长度呢。显然不对,因为pArr[13]并不是平台5的开始位置,pArr[12]=5。如果跳跃longest长度,后面的计算结果将全部错误。 此时,我们必须从13开始回头遍历,直到找到平台的其实位置pArr[12],然后从12位置开始跳跃longest=5的长度才可以。
//跳跃最长平台算法 int jump_longest_plateau(int * pArr, int size){ int longest=1; //最长平台长度 int index=1; //平台串位置索引 //计算第一个平台的长度 for(;index<size&&pArr[index]==pArr[index-1];index++,count++) ++longest; //跳跃longest比较平台长度 while((index+longest)<size){ // 如果跳跃之后相等,则循环继续增大最长平台的长度 if(pArr[index]==pArr[index+longest]){ while(pArr[index]==pArr[index+longest]){ ++longest; } index+=longest; }else{ //如果跳跃之后不相等,则回溯寻找当前平台的起始位置 index+=longest; for(;pArr[index]==pArr[index-1];index--); } } return longest; }
算法分析:时间复杂度仍然是O(n)级别 (注意:不要看到双重循环就认为是O(n^2)级别)。随然有的时候需要回溯到平台的起始位置,但改进之后的算法仍然降低了比较次数。 因为跳跃longest后最多需要回溯longest-1次(此时共比较longest次)。也就是最差情况下位置index每次跳跃之后都会回溯到index+1的位置上,因此最差情况下改进算法会蜕化成经典算法的比较次数n。
我们列举出一个最差情况的平台串: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 ....
平均而言,1000个长度的随机初始化平台串,改进算法的比较次数在149次左右。而经典算法必须比较1000次。
发表评论
-
★经典问题—链表中的环问题
2010-06-29 14:43 4397转载:http://www.cppblog.com ... -
★经典问题—元素选择问题
2010-05-24 10:53 3303元素选择问题 : 给定线性序集中n个元素和一个整数k( ... -
【排序结构7】 基数排序
2010-04-20 16:17 4506《桶排序 》中我们能够看到,数据值的范围越大,可能需要桶的个 ... -
【排序结构6】 桶排序
2010-04-19 20:28 22848从《基于比较的排序结构总结 》中我们知道:全依赖“比较”操作的 ... -
【排序结构5】 基于比较的内部排序总结
2010-04-18 16:15 6688★ 基于“比较”操作的内部排序性能大PK ... -
【排序结构4】 归并排序
2010-04-17 16:29 3262归并排序 O(N*logN) 是另一种效率很高的排序方法。&q ... -
【排序结构3】 选择排序
2010-04-14 21:10 3563(1) 简单选择排序 O(N^2) 一趟简单选择排序 ... -
【排序结构2】交换排序
2010-04-14 11:04 25511、起泡排序 O(N^2) ... -
【排序结构1】插入排序
2010-04-13 17:11 29741、基本概念介绍 (1) 如果待排序列中有两个 ... -
【串和序列处理 7】LIS 最长递增子序列
2010-03-25 16:37 5774LIS: 给定一个字符串序列S={x0,x1,x2,.. ... -
【串和序列处理 6】LCS 最长公共子序列
2010-03-23 17:38 8764LCS:又称 最长公共子序列。 其中子序列(subse ... -
【串和序列处理 5】KMP子串匹配算法
2010-03-22 19:59 9023模式匹配: 在字符串 ... -
★经典问题—欧几里得求最大公约数
2010-03-20 19:21 3323问题:快速求取正整数a,b的最大公约数? ... -
【串和序列处理 4】Suffix Trie 子串匹配结构
2010-03-20 15:15 9037Suffix Trie : 又称后 ... -
【串和序列处理 3】Trie Tree 串集合查找
2010-03-18 13:40 17563Trie 树, 又称字典树,单词查找树。它来源于retr ... -
【串和序列处理 2】字符串编辑距离算法
2010-03-15 08:45 11063我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的 ... -
【串和序列处理 1】PAT Tree 子串匹配结构
2010-03-14 19:10 11249Patricia Tree 简称PAT tree ... -
【查找结构6】动态查找树比较
2010-03-12 13:32 11218我们这个专题介绍的动态查找树主要有: 二叉查找树(BST),平 ... -
【查找结构4】红黑树 [RBT]
2010-03-10 10:58 10501大部分转载:http://yanglongylj.blog.1 ... -
【查找结构5】多路查找树/B~树/B+树
2010-03-09 11:56 18104在前面专题中讲的BST、A ...
相关推荐
这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 你的任务,就是对于给定的序列,求出最长上升子序列的长度。 输入样例 7 1 7 3 5 9 4 8 6 1 8 3 6 5 9 5 1 2 3 4 5 0 输出样例 4 4 5 提示 一,对输入...
针对处理机节点具有不同计算速度、不同通信能力的情况,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,提出一种存储受限异构机群系统的序列串最优分配线性规划模型,给出相应的序列串最优分配方法...
测试文字录入内容,常用的处理方法是关键字检测发,通过检测word文件中的关键字,可以测出考生操作的大概结果,但是很不准确,利用最长公共子序列算法进行文字录入测试,可以很好的解决这一问题。
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
ACM资料 字符串处理 字符串输入 最长上升子序列 并差集
给定一个字符串,寻找其中最长的重复子序列,如果字符串是单个字符组成的话如“aaaaaaaaaaaaa”那么满足要求的输出就是a 思路: 这里的思路有两种是我能想到的 (1)从头开始遍历字符串,设置标志位,在往后走的过程...
动态规划适用于多种实际应用场景,例如最短路径问题、背包问题、字符串匹配问题、最长公共子序列问题以及最长递增子序列问题等。在实际应用中,动态规划可以大大提高算法的性能,并找到问题的最优解。 总的来说,...
本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法。分享给大家供大家参考,具体如下: 问题 输入 第1行:字符串A 第2行:字符串B (A,B的长度 <= 1000) 输出 输出最长的子序列,如果有多...
字符串处理上:lcs(最长公共子序列),kmp(字符串匹配算法),复杂题设计思维+注释,类的设置,数据封装,多重嵌套解法。 图论算法上(目前出现过的):设置高效的邻接表,dfs是基础,bfs(最优/短问题且各边权值为1...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
11.5 处理NP完全问题的技术 11.5.1 回溯法和分枝限界法 11.5.2 确保性能的近似算法 11.6 小结 第12章 并行算法 12.1 引言 12.2 并行计算模型 12.3 共享存储器算法 12.3.1 并行加 12.3.2 寻找最大数的算法 ...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...