归并排序是一种相当稳健的排序算法，无论何种输入序列，其期望时间复杂度和最坏时间复杂度都是Θ(nlogn),这已经达到了基于比较排序算法的渐进下界。

因此归并排序时常会用于对可能导致quicksort退化的序列排序。

归并排序是典型的分治算法，一个最常见的实现如下：

void MergeSort(int a[], int low, int high)
{
	if (low < high)
	{
		int midIndex = (low + high) >> 1;
		// take apart
		MergeSort(a, low, midIndex);
		MergeSort(a, midIndex + 1, high);

		Merge(a, low, midIndex + 1, high);
	}
}

void Merge(int a[], int lowFirst, int highFirst, int highLast)
{
	int l = lowFirst;
	int r = highFirst;
	int len = highLast - lowFirst + 1;

	int* pBuffer = new int[len];
	_ASSERT(pBuffer != NULL);
	int* p = pBuffer;

	while (l < highFirst && r <= highLast)
	{
		*p++ = (a[l] <= a[r]) ? a[l++] : a[r++];
	}

	while (l < highFirst)
	{
		*p++ = a[l++];
	}

	while (r <= highLast)
	{
		*p++ = a[r++];
	}   

	p = pBuffer;
	for (int i = lowFirst; i <= highLast;)
	{
		a[i++] = *p++;
	}

	delete [] pBuffer;
}

但是在实践中，归并排序花费的时间往往超过预期，对于普通的序列而言，所花费的时间甚至远远超过quicksort。

究其原因，和归并排序的内存策略有关。

归并排序不是原地排序，需要额外的存储空间。并且在每次Merge过程中，需要动态分配一块内存以完成对两个数据堆的排序合并。并且排序完毕之后，我们需要将存储空间中的数据复制并覆盖原序列。

最后一步操作是由归并排序自身性质决定，无法优化，所以我们只能针对Merge操作。

经过分析很容易知道，对于长度为n的序列，要执行logn次的merge操作，这意味着需要进行logn次的内存分配和回收。内存操作开销较大。
Read the rest of this entry »

又是一周发文时。。。这次写篇槽文好了

题目来自上届的信息技术应用大赛复赛题，题目描述如下：

用1，2，3组成长度为n的字符串，要求相邻的子串不能重复。输出所有合法的字符串

和ACM之类的比赛不同，这比赛的题目对于算法居然没有时间要求，估计为了降低参赛门槛吧。

既然没有时间限制，只要想一个正确的算法就行，懒得管他复杂度多奇葩。

最容易想到的一个算法是,每生成一位数字后进行有效性测试,符合的话继续探测。而有效性测试的算法也可以有很多种。

最直接的是从末位往前检测，依次比较相邻的字串是否重复。对于长度为k的串而言，最多比较（指的是重复性）[k/2]次。

这种算法的复杂度应该在O(n^3)。

前天晚上当我洗澡回来时，郁磊刚好给出了这个算法的实现。不过代码木有了- -

而在洗澡时，我恰好想到了一种比较奇葩的解法。此方法和Programming Pearls中求解最大子向量和的递归解法相似。

对于长度为k的字符串，首先分成p1=floor{k/2}和p=2ceiling{k/2}两部分，从中间开始往两边遍历检测。如果检测合法，即说明p1和p2中相邻的字串必定不重复。

接着再同时递归处理两部分，停止条件为最后划分出来的集合只有一个元素。

最初郁磊认为这道题和书中的题目并不类似，这个算法应该不能用。但是我一直认为两个题目的模型类似，算法可行。遂花了大约一刻钟，写出了实现代码。

感谢郭嘉，这算法在不考虑性能的情况下运行良好。

有效性检测的代码如下：

bool CheckStr(wchar_t* sz, int low, int upper)
{
	if (low == upper)
	{
		return true;
	}

	int leftEnd = (low + upper) >> 1;
	int rightStart = leftEnd + 1;

	for (int i = 0; leftEnd - i >= low && rightStart + i <= upper; ++i)
	{
		if (!wcsncmp(&sz[leftEnd-i], &sz[rightStart], i + 1))
		{
			return false;
		}
	}

	bool l = CheckStr(sz, low, leftEnd);
	bool r = CheckStr(sz, rightStart, upper);

	return l && r ? true : false;
}

