[数据结构与算法]leetcode刷基础题（递归）

• 斐波那契数列

题目概述：

注意点：
F(n) = F(n - 1) + F(n - 2)这个通项公式是怎么得到的？
已知F0=0，F1=1，比如说F3这个数，我们通过二叉树进行分析。
如图所示：

主要就是这个比较难解决，剩下的问题就好解决了！

相关代码：

class Solution {
    public int fib(int n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        if(n>=2){
            return fib(n-1)+fib(n-2);
        }
        return 0;
    }
}

• 爬梯子问题

题目概述：

注意点：
需要得到climbStairs(n) = climbStairs(n - 1) + climbStairs(n - 2); 这个通项公式，得到过程具体如下：
假如n=3

• 相关代码：

class Solution {
    public int climbStairs(int n) {
        if(n==0){
            return 1;
        }
        if(n==1){
            return 1;
        }
        if(n>=2){
            return climbStairs(n-2)+climbStairs(n-1);
        }
        return 0;
    
    }
}

• 反转字符串

题目概述：

注意点：
涉及到双指针问题，好像和递归没有关系。
遇到双指针问题，最好 for(int i=0, j=s.length-1;i<j;i++,j–)写，而不是两个for循环，这样会更加的麻烦。

• 相关代码：

 class Solution {
    public void reverseString(char[] s) {
          for(int i=0, j=s.length-1;i<j;i++,j--){
              char temp = s[i];
              s[i] = s[j];
              s[j] = temp;
          } 
    }
}