今天是第二天，继续我们的征程。
题目
- 编写代码，把字符串中的每个空格替换为
%20。例如，输入"hello world."，则输出"hello%20world."。 - 编写代码，给定系数n，求1+2+3+...+n的总和，即
∑运算符 - 编写代码，观察如下数列，给定系数n，求数列中的第n个数字(tips: 斐波那契数列)。
1 1 2 3 5 8 13 21 34 55 89 ...
字符替换
本题是将空格等特殊字符变为转义字符的函数，常用于URL编码中，用来避免URL中可能存在的字符歧义。
/**
* 判断当前字符是否为普通字符
*/
public static boolean isPlainChar(char c) {
return (c >= '0' && c <= '9') ||
(c >= 'a' && c <= 'z') ||
(c >= 'A' && c <= 'Z') ||
c == '!' || c == '$' || c == '-' || c == '.' || c == '+' ||
c == '*' || c == '\'' || c == '(' || c == ')' || c == ',';
}
public static char[] encodeMap(char c) {
//构造特殊字符映射表
String[] map = new String[256];
map[' '] = "%20";
map['/'] = "%2F";
map['?'] = "%3F";
map['%'] = "%25";
map['#'] = "%23";
map['&'] = "%26";
map['='] = "%3D";
return map[c].toCharArray();
}
public static char[] urlEncode(char source[]) {
int needLength = 0;
for (int i = 0; i < source.length; i++) {
char c = source[i];
if (isPlainChar(c)) {
needLength++;
} else {
needLength += encodeMap(c).length;
}
}
char result[] = new char[needLength];
int resultIndex = 0;
for (int i = 0; i < source.length; i++) {
char c = source[i];
if (isPlainChar(c)) {
result[resultIndex] = c;
resultIndex++;
} else {
char encodeStr[] = encodeMap(c);
System.arraycopy(encodeStr, 0, result, resultIndex, encodeStr.length);
resultIndex += encodeStr.length;
}
}
return result;
}
//===========
//测试代码
public static void main(String args[]) {
char[] source = "hello world.".toCharArray();
System.out.println(urlEncode(source));
}
累加和 ∑
正向循环解题
要求n个数字的和，则需求出 f(1)+f(2)+...+f(n-1)+f(n)。
本题中等差数列的公差为1，则f(1) == 1 ,f(2) == 2...
public static int sigmaAdd(int n){
int sum = 0;
for (int i = 1;i<=n;i++){
sum+=i;
}
return sum;
}
逆向递归求解
通过观察数列，不难看出数列的如下性质:
f(n) = f(n-1) + 1
我们可以将∑n的问题转化为 f(n) + f(n-1) +...+ f(2) + f(1)，则可以使用递归来求解
public static int sigmaAdd2(int n) {
if (n > 1) {
return n + sigmaAdd(--n);
} else {
return 1;
}
}
递归在算法中的应用非常广泛，许多看似复杂的多重循环问题，都可以通过递归加中止条件写出较为简洁的代码
斐波那契数列
递归算法
先来看斐波那契数列的性质：
- 当n=0时，f(n) = 0
- 当0=1时，f(n) = 1
- 当n>1时，f(n) = f(n-2) + f(n-1)
根据其性质，很容易通过递归写出其代码：
public static int fibonacci(int n) {
if (n <= 0) {
return 0;
} else if (n < 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
//===========
//测试代码
public static void main(String args[]){
System.out.println(fibonacci(20));
}
递归的代码虽然简洁，但简洁不代表简单。以求得f(10)为例，需要先求得f(9)和f(8)。同样，想求得f(9)，需要先求得f(8)和f(7)...我们可以用树形结构来表示这种依赖关系，如下图所示。
不难发现，树中有很多结点是重复的，而且重复的结点数会随着n的增大而急剧增加，这意味着计算量会随着n的增大而急剧增大。你可以试下用递归方式求斐波那契数列的第50项试试，感受一下这样的递归会有多慢。
非递归算法
递归方法之所以慢，是因为重复计算太多，只需想办法避免重复计算，即可加快其速度。比如我们可以把之前计算过的结果保存下来，便于下次计算。
比如先根据f(0)和f(1)得到f(2)，再根据f(1)和f(2)得到f(3)，每次结果均保留，依次类推即可得到第n项的值，其时间复杂度为O(n)。实现代码如下。
public static long fibonacci2(int n) {
int fib[] = new int[]{0, 1};
if (n < 2) return fib[n];
long fib1 = 1;
long fib2 = 0;
long result = 0;
for (int i = 2; i <= n; i++) {
result = fib1 + fib2;
fib2 = fib1;
fib1 = result;
}
return result;
}
时间对比
| 基准 | 递归方式 | 非递归方式 |
|---|---|---|
| fib(20)耗时 | 0ms | 0ms |
| fib(30)耗时 | 4ms | 0ms |
| fib(40)耗时 | 383ms | 0ms |
| fib(50)耗时 | 44269ms | 0ms |
通过表格可以看到，在时间方面非递归方式有着显著的优势。除了时间的开销，递归过程中还会创建多个函数栈，每个函数栈都有自己的参数，返回值等信息，因此递归也会给栈的内存空间带来一定的压力。如StackOverflow调用栈溢出异常就是由于栈空间不足引起的。
从思路上来讲，递归采用的是自顶向下的方式，将一个个较大的问题分解为若干个较小的问题（如 f(10) = f(9) + f(8)），但小的问题可能会有多次重复计算。我们可以反其道而行之，采用自底向上的方式，先从小问题开始处理，记录小问题的结果，然后根据小问题的结果来解答较大的问题，以此类推，得到特定问题的解。
扩展
通过今天的练习，我们分析了递归的一些优缺点。在编写代码时，要了解递归潜在的问题，在一些注重性能的场合，尽量采用循环来代替递归，从而提高程序的运行效率。
此外在面试中，编程题通常不会太直白的表现出来，面试官往往会将问题包装一下，以此来考察我们的分析与建模能力，如下边几个问题。
- 上台阶问题，一共有n个台阶，每次可以上1阶或2阶，那么上到第n阶有几种方法。
- 小马过河问题，河中有n块石头，小马每次能跳过1块或2块石头，那么跳过n块石头有几种方法。
-
如下图所示，用左边的2*1的小矩形横着或者竖着去覆盖右边2*8的大矩形，在不发生重叠的情况下，总共有多少种方法？
矩形覆盖问题
扩展题答案
前两个问题基本一致，我们先来分析问题。
假设有n个台阶，则第一步有两种方法
- 若上1个台阶，则剩下n-1个台阶
- 若上2个台阶，则剩下n-2个台阶
以此类推，不难得出 f(n) = f(n-1)+ f(n-2) 这个式子，是不是很熟悉呢？对的，前两个问题仍是斐波那契数列相关的应用题，有公式后不难得出其答案。
接下来看第三个问题。
我们先把2*8的覆盖方法记为f(8)。用第一个2*1的小矩形去覆盖大举证的最左边边时有两种选择：
- 竖着放，则右边还剩2*7的区域，记为f(7)
- 横着放，则左下方也只能横着放一个2*1的小举证，右边还剩下 2*6的区域，记为f(6)
因此f(8) = f(7) + f(6)，此时可以看出，这仍然是斐波那契数列。
参考书目
《剑指offer》2.4.1