由于这里的递归为分治策略，所以复杂度分析要稍微复杂些。

我们首先可以确定当串长度为n时整个递归表达式为

T(n) = 2T(n/2) + f(n)

这里的f(n)为中间往两边检测的复杂度，经过分析可以得到

f(n) = sigma(1,[k/2]) = O(n^2)

带入得到递归表达式

T(n) = 2T(n/2) + O(n^2)

根据主定理分析，上述表达式属于第三种情况：n^logb(a)小于f(n)且多项式小于，且存在小于1的正数c使得

af(n/b) <= cf(n)

成立（这里取c=1/4即可）

所以递归式的复杂度是O(n^2)，而由于这是生成一个测试位的复杂度，所以整体复杂度为O(n^3)

这里提下生成过程，经过优化的最多测试次数为2(n-1)

虽然无论是直接的反向检测还是递归分治，复杂度都并不好看，但是经过实际测试，发现当n比较大时，符合条件的数反而更少。

另外，以上讨论的方法都是基于生成测试法。似乎此算法的下界也至少是立方复杂度（未证明）。

所以如果要设计更高效的算法的话，应该需要换一个角度。

表达式树是树结构的一个经典应用，常用于编译器的设计。

在表达式树中，叶子通常是常数值或者变量名，统称为操作数（operands）。而其他非叶子结点则包含各种操作符（operators）。

在不同的词法解析中，表达式树的分支设计也不同。对于简单的诸如表达式求解而言，表达式树往往采用二叉树。这是因为每一个操作符正好对应两个操作数。

而在包含一元操作符（e.g自增自减操作符）或三元操作符的复杂情况下，每个操作符结点拥有的不再是两个孩子结点，此时二叉树便显得不太适用。

在此处的简单实现，我们只考虑适合二叉树的表达式求解，其余情况请自行翻阅编译原理相关书籍。当然，无论是哪种情况，本质的算法思想是相同的。

0.构造表达式树

要构造一个表达式树，首先要将一般的中缀表达式（infix）转换成逆波兰式（即后缀表达式，postfix）。

PS：关于逆波兰式以及infix和postfix的转换，请参考我之前的一篇文章http://blog.kingsamchen.com/archives/637

对于中缀表达式(a+b)*(c*(d+e))，其逆波兰式为ab+cde+**，我们现在结合这个表达式，阐述利用逆波兰式构造表达式树的一般步骤。

在构建表达式树时，我们需要一个堆栈，用于保存树或者结点的指针，记这个堆栈为S。

我们对逆波兰式进行遍历，如果碰到的是

（1）操作数，那么则建立一个叶子结点，数据为操作数，并将结点指针保存到堆栈中
（2）操作符，那么从堆栈中弹出两个指针，分别为p2和p1.建立一个结点，内容为操作符，然后分别将结点的左右孩子设置为p1和p2，最后将结点指针压入栈

一直重复以上步骤即可。最后堆栈中保存的即是表达式树的根结点指针。
Read the rest of this entry »

此题来源于经典的求给定数组子数组最大和的变形，同时也是Programming Pearls的课后习题。

不过书中对于此题的分析存在瑕疵，正确的算法需要在原算法基础上做一点小小的改动。

此题的描述如下：

设计一个算法，对给定一个有正有负的整数数组，求数组的子数组中最接近0的和

解决过子数组最大和这一问题，很容易知道，蛮力的枚举不是一个好方法，因为这会使得时间复杂度提高到难以接受的地步。

类似的，我们可以尝试使用“将x[0...n-1]扩展为x[0...n]”的思想，建立一个累积和表cumSum进行处理。这里假设输入数组为x[n]，那么则有

由此我们发现，cumSum两个元素的差值恰好对应一个子数组的和。

