线段覆盖长度

2012年7月16日 4 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

给定一些线段,线段有起点和终点,求这些线段的覆盖长度,重复的部分只计算一次。

这是在小桥流水博客中看到的一道面试题(小米科技),后来为了练习线段树这个数据结构,就做了一下这道题,本节给出两种方法,一种是基于排序来做的,一种是使用线段树来做的。

方法一:

首先说排序对于处理很多问题都是非常有效的,例如寻找兄弟单词等问题中,经过排序处理后,问题就明朗了很多;

线段覆盖长度也是这样,将线段排序后,然后扫描一遍就可以得到覆盖的长度。具体做法:排序时,先按线段的起始端点排序,如果始点相同则按照末端点排,然后从头扫描,寻找连续段;所谓连续段即下一条线段的始点不大于当前线段的末点就一直扫描,直到找到断层的,计算当前长度,然后继续重复扫描直到最后,便得总长度。代码如下:

阅读全文...

关于字符串处理的一些问题 | 目录

2012年7月8日 没有评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

字符串处理问题很常见,一般来说,这样的问题分为单字符串问题和双字符串问题。本博对这些问题也陆续整理了一点,这里做个目录,方便查找,以后慢慢更新。

===单字符串问题===

==反转字符串的思考及三种解法==

==最长重复子串==

==最长不重复子串==

==最长回文子串==

===双字符串问题===

==字符串相似度(编辑距离)==

==最长公共子序列(LCS)==

==最长公共子串==

本节相关代码可以到这里下载。

阅读全文...

字符串排序新探索——使用基数排序

2012年7月7日 1 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

一个偶然的机会发现字符串排序也可以使用基数排序来实现,而且是一个很有意思的问题,因为这其中有一个渐进优化的过程,本文先考虑字符串排序的几种实现方法,然后从理论上分析使用基数排序的复杂度,最后将其与快排进行定性比较,从理论和实现两方面验证在字符串排序问题中,基数排序何时超越快排。

那么字符串排序有哪些方法呢?这里给出一个简洁列表,欢迎补充

  1. 快速排序:最简单最直接的方法,但是规模稍大,字符串大量移动和复制的开销会特别大。
  2. 先做地址索引,然后快排:目前来讲,这似乎应该是最优的方法,有效避免了字符串的移动和复制开销,时间复杂度为O(Lcmp*N*lgN)。Lcmp是字符串比较时的平均比较长度,这个我们稍后做定量计算。
  3. Trie树:这是我写本文草稿时忽然想到的,这种方法也不错,如果串有重复可以在节点设置一个计数域;优点是能有效节省空间,大规模字符串真能节省不少空间呢,内存有限情况下可以考虑,而且理论上复杂度是线性的O(Lave*N),Lave为字符串平均长度,N为串个数;缺点是什么呢?缺点是建树过程要不断的申请开辟空间,大规模情况下这个开销不可忽视;不过我觉得仍然可以一试,改天我再做一个测试,看看百万级规模情况下(硬件条件有限,千万级就做不来了)时间与快排比起来怎么样,本节稍后我们可以从理论上做一个大致的分析。
  4. 基数排序:以上三种方法应该说比较容易想到,也比较常规;偶然发现基数排序在这方面也是有用武之地的,而且某些情况下,它的性能是超越第二种快排方法的,同时在实现上,我们也可以将基数排序分配和收集过程中空间的申请和释放优化掉,甚至可以通过数据结构的有效设计来优化掉桶元素的添加和删除操作时的开销。基数排序的复杂度为O(Lmax*N),Lmax是待排字符串的最大长度,这也是限制基数排序的地方。
  5. Summary:个人认为在实际应用时,后三种方法都是可以考虑的,优先考虑索引快排和Trie树,在了解本文之后,可以知道某些特定情况下基数排序也是不错的选择。

下面说一下,基数排序字符串实现中的几个问题,几个关键词:

阅读全文...

最长回文子串

2012年7月3日 12 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

题:给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度。回文就是正反读都是一样的字符串,如aba, abba等。

例如:aaaa与abab:最长的回文串长度分别为4、3。

解法一:(该解法有误,见勘误)

最先考虑到,这又是一个后缀数组的应用,一个字符串X如果含有回文子串,那么在其后面“连接”一个逆序X’, 类似最长公共子串的解决方法,通过后缀数组寻找,这个最长回文子串必然会出现两次,类似的,我们将串X变为X#X’,其中X’是X的逆序序列。之后的实现跟最长公共子串就基本一样了,代码如下:

阅读全文...

最长公共子序列|最长公共子串|最长重复子串|最长不重复子串|最长回文子串|最长递增子序列|最大子数组和

2012年6月27日 1 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

最近练手,整理了一个“最”系列的主题,这些题目有点绕,个别的还有别名(详见博文),混在一块比较乱,就索性放在一起做了个整理,区别的时候要注意子序列与子串的不同,前者不要求连续,后者要求连续;由于大部分跟DP有关,有的还可以渐进寻求多种解法,可以用来做不错的练手。

下面是这些问题的博文目录

==========================

=1=最长公共子序列(LCS)==

=2=最长公共子串==

=3=最长重复子串==

=4=最长不重复子串==

=5=最长回文子串==

=6=最长递增子序列(LIS)==

=7=最大子数组和(连续子数组最大和)==

==========================

