范畴：递归
1、青蛙跳台阶
青蛙跳台阶算法，每次可以跳1级或两级，请问有n级台阶，有多少种算法，递归和非递归如何写
-
递归：
public int JumpFloor(int n) { if (n < 0) return 0; int[] fibArry = { 0, 1, 2 }; if (n < 3) return fibArry[n]; return JumpFloor(n - 1) + JumpFloor(n - 2); } -
非递归：
public int JumpFloor(int n) { if (n < 0) return 0; int[] fibArry = { 0, 1,2 }; if (n < 3) return fibArry[n]; long nReturn = 0L; long fibFirst=1L; long fibTow=2L; for (int i = 3; i <= n; i++) { nReturn = fibFirst + fibTow; fibFirst=fibTow ; fibTow = nReturn; } return nReturn; }
2、变态跳台阶 来自牛客网
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：
关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:
f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。
f(3) = f(3-1) + f(3-2) + f(3-3)
...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
说明：
1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。
2）n = 1时，只有1种跳法，f(1) = 1
3 ) n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1） ，f(2) = f(2-1) + f(2-2)
4 ) n = 3时，会有三种跳得方式，1阶、2阶、3阶，
那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)
因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
5 ) n = n时，会有n种跳的方式，1阶、2阶...n阶，得出结论：
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
由以上已经是一种结论，但是为了简单，我们可以继续简化：
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出：f(n) = 2f(n-1)
7 ) 最终结论 在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：
| 1 ,(n=0 )
f(n) = | 1 ,(n=1 )
| 2*f(n-1) ,(n>=2)
代码：
public class Solution {
public int JumpFloorII(int target) {
if(target < 0){
return -1;
}else if(target == 0 || target == 1){
return 1;
}else{
return 2*JumpFloorII(target-1);
}
}
}
范畴：树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的 前序遍历 和 中序遍历 的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
/**
*Definition for binary tree
*struct TreeNode {
*int val;
*TreeNode *left;
*TreeNode *right;
*TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
int inlen = in.size();
if(inlen == 0){
return NULL;
}
vector<int> left_pre,right_pre,left_in,right_in;
// 创建根节点，根节点肯定是 前序遍历 的第一个数
TreeNode* head = new TreeNode(pre[0]);
// 找到 中序遍历 根节点所在位置，存在变量gen中
int gen = 0; // 从中序遍历中找到的 根节点的坐标
for(int i = 0; i < inlen; i++){
if(in[i] == pre[0]){
gen = i;
break;
}
}
// 接下来两个for循环判断：哪些元素属于该根节点的左边，哪些属于右边
// 对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边节点位于二叉树右边
// 利用这一点对二叉树进行归并，先判断左边的
for(int i = 0; i < gen; i++){
left_in.push_back(in[i]);
left_pre.push_back(pre[i+1]); //+1跳过前序的根节点
}
for(int i = gen+1; i < inlen; i++){
right_in.push_back(in[i]);
right_pre.push_back(pre[i]); //这里不用加1
}
// 和shell排序的思想类似，取出前序和中序根节点左边和右边的子树，
// 也就是前面两个for循环中保存起来的前序和中序的左右子树数组
// 递归电泳该方法直到叶子节点
head->left = reConstructBinaryTree(left_pre,left_in);
head->right = reConstructBinaryTree(right_pre,right_in);
return head;
}
};