[剑指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;

    }
}
展示评论