Fibonacci number

Fibonacci numbers, usually denoted by F(n), form a sequence called the Fibonacci sequence. The sequence starts with 0 and 1, and each successive digit is the sum of the preceding two. That is:

  • F of 0 is 0, F of 1 is 1
  • F(n) = F(n-1) + F(n-2), where n is greater than 1

I give you n, please calculate F(n).

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/fi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: recursive method

When n is less than 2, return n directly, when n is greater than 2, recursively call the current method by the formula F(n) = F(n-1) + F(n-2) and return.

Solution two: iterative method

When n is less than 2, it returns you directly. When n is greater than 2, it calculates the current value iteratively. The specific process is as follows:

  • The first 2 bits of the current value are lastSecond and the first 1 bit of the current value is lastOne;
  • And then you go from 2 to n;
  • The specific process is tolastOneUpdated tolastSecond + lastOne.lastSecondUpdated toBefore the value of the;

LastOne is returned as the current value.

/ * * *@Author: ck
 * @Date: 2021/10/3 10:33 上午
 */
public class LeetCode_509 {
    /** * recursively **@param n
     * @return* /
    public static int fib(int n) {
        if (n < 2) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }

    /** * iteration **@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)); }}Copy the code

Leave opportunities to friends, luck to relatives, and diligence to yourself.