总结:

  1. 问题分类
    • 前两个是关于两个字符串的问题、中间三个是关于单个字符串的问题,最后两个是数组相关的问题;不过不一定绝对,例如最长公共子序列也可以是数组问题;
    • 从解决方案看,12属于“二维”DP问题,因为是两个对象间的问题;467属于“一维”DP问题,是单个对象的问题;345又是后缀数组的典型应用。
  2. 为练手,对大多数问题,尽量逐步探索,整理了多种思路,例如在最长不重复子串问题中,我逐步优化,尝试了四种实现方法,并成功得到了时间为O(N),辅助空间为常数的方案,回头反思,发现其优化的思维得益于对最大子数组和以及LIS的整理与思考。
  3. 这些问题之间相互有很多相通的地方,例如,在最长不重复子串问题中,其DP思路与最长递增子序列有点类似,二者同属“一维”的问题,并且都需要记录当前元素“之前”的某些信息;而在DP优化过程中,最长不重复子串问题又与最大子数组和的优化同出一辙,这两个“一维”的DP问题都只使用O(1)的空间便可以记录子问题的最优解,这种“便捷”的方案并不是空穴来风,而是先通过“规规矩矩”的DP一步步探索,才发现这种“trick”的存在,很是有意思。

勘误:

  • 本系列文章所有代码出现 char xx  [256] 的地方改为 int xx [256] ,因为从逻辑上讲char xx[256] 是有可能出问题的。(感谢HFC

阅读全文...

最长不重复子串

2012年6月25日 20 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

题:从一个字符串中找到一个连续子串,该子串中任何两个字符不能相同,求子串的最大长度并输出一条最长不重复子串。

本节从最直接的方法逐步优化,渐进探索了四种实现方式,并最终找到时间复杂度为O(N),辅助空间为常数的方案,内容如下:

==基本算法 使用Hash==

==DP方案==

==DP + Hash 方案==

==DP + Hash 优化方案==

==================================

基本算法 使用Hash

要求子串中的字符不能重复,判重问题首先想到的就是hash,寻找满足要求的子串,最直接的方法就是遍历每个字符起始的子串,辅助hash,寻求最长的不重复子串,由于要遍历每个子串故复杂度为O(n^2),n为字符串的长度,辅助的空间为常数hash[256]。代码如下:

阅读全文...

最长公共子串(Longest-Common-Substring,LCS)

2012年6月25日 7 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

这个LCS跟前面说的最长公共子序列的LCS不一样,不过也算是LCS的一个变体,在LCS中,子序列是不必要求连续的,而子串则是“连续”的。即:

题:给定两个字符串X,Y,求二者最长的公共子串,例如X=[aaaba],Y=[abaa]。二者的最长公共子串为[aba],长度为3。

本节给出三种不同的实现方式,并对比分析每种方法的复杂度,内容如下:

==基本算法==

==DP方案==

==后缀数组==

==各方法复杂度分析==

==================================

基本算法

其实对于最长公共子串,还是比较简单易想的,因为子串是连续的,这就方便了很多。最直接的方法就是用X每个子串与Y的每个子串做对比,求出最长的公共子串。代码如下:

阅读全文...

最长重复子串

2012年6月25日 5 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

首先这是一个单字符串问题。子字符串R 在字符串L 中至少出现两次,则称R 是L 的重复子串。重复子串又分为可重叠重复子串和不可重叠重复子串,这里只是简单讨论最长可重叠的重复子串,给出基本算法和基于后缀数组的算法;关于后缀数组,这里也只是用最简单的形式实现,对于后缀数组的倍增算法和DC3算法的实现以及不可重叠重复子串的问题可参见算法合集之《后缀数组——处理字符串的有力工具》,以后再整理这几个问题。

最直接的方法就是子串和子串间相互比较,这样查看所有的子串对,时间复杂度为O(n^2),代码如下:

/* 最长重复子串 Longest Repeat Substring */

int maxlen;    /* 记录最长重复子串长度 */
int maxindex;  /* 记录最长重复子串的起始位置 */
void outputLRS(char * arr);  /* 输出LRS */

/* 最长重复子串 基本算法 */
int comlen(char * p, char * q)
{
	int len = 0;
	while(*p && *q && *p++ == *q++)
	{
		++len;
	}
	return len;
}

void LRS_base(char * arr, int size)
{
	for(int i = 0; i < size; ++i)
	{
		for(int j = i+1; j < size; ++j)
		{
			int len = comlen(&arr[i],&arr[j]);
			if(len > maxlen)
			{
				maxlen = len;
				maxindex = i;
			}
		}
	}
	outputLRS(arr);
}

阅读全文...

最大子数组和(最大子序列和 | 连续子数组最大和)

2012年6月22日 16 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

--

一个有N个元素的整型数组arr,有正有负,数组中连续一个或多个元素组成一个子数组,这个数组当然有很多子数组,求子数组之和的最大值。例如:[0,-2,3,5,-1,2]应返回9,[-9,-2,-3,-5,-3]应返回-2。

网上有称之为最大子序列和,亦有称连续子数组最大和。个人觉得叫最大子序列和不太妥,数学上讲,子序列不一定要求连续,而这里我们的题目必然要求是连续的,如果不连续而求子序列最大和很显然就无意义了,这也是为啥又称连续子数组最大和。不过,莫要在意细节。

鉴于《编程之美》对其有几个扩展问题,这里就练手一并实现了,不过整理过程中发现了《编程之美》中的解法错误,查了一下官网的勘误表,居然木有,小激动了一下。。。本节包括以下内容:

==基本思路==

==DP方案==

==返回最大子数组始末位置==

==数组首尾相连【《编程之美》解法错误分析】==

==类似问题==

==================================

基本思路

最直接的方法就是找出所有的子数组,然后求其和,取最大。如果每个子数组都遍历求和,该方法的复杂度为O(N^3),仔细考虑,在遍历过程中,这些子数组的和是有重复计算的:下标i与j之间的区间和Sum[i,j]=Sum[i,j-1]+arr[j]。于是子数组和的求法不必每次都遍历,算法复杂度可以降为O(N^2)。代码如下:

阅读全文...