In this Leetcode Fibonacci Number problem solution 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).
Problem solution in Python.
class Solution: def fib(self, N: int) -> int: if N == 0: return 0 if N == 1: return 1 curr_n = 2 n_1 = 1 n_2 = 0 while N>=curr_n: ans = n_1 + n_2 n_2=n_1 n_1=ans curr_n+=1 return ans
Problem solution in Java.
public int fib(int N) {
if(N == 1) return 1;
if(N == 0) return 0;
return fib(N-1)+fib(N-2);
}
Problem solution in C++.
public: int fib(int N) { if(N < 2){ return N; } vector vals = {0, 1}; int i = 2; int sum = 1; while(i <= N){ sum = vals[i-1] + vals[i-2]; vals.push_back(sum); i++; } return sum; } };
Problem solution in C.
int calculate_fib(int N, int *cache) { if (N == 1 || N == 0) return (N); if (cache[N - 1] != 0) return (cache[N - 1]); cache[N - 1] = calculate_fib(N - 1, cache) + calculate_fib(N - 2, cache); return (cache[N - 1]); } int fib(int N){ int *cache; int r; int i; i = -1; cache = (int *)malloc(sizeof(int) * N); while (++i < N) cache[i] = 0; r = calculate_fib(N, cache); free(cache); return (r); }
0 Comments