存档

2012年7月 的存档

线段树

2012年7月16日 1 条评论

---

概述

线段树也叫区间树,顾名思义,线段树是一种基于区间的树,每个节点表示一个“线段”或“区间”。树的根节点表示是“整体”的区间,左右子树分别表示这个区间的左半边和右半边。

基本结构及性质

假设要构造一个表示N个区间大小的线段树,线段树的根节点表示区间[0,N-1],然后将区间分成两半,分别为左右子树表示,这样的线段树的节点只有2N-1个,是O(N)级别的,如图所示表示构造区间[1-5]的线段树。

1)存储:

线段树可以使用链状结构动态构造,这样的优点是节省空间,空间复杂度在2N,但是缺点就是编程复杂度大,执行效率低;

所以线段树一般是使用一维数组以完全二叉树的方式来存储,类似堆,这样的编程复杂度低,执行效率高,但是耗费空间,一般来讲,这样情况下都是申请4N的空间,关于这方面的分析请见参考资料。

2)实现细节:

使用一维数组存储,设父节点的下标为idx,则左儿子下标为(idx<<1)+1,右儿子下标为(idx<<1)+2。

一般来讲,线段树的节点必有的两个域为left和right,代表该节点表示区间[left,right],区间的中间节点为mid=(left+right)>>1,它左儿子表示的区间为[left,mid],右儿子表示的区间为[mid+1,right],有时候右儿子的区间为[mid,right],具体是什么取决于实际问题,主要是看解决的问题是针对于“点”还是针对于“区间”,具体可参见本节后面的应用举例部分。

阅读全文...

逆序对 | 逆序数

2012年7月16日 3 条评论

---

设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对(inversion)【《算法导论》2-4】

现给出一个数列,求该数列中的逆序对数(逆序数)。本节给出三种方法:方法一是最直接的暴力方法;方法二是基于归并分治的思想;方法三是基于线段树的。

解法一

暴力方法最直接,也最容易想到,两层for循环就可以算出来逆序数:每遇到一个元素回头遍历寻找比其大的元素个数即可,当然向后寻找比其小的元素个数也可以,复杂度为O(n^2),代码:

	int sum = 0;
	for(int i = 0; i < size; ++i)
	{
		for(int j = i+1; j < size; ++j)
		{
			if(arr[i] > arr[j])
			{
				++sum;
			}
		}
	}
	return sum;

解法二

这种方法最初见于《算法导论》,这里先附上《算法导论》2-4关于逆序对的几点讨论:

阅读全文...

线段覆盖长度

2012年7月16日 4 条评论

---

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

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

方法一:

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

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

阅读全文...

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

2012年7月8日 没有评论

---

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

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

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

==最长重复子串==

==最长不重复子串==

==最长回文子串==

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

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

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

==最长公共子串==

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

阅读全文...

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

2012年7月7日 1 条评论

---

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

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

  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 条评论

---

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

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

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

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

阅读全文...