509. Fibonacci Number

三刷 07/2022

Version #1 Iterative DP

Time O(N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.

Memory Usage: 40.4 MB, less than 78.16% of Java online submissions for Fibonacci Number.

class Solution {

    public int fib(int n) {

        if (n < 2) {

            return n;

        }

        int prevprev = 0;

        int prev = 1;

        for (int i = 2; i <= n; i++) {

            int curr = prevprev + prev;

            prevprev = prev;

            prev = curr;

        }

        return prev;

    }

}

二刷 05/2022

Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.

Memory Usage: 38.9 MB, less than 93.34% of Java online submissions for Fibonacci Number.

class Solution {

    // Time O(n)

    // Space O(n) -> Space O(1)

    public int fib(int n) {

        if (n < 0) {

            return 0;

        }

        int[] res = new int[2];

        for (int i = 0; i <= n; i++) {

            if (i == 0 || i == 1) {

                res[i % 2] = i;

                continue;

            }

            // curr = prev + prevprev

            res[i % 2] = res[(i - 1) % 2] + res[(i - 2) % 2];

        }

        return res[n % 2];

    }

}

一刷

class Solution {

    /**

     * @param n: an integer

     * @return an integer f(n)

     */

    public int fibonacci(int n) {

        // write your code here

        /*

        if (n == 1) return 0;

        if (n == 2) return 1;

        return fibonacci(n - 2) + fibonacci(n - 1);

        */

        int lastlast = 0;

        int last = 1;

        int temp = 0;

        for (int i = 0; i < n - 1; i++) {

            temp = last + lastlast;

            lastlast = last;

            last = temp;

        }

        return lastlast;

    }

}