M.DAI'M²
Live moderately, Life add longevity10.1 斐波那契数列
题目描述
求斐波那契数列的第 n 项，n <= 39。
解题思路
如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。
递归是将一个问题划分成多个子问题求解，动态规划也是如此
20. 表示数值的字符串
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。 例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
解题思路
使用正则表达式进行匹配。
[] ： 字符集合 ()
* [3. 数组中重复的数字](#3-数组中重复的数字)
* [4. 二维数组中的查找](#4-二维数组中的查找)
* [5. 替换空格](#5-替换空格)
* [6. 从尾到头打印链表](#6-从尾到头打印链表)
* [7. 重建二叉树](#7-重建二叉树)
* [8. 二叉树的下一个结点](#8-二叉树的下一个结点)
* [9. 用两个栈实现队列](#9-用两个栈实现队列)
#
题目：找到所有数组中消失的数字
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。 找到所有在 [1, n] 范围之间没有出现在数组中的数字。
示例：
输入: [4,3,2,7,8,2,3,1] 输出: [5,6]
思考：
遍历数组，取数组中每个元素的绝对值-1（这里-1是因为数组下标从0开
题目：平方数之和
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a 的平方加 b 的平方等于 c 。
示例：
输入: 5 输出: True 解释: 1 * 1 + 2 * 2 = 5 输入: 3 输出: False
思考：
这题因为 a * a + b * b = c,所以 a < 根号c，b < 根号c。 所以可以用两个变量i = 0，j = 根号c， 当 i <= j 时，计算i * i + j * j 当结果小于c则i++，否则j--， 若结果等于c则返回true。
实现：
class Solution {
public boolean judgeSquareSum(int c) {
int i = 0;
int j = (int) Math.sqrt(c);
while (i <= j) {
int num = i * i + j * j;
if (num == c) {
return true;
}
if (num < c) {
i++;
} else {
j--;
}
}
return false;
}
}
最近看了一种数据结构叫做skipList，redis和levelDB都是用了它。Skip List是在有序链表的基础上进行了扩展，解决了有序链表结构查找特定值困难的问题，查找特定值的时间复杂度为O(logn)，他是一种可以代替平衡树的数据结构。
下面是skipList的一个介绍，转载来的，源地址：http://kenby.iteye.com/blog/1187303，为防