剑指 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。
题目链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof

方法一：递归

递归，但在本题可能因为取余操作的存在会导致超时 
class Solution {
    public int fib(int n) {
        if(n <= 1){
            return n;
        }
        return (fib(n-1) + fib(n-2)) % 1000000007;
    }
}

方法二：迭代

按规律迭代，0 1 1 2 3 5...，注意要对每次的循环的结果进行取余，只对最终结果取余的话可能导致结果越界 
class Solution {
    public int fib(int n) { //按规律迭代，0 1 1 2 3 5...
        if(n <= 1){
            return n;
        }
        int n1 = 0;
        int n2 = 1;
        for(int i = 2; i <= n; i++){
            n2 = n1 + n2;
            n1 = n2 - n1;
            n2 %= 1000000007;
        }
        return n2;
    }
}

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

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
题目链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof

思路

根据题意可知，跳台阶的跳法规律为：1 1 2 3 5...符合斐波那契数列的规律，但又有所不同，如n=0时为1

实现代码 

class Solution {
    public int numWays(int n) { 
        if(n <= 1){
            return 1;
        }
        int n1 = 1;
        int n2 = 1;
        for(int i = 2; i <= n; i++){
            n2 = n1 + n2;
            n1 = n2 - n1;
            n2 %= 1000000007;
        }
        return n2;
    }
}

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

题目描述

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

思路

动态规划，维护一个当前位置之前的最小买入价格的数组，遍历价格数组，将当前价格作为卖出价格得到当前位置的最大利润

实现代码 

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0){
            return 0;
        }
        int length = prices.length;
        int max = 0;
        int[] dp = new int[length];
        dp[0] = prices[0];
        for(int i = 1; i < length; i++){
            //当前价格-前面出现的最小买入价格得到当前卖出的最大利润
            max = Math.max(max, prices[i] - dp[i-1]);
            dp[i] = Math.min(dp[i-1], prices[i]); //维护当前位置前出现的最小买入价格
        }
        return max;
    }
}