【剑指offer】10

本节目录

刷前点说题目介绍(link)思路/想法

1、初始思路/最终思路

迭代递归 2、注意点 迭代实现递归的代码实现（不推荐的，面试不要写这样的代码！）递归+不重复计算（推荐的写法 是微软的面试题）感谢语 刷前点说

以后的话，除了代码和想说的话，就会的剪短文章的长度，

因为在写文章上浪费了太多的是时间！

其实刷题是不难的，难的是坚持！

这个分栏是《剑指 offer》 的经典题目，

并在这个博客里记录自己的理解与学习过程！

题目介绍(link)

那关于题目的话，我就不做过多的介绍了，照抄的意义不大，我在这里直接贴链接了！

LeetCode链接：点击这里！

NowCoder链接：点击这里！

思路/想法 1、初始思路/最终思路

今天的题目是比较简单的，大家肯定都见过！

但是我想传递一个概念：剪枝重复计算的处理！

就是以前直接写递归方案的时候效率非常的低，那如何去解决呢？

就有了剪枝的策略！

到这里我会让大家知道实际递归的一些细节问题和时间的成本问题，并解决时间的成本问题！

迭代

要注意临界的问题，n == 1的时候直接return 1；，就可以！

剩下的就不写了，大家都会的，直接看下面的代码，不会的评论私信！

其实迭代的代码就是一个动态规划的代码，

只是可能是因为题目太简单了，大家体会不出来！

但是，这不是重点，重点是下面的递归！

递归

在之前学习C语言的时候，我写过一篇函数的文章里面提及了斐波那契数列递归的问题，大家可以先看看！

请务必看上面的文章后面的递归与迭代的部分，如果是大佬，当我没说，但是还是建议看一下，顺便别忘了点赞！

现在知道了斐波那契递归是非常的耗时间的，如果你OJ（NowCoder或者LeetCode）的时候写了这样的代码，直接会 “爆炸” 的！

我测试了一下，NowCode写成递归的时候竟然过了，我只能说，NowCoder的测试用例写的不好！

相比之下，LeetCode还是牛！

现在，我们要做的是如何降低消耗，解决大量的重复计算！

这里就可以使用Map进行相关的剪枝动作！

2、注意点

大家注意：LeetCode和NowCoder的题目有一点点小变动：

LeetCode后面的描述是这样的：答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

有一个好方法：取模的效率是比较低的，所以减法更简单的！

想不明白往下看：

求余比较耗时，可以采用减去1000000007，因为第一个大于1000000007的结果就减去1000000007了，所以永远不会出现大于等于2倍的1000000007的情况，这样对1000000007求余就退化为减去1000000007。

迭代实现

//NowCoder版本public class Solution { public int Fibonacci(int n) { if (0 == n) { return 0; } //下面的if语句是可以省略的，前提是third定义的时候要赋值为1，到后面返回的时候不管是第一次还是第二次都返回1 if (2 == n || 1 == n) { return 1; } int first = 1; int second = 1; int third = 0;// 第三个数初始化为0 // 这里要理解，从第三个数要迭代一次，以此类推条件就出来了 while (n > 2) { third = first + second; first = second; second = third; n--; } return third; }}

//LeetCode版本public class Solution { public int fib(int n) { if (0 == n) { return 0; } //下面的if语句是可以省略的，前提是third定义的时候要赋值为1，到后面的返回的时候不管是第一次还是第二次都返回1 if (2 == n || 1 == n) { return 1; } int first = 1; int second = 1; int third = 0;// 第三个数初始化为0 // 这里要理解，从第三个数要迭代一次，以此类推条件就出来了 while (n > 2) { third = first + second; //求余比较耗时，可以采用减去1000000007 if (third >= 1000000007) { third -= 1000000007; } first = second; second = third; n--; } return third; }}

递归的代码实现（不推荐的，面试不要写这样的代码！）

class Solution { public int Fibonacci(int n) { if (0 == n) { return 0; } if (n <= 2) { return 1; } return Fibonacci(n - 2) + Fibonacci(n - 1); }}

递归+不重复计算（推荐的写法 是微软的面试题）

//NowCoder版本import java.util.HashMap;import java.util.Map;public class Solution { private Map filter = new HashMap<>(); public int Fibonacci(int n) { if (n == 0 || n == 1) { return n; } int ppre = 0;// 第n-2个 if (filter.containsKey(n - 2)) { // 找到了 ppre = filter.get(n - 2); }else { // 没有找到就自己计算出来然后添加进去 ppre = Fibonacci(n - 2); filter.put(n-2, ppre); } int pre = 0;// 第n-1个 if (filter.containsKey(n - 1)) { // 找到了 pre = filter.get(n - 1); }else { // 没有找到就自己计算出来然后添加进去 pre = Fibonacci(n - 1); filter.put(n-1, pre); } return ppre + pre; }}

//LeetCode版本import java.util.HashMap;import java.util.Map;public class Solution { private Map filter = new HashMap<>(); public int fib(int n) { if (n == 0 || n == 1) { return n; } int ppre = 0;// 第n-2个 if (filter.containsKey(n - 2)) { // 找到了 ppre = filter.get(n - 2); }else { // 没有找到就自己计算出来然后添加进去 ppre = fib(n - 2); filter.put(n-2, ppre); } int pre = 0;// 第n-1个 if (filter.containsKey(n - 1)) { // 找到了 pre = filter.get(n - 1); }else { // 没有找到就自己计算出来然后添加进去 pre = fib(n - 1); filter.put(n-1, pre); } int result = ppre + pre; if (result >= 1000000007) { result -= 1000000007; } return result; }}

感谢语

是这样的，如果是关注我的大佬有可能发现，

我写的关于刷题的文章是由简单到难的。

现在仅仅就是一个开始，就是用的都是简单的算法，

而且这个算法会越来越难的，现在慢慢的就会在里面穿插一些算法思想：动态规划和回溯！

其实上过学的斐波那契数列大家都是见过的，那我阐述太多冗余的东西是很无聊的，

所以，我会通过这道题让大家理解空间复杂度，时间空间消耗带来的直观上的危害！

再次感谢大家的关注，你们的支持就是我的动力！