【剑指offer】7.斐波那契数列
Offer 数列 斐波 那契
2023-09-11 14:20:18 时间
/**
*题目描述:
*大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。
*n<=39
*/
import java.util.ArrayList;
public class Solution {
//方法一:循环
public int Fibonacci(int n) {
int preNum=1;
int prePreNum=0;
int result=0;
if(n==0)
return 0;
if(n==1)
return 1;
for(int i=2;i<=n;i++){
result=preNum+prePreNum;
prePreNum=preNum;
preNum=result;
}
return result;
}
//方法二:递归
public int Fibonacci1(int n) {
return Fibonacci1(n,0,1);
}
public int Fibonacci1(int n,int acc1,int acc2){
if(n==0)
return 0;
if(n==1)
return acc2;
else
return Fibonacci1(n - 1, acc2, acc1 + acc2);
}
//尽量不用递归,如果数很大时,会很耗时
public static void main(String[] args) {
Solution s=new Solution();
System.out.println(s.Fibonacci(35));
System.out.println(s.Fibonacci1(35));
}
}
/*
Fibonacci(4) = Fibonacci(3) + Fibonacci(2);
= Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
= Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
*/
相关文章
- 【剑指offer】删除链表中重复的结点
- 剑指Offer题解(Python版)
- (剑指Offer)面试题14:调整数组顺序使奇数位于偶数前面
- (剑指Offer)面试题56:链表中环的入口结点
- (剑指Offer)面试题32:从1到n整数中1出现的次数
- (剑指Offer)面试题14:调整数组顺序使奇数位于偶数前面
- 剑指 Offer II 119. 最长连续序列
- 剑指 Offer 32 - II. 从上到下打印二叉树 II
- [剑指Offer] 第5章课后题详解
- 剑指 Offer II 118. 多余的边-记忆搜索深度优先遍历
- 剑指 Offer II 093. 最长斐波那契数列-哈希表法
- 剑指 Offer II 038. 每日温度-单调栈
- 【Leetcode刷题Python】剑指 Offer 04. 二维数组中的查找
- 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- 剑指 Offer 47. 礼物的最大价值
- 【LeetCode】剑指 Offer 29. 顺时针打印矩阵
- 【剑指 Offer 40】最小的k个数 【LeetCode】