剩下我们只需要对cumSum进行排序，然后寻找最接近（差值的绝对值最小）的相邻的两个数即可。
Read the rest of this entry »

前两天看Pointers On C时碰到的问题，问题的详细描述如下：

编写一个函数，该函数接受一个无符号的整数（unsigned int），将这个整数在二进制上进行逆置（即逆置bit位）。

如，十进制的整数7的二进制位是 0000 0000 0000 0111，逆置后的结果为 1110 0000 0000 0000，这个数是3758096384。

函数应当返回逆置后的数。

需要注意的是，为了保持可移植性，并不假设int类型具有32bit长，所以编写的函数要能同时对16bit和32bit有效。

解决问题的关键是，如何正确处理不同字节长。

实际上，我们并不一定需要知道具体的字节长，我们只需要知道何时操作应该停止即可。

联想bitwise相关内容，这里使用一个unsigned int的标志变量i，且将其初始化为1，并对变量i执行单位左移操作。

当i的值为0时，表示左移出界，此时操作应该停止。

demo如下:

typedef unsigned int uint;

// reverses value on bit based
uint ReverseBit(uint value)
{
    uint answer = 0U;

    for (uint i = 1U; i != 0; i <<= 1)
    {
        answer <<= 1;

        if (value & 1)
        {
            answer |= 1;
        }

        value >>= 1;
    }

    return answer;
}

我们每次检测value的第一位（最低位），根据结果设置answer的相应位。

每次操作前，answer都需要右移一位，为下一次操作留出空间。这么做有两个原因：

其一，右移后，之前的bit值会上升到高位，正好迎合我们逆置的目标

其二，每次操作后，answer不能进行位移操作，否则最后一次操作之后的位移会使得代码运行的不正确。

所以我们需要在操作前进行单位位移

题目虽小，却可以说明很多东西

0.在二分搜索中返回元素第一次出现的位置

对于传统的二分搜索，如果要搜索的元素存在重复，那么其只能返回这个元素任意一个位置。

如果我们需要返回这个元素第一次出现的位置，且希望算法仍然保持Θ(logn)的复杂度，那么应该如何设计算法？

我们可以适当的引入一个保持循环不变式成立的断言条件,来作为整个算法思路的突破口。

对于原始的二分搜索来说，这个断言是mustin(l, u),因为每次迭代我们都需要保证目标元素在一个区间之内（假设元素存在）。

相似的，我们可以对这个修改版的二分搜索设立断言条件：a[l]<t<=a[u]。

这个断言条件对于整个算法来说都是至关重要的，以至于只要每次迭代都能使如上断言满足，那么迭代结束后，元素第一次出现的位置就是u。（仍然假设元素存在）

考虑到输入数据的极端情况，l和u初始值应该分别设为-1和n。其中n为元素个数，这里为zero-based。

除此之外，我们只需要对于不存在的情况稍加处理即可。

该算法实现如下：

typedef int DataType;
int BinSearchEx(int data, const DataType a[], int count)
{
	int lower = -1, upper = count;
	int pos;

	// a[l]<t<=a[u]
	while (lower + 1 != upper)
	{
		int mid = lower + ((upper - lower) >> 1);
		if (a[mid] < data)
		{
			lower = mid;
		}
		else
		{
			upper = mid;
		}
	}

	pos = upper;
	if (pos >= count || a[pos] != data)
	{
		pos = -1;
	}

	return pos;
}

一个有意思的结果是，这个扩展版的二分搜索的效率相对要比原始的算法要高，因为每次迭代中元素比较的次数降低了。

扩展问题：如果我们需要返回元素最后一次出现的位置，又该如何设计算法？

A：将断言条件改为a[l]<=t<a[u]

1.乘方的递归算法

如果要计算一个数的n次方，朴素的迭代算法需要Θ(n)的复杂度。这对于日常计算来说已经完全够用，毕竟目前内建整型的数据最多也只能表示到2⁶⁴-1。

但是对于大整数计算来说，线性复杂度并不太让人满意。

而如果利用递归算法，则可以将复杂度降低至Θ(logn)，这可以说是一个质的飞跃。

