剑指 Offer 10- I. 斐波那契数列
2022/1/13 23:34:59
本文主要是介绍剑指 Offer 10- I. 斐波那契数列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
509. 斐波那契数
import java.util.Scanner; class Solution { private static final int MOD = 1000000007; private int[][] multiply(int[][] a, int[][] b) { int[][] ans = new int[a.length][b[0].length]; for (int i = 0; i < a.length; ++i) { for (int j = 0; j < b[0].length; ++j) { for (int k = 0; k < a[0].length; ++k) { ans[i][j] = (ans[i][j] + (int) (1L * a[i][k] * b[k][j] % MOD)) % MOD; } } } return ans; } public int fib(int n) { int[][] base = { {1, 1}, {1, 0} }; int[][] ret = {{1, 0}}; while (n > 0) { if ((n & 1) == 1) { ret = multiply(ret, base); } base = multiply(base, base); n >>= 1; } return ret[0][1]; } public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { System.out.println(new Solution().fib(in.nextInt())); } } }
这篇关于剑指 Offer 10- I. 斐波那契数列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现