LeetCode-509-斐波那契数
source link: https://segmentfault.com/a/1190000040782340
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode-509-斐波那契数
斐波那契数
解法一:递归法题目描述:斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
- F(0) = 0,F(1) = 1
- F(n) = F(n - 1) + F(n - 2),其中 n > 1
给你 n ,请计算 F(n) 。
示例说明请见LeetCode官网。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法二:迭代法当n小于2时,直接返回n,当n大于2时,通过公式
F(n) = F(n - 1) + F(n - 2)
递归调用当前方法并返回。
当n小于2时,直接返回你,当n大于2时,通过迭代的方式计算当前值,具体过程如下:
- 记录当前的值的前2位的值是lastSecond,记录当前的值的前1位的值是lastOne;
- 然后从2开始遍历,一直到n;
- 具体过程是将lastOne更新为
lastSecond + lastOne
,lastSecond更新为 之前的值;最后返回lastOne的值即为当前值。
/** * @Author: ck * @Date: 2021/10/3 10:33 上午 */ public class LeetCode_509 { /** * 递归 * * @param n * @return */ public static int fib(int n) { if (n < 2) { return n; } return fib(n - 1) + fib(n - 2); } /** * 迭代 * * @param n * @return */ public static int fib2(int n) { if (n < 2) { return n; } int lastOne = 1, lastSecond = 0; for (int i = 2; i <= n; i++) { int temp = lastSecond + lastOne; lastSecond = lastOne; lastOne = temp; } return lastOne; } public static void main(String[] args) { System.out.println(fib(4)); System.out.println(fib2(4)); } }
【每日寄语】 把机遇留给朋友,把幸运留给亲人,把勤奋留给自己。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK