leetcode题目70爬楼梯

第70题是著名的斐波那契数列，正常思路一开始都是迭代

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

上述方法只用迭代超出时间限制，因为里面存在重复计算问题

面试时，面试官一般让你用迭代循环来代替递归，减少重复计算

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

上述方法执行用时很少，也可以在迭代中引入哈希表，也能解决重复计算问题

//unordered_map  内部实现了一个哈希表，因此元素的排列顺序是杂乱无序的

//优点：内部实现了哈希表，因此查找速度非常快

//缺点：哈希表的建立时间比较耗时

//适用性：对于查找问题更加高效。


class Solution{
public:
    unordered_map<int,int> mp;
    int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;

        auto it = mp.find(n);  //查找元素中是否存在n
        if( it != mp.end() )
            return it->second;//如果有，返回值

        int sum = climbStairs(n-1) + climbStairs(n-2);//如果没有计算出值
        mp.insert(pair<int, int> (n, sum));   //将计算出的值插入哈希表
        return sum;
    }
};

最后

以上就是诚心铃铛为你收集整理的leetcode题目70爬楼梯的全部内容，希望文章能够帮你解决leetcode题目70爬楼梯所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。