[剑指Offer] Day 08

题目来源：剑指 Offer 10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1

解题思路：动态规划+滚动窗口。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int fib(int n) {
        int p = 0;
        int q = 1;
        int ans = 0;
        final int MOD = 1000000007;
        if (n < 2) return n;
        while (n > 1) {
            ans = (p + q)% MOD;
            p = q;
            q = ans;
            n--;
        }
        return ans;

    }
}

题目来源：剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

解题思路：思路同上一题，动态规划+滚动窗口。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int numWays(int n) {
        final int MOD = 1000000007;
        if (n == 0) return 1;
        if (n < 3) return n;
        int p = 1;
        int q = 2;
        int ans = 0;
        while (n > 2) {
            ans = (p + q) % MOD;
            p = q;
            q = ans;
            n--;
        }
        return ans;
    }
}

题目来源：剑指 Offer 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

解题思路：维护一个最低价格，维护一个最大获利值。遍历整个数组，若价格高于最小值，则判断获利是否大于之前的最大获利；若当前价格小于之前维护的最小价格，则更新最小价格。最后返回最大获利。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0 ) return 0;
        int min = prices[0];
        int profit = 0;
        for (int price : prices) {
            if (price > min){
                profit = Math.max(profit, price - min);
            } else {
                min = price;
            }
        }
        return profit;

    }
}