Posts Tagged 算法

关于字符串“循环左移”算法的讨论

问题:有一个长度为n的字符串,对其循环左移i位,就像这样,有字符串“abcdefg”,对其循环左移3位得到“defgabc”。使用什么样的算法实现?

这个问题是腾讯C/C++研发实习生的一个面试题。

我要说明一下,在这里我只是关注算法。在实现中,不考虑错误检测或者异常处理,也不考虑特殊的情况,比如i<0就是循环右移啊,i>n需要取模啊等等;也不计算每种算法实现都需要步骤的时间开销,比如字符串的初始化,事实上,为了简化代码,我就直接使用了string类型而不是char[ ],再比如求字符串的长度,就直接调用了字符串处理函数等等。做这么多简化,为的就是能更侧重算法本身。下面来看几种实现算法。

一、使用一个字节的额外空间开销

这种算法要经历i趟,每一趟把str[0]赋值给临时变量char t,剩余的字符向左移动一位,即str[k]=str[k+1],移动完成后把临时变量t赋值给str[n-1]。

//code in C++
string rotateLeft_1(string str,int i)
{
	char t;
	int strlen;
	strlen = str.length();
	for (int j=0;j<i;j++)
	{
		t = str[0];
		for (int k=0;k<strlen;k++)
		{
			str[k] = str[k+1];
		}
		str[strlen-1] = t;
	}
	return str;
}

这个算法虽然空间开销小,但是时间开销可大了去了,两层的嵌套循环,效率太低。有没有效率高一点的算法呢——废话,当然有!

二、使用n个字节的额外空间开销

减小时间开销的一个基本思想是以空间换时间。这个算法使用一个新的长度为n的字符串(字符数组)保存原始字符串的副本,然后对原始字符串的每个元素重新赋值。

//code in C++
string rotateLeft_2(string str,int i)
{
	int strlen;
	strlen = str.length();
	string t = new char[strlen];
	for (int j=0;j<strlen;j++)
	{
		t[j] = str[j];
	}
	for (j=0;j<strlen;j++)
	{
		str[j] = t[(j+i)%strlen];
	}
	return str;
}

这种算法要比第一种时间开销小,但是似乎空间上的开销过大了。

三、使用i个字节的额外空间开销

显而易见,上面的算法远非最佳算法,所以算法有在时空上取得双赢的改进的可能。第三种算法将字符串的前i个元素复制到一个临时字符串(字符数组)中,将原始字符串余下的n-i个元素左移i个位置,最后将最初的i个元素从临时字符串(字符数组)中复制到余下的位置。

//code in C++
string rotateLeft_3(string str,int i)
{
	string t = new char[i];
	int strlen = str.length();
	for (int j=0;j<i;j++)
	{
		t[j] = str[j];
	}
	for (j=i;j<strlen;j++)
	{
		str[j-i] = str[j];
	}
	for (j=strlen-i;j<strlen;j++)
	{
		str[j] = t[j-strlen+i];
	}
	return str;
}

这种算法看上去和第二种没太大差别,但无论从时间开销还是空间开销上来讲,都要比第二种好。原因在于虽然原始字符串中的每个位置都要发生变化,但没有必要花费n个字节的内存开销保存原始字符串的副本,只需保存前i个位置的元素。不过总觉得这种算法还不够好-_-!

四、使用一个字节额外空间开销的“杂技”算法

同样是使用一个字节的额外空间开销,但这种“有点像精巧的杂技动作”的算法的时间开销比第一种要小很多。首先把str[0]存到一个临时变量char t中,然后移动str[i]到str[0],str[2i]到str[i],……,直到遇到str[0](str的下标对n取模),将t赋值给刚才移动的最后一个位置。str中的每个元素都要进行移动,如果没有移动完,就从str[1]开始再次移动,直到所有的元素都已经移动了。

//code in C++
string rotateLeft_4(string str,int i)
{
	int strlen = str.length();
	char t;
	int count = 0;    //统计移动次数
	int j,k = 0;      //k初始化为0,从str[0]开始
	while (1)
	{
		t = str[k];         //开始的元素保存到临时变量t中
		j = (k+i) % strlen;
		while(j != k)       //开始移动,直到遇到开始的元素
		{
			str[(j-i+strlen) % strlen] = str[j];
			count++;    //移动次数统计量+1
			j = (j+i) % strlen;
		}
		str[(k-i+strlen) % strlen] = t;    //临时变量t中保存的值赋值给刚才移动的最后一个位置
		count++;
		if (count<strlen)    //判断是否所有元素都已经移动
		{
			k++;         //没有移动所有元素,再次从str[k+1]开始
		}
		else
		{
			break;       //所有元素都已经移动,跳出循环
		}
	}
	return str;
}

这个算法看起来就比较复杂,难怪说是“有点像精巧的杂技动作”,实现起来也要格外小心。

五、“翻手”算法

来看一个有趣的实现字符串循环左移的算法。在具体讲这种算法之前,先来看看线性代数里的转置。(AB)T等于什么?等于BTAT。那么(ATBTT等于什么?等于(BTT(ATT,即BA。

啊哈!我们用三个步骤就可以完成这个字符串的循环左移了。对于字符串来讲,转置在这里就是逆置。把原始字符串分成ab两部分,a是前i个元素,b是后n-i个元素,首先对a求逆,得到a-1b,然后对b求逆得到a-1b-1,然后对整体求逆得到(a-1b-1-1=ba。

下面这张图形象地说明了这种算法,这里是将一个长度为10的字符串循环左移5位。

//code in C++
string reverse(string str,int m,int n)
{
	char temp;
	while(m<n)
	{
		temp = str[m];
		str[m] = str[n];
		str[n] = temp;
		m++;
		n--;
	}
	return str;
}
string rotateLeft_5(string str,int i)
{
	int strlen = str.length();
	str = reverse(str,0,i-1);
	str = reverse(str,i,strlen-1);
	str = reverse(str,0,strlen-1);
	return str;
}

我写的代码有些丑陋。“翻手”算法的时空效率是比较高的。

另外来看一下使用python实现的算法。用python来处理字符串非常方便,尤其是分片,简直就是神器啊。(这里就不讨论时空效率了)

#code in python
#! /usr/bin/python
str = raw_input("Please input the string and i\n")
i = input()
str = (str[i-1::-1]+str[:i-1:-1])[::-1]
print str

这里将分片操作的最后一个参数置为-1,用作置逆。但这是不是多此一举呢?既然都有分片操作了,直接分片连接就行了,这似乎就没有设计算法的味道了。

#code in python
#! /usr/bin/python
str = raw_input("Please input the string and i\n")
i = input()
str = str[i:]+str[:i]
print str

上面五个算法里我认为最漂亮的是第五个算法,算法思想简洁优美,实现起来也不复杂,并且效率高,空间开销也小。

,

4 Comments