常见数据结构与算法题

范畴：递归

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;
}
};