递归算法的正确性在于：计算aⁿ的结果可以转化为a^n/2的平方，而a^n/2又可以再经过一次转换，再继续递归求解（以上假设n为偶数）。

此递归表达式为：T(n) = T(n/2) + Θ(1)

该算法实现如下：

int Pow(int num, int x)
{
	assert(x >= 0);

	if (0 == x)
	{
		return 1;
	}
	else if (1 == x)
	{
		return num;
	}

	// odd
	if (x & 1)
	{
		return num * Pow(num * num, x >> 1);
	}
	else
	{
		return Pow(num * num, x >> 1);
	}
}

需要注意的一点是，利用Pow(num, x/2) * Pow(num, x/2)来计算偶次方是错误的，因为这样会使得复杂度骤升至线性。

在实际应用中，经常会碰到需要计算和日期有关的问题。其中最常见包括：计算两个给定日期间的天数，返回给定日期的星期以及生成指定年月的日历等。

这些问题实际上都不是非常难（但是某些极易出错），但是运用某些trick可以使得编码更加简洁，算法效率更高。

Q1：如何计算两个给定日期间的天数

首先我们需要明确所谓两个日期间的天数这一定义。

从习惯上说，两个日期间的天数一般看作“从日期一到日期二所需要的天数”。即2011/7/20和2011/7/21之间存在一天。

这个问题在网上流传着众多算法和详细的代码实现，但是大部分都显得比较累赘且低效。比如我在Google的结果中找到的一个sampl（http://sillydong.com/myc/day-counter.html），写了80多行代码（减去了结构声明和头部注释）。

ps：给出URL仅仅用于说明问题，绝无任何恶意。

计算这个问题真的需要那么复杂吗？其实，很多时候，问题都是被自己搞复杂的～

我们首先需要明确一点，要正确的计算两个给定日期间的天数，不可避免的要解决如下两个问题：（1）跨年分的日期 （2）闰年的2月份。

事实上，我们可以根据一个更高效的算法来处理这个问题：

（1）假设没有闰年，即一年都是365天，分别返回两个给定日期在当年日期中的编号（对应的第x天,需要正确处理闰年），分别设为d1和d2

（2）另t为d2减去d1的差。如果两个日期在同一年，则直接返回t。否则加上两个年份之差的365倍

（3）然后在从较小小的日期年份开始遍历，碰到闰年，将天数自增1.但是不用考虑较大日期年份是不是闰年。

这个算法并不复杂，很容易实现。但是要达到简化编码的目的，每一步我们都需要使用一些些trick。
Read the rest of this entry »

首先，这两个问题都来自Programming Pearls（编程珠玑），且都具有令人想不到的解法和应用，值得细细分析和思考。

一、二分搜索缺失整数

此问题描述如下：

给定一个最多包含40亿个随机排列的32位整数文件，找出一个不在文件中的32位整数。在具有足够内存的的情况下，如何解决该问题？如果有几个外部临时文件可用，但是仅有几百字节的内存，又该如何解决？

如果内存足够，那么该问题就变得非常简单。直接利用位向量为每一个数设置标志位，然后遍历搜索即可。

相关的方法在第一章已经使用过，在此不再进行阐述。

而对于第二种情况，问题就变得不是那么容易解决。

由于受到内存大小的限制，位向量的做法显然不可取，而且，提供的临时文件又该怎么使用？

这里有一个高效的解法可以只需要少数的内存（满足题设）和几个外部文件。并且，它还和二分搜索的思想有关。

该算法的描述如下：

以二进制形式来看待每一个整数，第一趟对每一个整数的第一位进行检测，如果第一位是0，则写入文件A，否则写入文件B。

第一趟完毕后，任意一个文件中整数个数不会超过20亿。根据个数较少的文件（如果一样多的话，任选一个文件），把缺失整数变量的第一个二进制设置为对应数值，再把此文件设置为输入文件，重复此操作，logn次之后确定缺失整数。

现在对该算法进行分析：
Read the rest of this entry »