509. Fibonacci Number - Easy

悠悠 2021-10-29 12:30 218阅读 0赞

The Fibonacci numbers, commonly denoted `F(n)` form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from `0`and `1`. That is,

F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), for N > 1.

Given `N`, calculate `F(N)`.

Example 1:

Input: 2
    Output: 1
    Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: 3
    Output: 2
    Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: 4
    Output: 3
    Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Note:

0 ≤ `N` ≤ 30.

M1: recursion, time = O(2^n), space = O(n)

M2: dp, time = O(n), space = O(1)

class Solution {
        public int fib(int N) {
            if(N <= 1) {
                return N;
            }
            int f0 = 0, f1 = 1, f2 = f0 + f1;
            for(int i = 1; i < N; i++) {
                f2 = f0 + f1;
                f0 = f1;
                f1 = f2;
            }
            return f2;
        }
    }

转载于:https://www.cnblogs.com/fatttcat/p/11103082.html

发表评论取消回复

表情：

评论列表（有 0 条评论，218人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Easy - 263. Ugly Number

Topic Math Description [https://leetcode.com/problems/ugly-number/][https_leet

偏执的太偏执、/ 2023年01月09日 15:43/ 0 赞/ 181 阅读

相关 LeetCode - Easy - 268. Missing Number

Topic Array Math Bit Manipulation Description [https://leetcode.com/prob

小灰灰/ 2023年01月07日 08:46/ 0 赞/ 140 阅读

相关 LeetCode：509. Fibonacci Number斐波那契数（C语言）

题目描述：斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) =

ゞ浴缸里的玫瑰/ 2023年01月02日 01:30/ 0 赞/ 125 阅读

相关 LeetCode - Easy - 9. Palindrome Number

Topic Math Description [https://leetcode.com/problems/palindrome-number/][http

小咪咪/ 2023年01月01日 15:50/ 0 赞/ 137 阅读

相关 LeetCode - Easy - 202. Happy Number

Topic Math Hash Table Description [https://leetcode.com/problems/happy-numb

╰+攻爆jí腚メ/ 2022年12月30日 13:37/ 0 赞/ 113 阅读

相关 LeetCode - Easy - 193. Valid Phone Numbers

Topic Bash Description [https://leetcode.com/problems/valid-phone-numbers/][ht

傷城~/ 2022年12月30日 08:16/ 0 赞/ 121 阅读

相关 UESTC 87 Easy Problem With Numbers

Description Give a sequence of integers, you are required to deal with the following

约定不等于承诺〃/ 2022年08月09日 02:26/ 0 赞/ 132 阅读

相关 PDSOJ 1048 Fibonacci Numbers(大数)

[Fibonacci Numbers][] 时间限制: 1 Sec 内存限制: 128 MB 提交: 13 解决: 2 \[ [提交][Link 1]\]

淡淡的烟草味﹌/ 2022年06月17日 00:49/ 0 赞/ 136 阅读

相关 Colossal Fibonacci Numbers! UVA - 11582

Think: 1知识点:快速乘+数学规律+取模知识+64位无符号整数与64位有符号整数范围 (有符号型64位整数，值域为：-9223372036854775808 ..

偏执的太偏执、/ 2022年06月15日 03:23/ 0 赞/ 116 阅读

相关 509. Fibonacci Number - Easy

The Fibonacci numbers, commonly denoted `F(n)` form a sequence, called the Fibonacci seq

悠悠/ 2021年10月29日 12:30/ 0 赞/ 219 阅读