Leetcode剑指Offer刷题指南：

Leetcode剑指Offer刷题-学习计划目录_DEGv587的博客-CSDN博客

剑指 Offer 10- I. 斐波那契数列 

解法：动态规划，如果用递归会超时）

注意：题内有要求 --> 答案需要取模 1e9+7（1000000007）

class Solution {
    public int fib(int n) {
        if (n <= 0) return n;
        int first = 0;
        int second = 1;
        while (n > 1) {
            second += first;
            first = second - first;
            second %= 1000000007;
            n--;
        }
        return second;
    }
}

剑指 Offer 10- II. 青蛙跳台阶问题

解法：动态规划（和上一道题一样）

注意：题内有要求 --> 答案需要取模 1e9+7（1000000007）

class Solution {
    public int numWays(int n) {
        if (n == 1 || n == 0) return 1;
        int first = 1;
        int second = 1;
        while (n > 1) {
            second += first;
            first = second - first;
            second %= 1000000007;
            n--;
        }

        return second;
    }
}

剑指 Offer 63. 股票的最大利润

解法一：暴力循环

class Solution {
    public int maxProfit(int[] prices) {
        int ret = 0;

        for (int i = 0; i < prices.length; ++i) {
            for (int j = i; j < prices.length; ++j) {
                int tmp = prices[j] - prices[i];
                ret = Math.max(tmp, ret);
            }
        }
        return ret;
    }
}

解法二：一次遍历，维护最小数和差值

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int ret = 0, min = prices[0];
        for (int i = 1; i < prices.length; ++i) {
            if (prices[i] <= min) {
                min = prices[i];
            } else {
                ret = Math.max(ret, prices[i] - min);
            }
        }

        return ret;
    }
}