leetcode 70.爬楼梯（c++详细最全解法+补充知识）

目录

题目

解答过程

补充哈希表知识

哈希表基本特性

常用成员函数

基本用法

实现代码

1.递归

2.循环遍历

3.哈希表

---

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

解答过程

递归方法很简单可以想到。首先要列出关系式:

f(1)=1,f(2)=2

f(n)=f(n-1)+f(n-2) n≥3

公式解释：如果只有一阶台阶，只有一种走法。如果两阶台阶，有1+1和2两种走法。有3种及以上个台阶，那么分以下两种情况，将两者进行相加，即为最终结果。

• 当你第一步走一个台阶，剩余的是f(n-1)种走法
• 当你第一步走两个台阶，剩余的是f(n-2)种走法

非循环方法：

方法一：就是利用两个变量循环进行保存前一个结果pre，和前面第二个结果prePre。还需要一个变量用来记录结果result。遍历内部核心部分代码如下：

result=pre+prePre;

prePre=pre;

pre=result;

方法二：使用哈希表进行存储所有的结果。

hashmap[i]=hashmap[i-1]+hashmap[i-2];

补充哈希表知识

unordered_map 是 C++ STL 中的关联容器，基于哈希表实现，提供快速的键值对查找功能。

哈希表基本特性

• 存储键值对（key-value pairs）

• 基于哈希表实现，平均情况下查找、插入、删除操作的时间复杂度为 O(1)

• 元素无序存储（与 map 的有序存储相对）

• 需要包含头文件 <unordered_map>

常用成员函数

• insert(): 插入键值对

• erase(): 删除元素

• find(): 查找元素

• count(): 统计特定键的数量（0或1，因为键唯一）

• size(): 返回元素数量

• empty(): 判断是否为空

• clear(): 清空容器

基本用法

#include <iostream>
#include <unordered_map>
#include <string>int main() {// 创建 unordered_mapstd::unordered_map<std::string, int> ageMap;// 插入元素ageMap["Alice"] = 25;ageMap["Bob"] = 30;ageMap.insert({"Charlie", 28});// 访问元素std::cout << "Alice's age: " << ageMap["Alice"] << std::endl;// 检查元素是否存在if (ageMap.find("David") == ageMap.end()) {std::cout << "David not found" << std::endl;}// 遍历元素for (const auto& pair : ageMap) {std::cout << pair.first << ": " << pair.second << std::endl;}// 删除元素ageMap.erase("Bob");return 0;
}

实现代码

1.递归

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

但是递归方法会显示超出时间限制，提交会失败

2.循环遍历

class Solution {
public:int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;int result=0;int prePre=1;int pre=2;for(int i=3;i<=n;i++){result=pre+prePre;prePre=pre;pre=result;}return result;}
};

3.哈希表

class Solution {
public:int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;unordered_map<int,int> hashmap;hashmap[1]=1;hashmap[2]=2;for(int i=3;i<=n;i++){hashmap[i]=hashmap[i-1]+hashmap[i-2];}return hashmap[n];}
};