剑指Offer - 面试题10- I. 斐波那契数列
发布日期:2021-07-01 03:20:07
浏览次数:2
分类:技术文章
本文共 1842 字,大约阅读时间需要 6 分钟。
文章目录
1. 题目
写一个函数,输入 n
,求斐波那契(Fibonacci
)数列的第 n
项。斐波那契数列的定义如下:
F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由0和1开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:输入:n = 2输出:1示例 2:输入:n = 5输出:5提示:0 <= n <= 100
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。2. DP解题
class Solution { public: int fib(int n) { if(n <= 1) return n; int i = 2, a = 0, b = 1, sum; while(i <= n) { sum = (a + b)%1000000007; a = b; b = sum; i++; } return sum; }};
3. 面试题 08.01. 三步问题
三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。
示例1: 输入:n = 3 输出:4 说明: 有四种走法 示例2: 输入:n = 5 输出:13 提示:n范围在[1, 1000000]之间
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/three-steps-problem-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。class Solution { public: int waysToStep(int n) { if(n==1) return 1; if(n==2) return 2; if(n==3) return 4; vectordp(n+1,0); dp[1] = 1, dp[2] = 2, dp[3] = 4; for(int i = 4; i <= n; ++i) dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%1000000007; return dp[n]; }};
4. LeetCode 509. 斐波那契数
斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。
该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.给定 N,计算 F(N)。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/fibonacci-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution { public: int fib(int N) { if(N <= 1) return N; int a = 0, b = 1, sum; for(int i = 2; i <= N; ++i) { sum = a + b; a = b; b = sum; } return sum; }};
0 ms 8.1 MB
转载地址:https://michael.blog.csdn.net/article/details/104272616 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年05月02日 22时09分33秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
odoo10学习笔记十一:视图综述
2019-05-02
commons-dbutils【不推荐】
2019-05-02
SOCAT端口转发
2019-05-02
docker快速搭建HTTP代理
2019-05-02
jpa的entry审查Auditing
2019-05-02
mongdb查询笔记
2019-05-02
facebook区块链libra测试网体验
2019-05-02
Java面向对象三巨头
2019-05-02
前端学习 -- Css -- 属性选择器
2019-05-02
Python 日期和时间
2019-05-02
前端学习 -- 长度单位
2019-05-02
前端学习 -- Css -- 定义列表
2019-05-02
前端学习 -- Css -- 字体
2019-05-02
前端学习 -- 颜色
2019-05-02
前端学习 -- Css -- 字体的几个属性学习
2019-05-02
前端学习 -- Css -- 字体分类
2019-05-02
Shell脚本学习
2019-05-02
前端学习 -- Css -- 行间距
2019-05-02
前端学习 -- Css -- 文本样式
2019-05-02
前端学习 -- Css -- 盒子模式
2019-05-02