找不到工作，刷刷 Leetcode 来保持一下写代码的手感。从最简单的开始，也就是 Acceptance 最高的开始。目前接受率最高的是逆序字符串

题目

编写一个函数能够逆序输出字符串
例子
给定 s = "hello" 返回 olleh

总的来说是一个很简单的题目。CS 的学生估计都做过这道练手题。

In Haskell Way

思路

看到这个题目就很自然的想到使用分治的思想。如果是空字符串则不需要逆序，直接返回即可。如果是长度为1的字符串

  1. 如果是空字符串，不需要逆序，直接返回即可
  2. 如果不是空字符串，将除了第一个字符外的子字符串逆序，之后拼接上第一个字符串即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <string>

string reverseString(string s) 
{
	if (s.length() == 0) 
	{
		return "";
	}
	else
	{
		return reverseString(s.substr(1, s.length())) + s[0];
	}
}

结果

在遇到超长字符时提示 Memory Limit Exceeded 。估计是因为递归的次数太多，调用次数太多而产生 StackOverflow （栈溢出）。所以下一步是要优化递归。通常的解决方案是将递归优化为尾递归。递归通常需要全部展开之后才能计算值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
reverseString("Hello")

	reverseString("ello") + 'H'

		reverseString("llo") + 'e' + 'H'

			reverseString("lo") + 'l' + 'e' + 'H'

				reverseString('o') + 'l' + 'l' + 'e' + 'H'

				'o' + 'l' + 'l' + 'e' + 'H' // 完全展开 开始计算

			"ol" + 'l' + 'e' + 'H'

		"oll" + 'e' + 'H'

	"olle" + 'H'

"olleH"

尾递归是将计算结果传递到下一次递归中。因此之前的任何信息都不需要保存了，清理栈中的参数和返回地址等。这样就不会出现 StackOverflow 。当然这一步是编译器做的优化工作。

In Tail Recursion Way

思路

尾递归需要把计算结果传递到下一次递归中。纯函数的唯一输入只有参数。所以需要通过传递参数的方式将计算结果传递。

代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <string>

string reverseStringTailRecursion(string s, string result = "")
{
	if (s.length() == 0) return result;
	else return reverseStringTailRecursion(s.substr(1, s.length()), s[0] + result);
}

string reverseString(string s) 
{
	return reverseStringTailRecursion(s);
}

结果

先来看一下尾递归版本的计算过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
reverseString("Hello")

reverseStringTailRecursion("Hello","")

reverseStringTailRecursion("ello",'H' + "")

reverseStringTailRecursion("llo",'e' + 'H')

reverseStringTailRecursion("lo",'l' + "eH")

reverseStringTailRecursion('o','l' + "leH")

reverseStringTailRecursion("",'o' + "lleH")

"olleH"

可以发现每一次的计算都与之前的函数不再有关系，只与参数有关。从形状上来看，普通递归是一个箭头型 > 。而尾递归是一个直筒型 ≡ 。信心满满的提交。最后报错，错误和上次一样 StackOverflow 。 看来编译环境没有开启尾递归优化。只好另行他法。既然不允许递归，那就想办法消除递归。通过观察普通递归的计算过程发现其分为展开和计算两个阶段。展开阶段会栈溢出。所以想办法去掉展开阶段，转为普通的循环即可。观察计算的过程，发现是从尾部开始拼接字符串。那么循环从尾部开始即可。

In Loop Way

思路

从尾部开始去字符串，一直拼接，拼接到字符串第一个字符。

代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <string>

string reverseString(string s) 
{
	string result = "";
	for (int i = s.length() - 1; i >= 0; i--)
	{
		result += s[i];
	}

	return result;
}

结果

通过 476 个测试用例，用时 13ms 。超过 25.5% 的人（C++）。总算是通过了。不过似乎成绩不是很理想，居然连一半的人都没有超过。仔细想想还是有优化空间的。现在的时间复杂度是 O(n), 空间复杂度是 O(1) 。看起来似乎是很优秀的数据。但是逆序的过程需要额外的一个字符串来承载结果。能否做成原地（In Place）的呢？答案是肯定的。

In Place Way

思路

交换首尾字符直至完成。

代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <string>

string reverseString(string s) 
{
	int i = 0;
	int j = s.length() - 1; //s.length() 位置是 '\0'
	while (i < j)
	{
		swap(s[i++], s[j--]);
	}
	return s;
}

结果

通过 476 个测试用例，用时 12ms 。超过 29% 的人（C++）。噗，只提升了 5% 。不知道前面的人是不是用了什么稀奇古怪的 Hack 。 尝试了传递参数时传递引用。发现时间没有变化。又尝试了其他方法，都没有什么效果。

总结

先是根据直觉写出递归的方式，然后优化为尾递归，发现编译环境没有做优化。于是改为循环，此时时间复杂度为 O(n) 。之后使用原地交换的方法将时间复杂度降为 O(n/2) 。最后还是没有找到更快的解决方案。如果有更快的方案，欢迎交流。

参考

  1. 什么是尾递归
  2. What is tail recursion
  3. C++ 性能分析