(1)剑指Offer之斐波那契数列问题和跳台阶问题
一 斐波那契数列
题目描述:
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。
n<=39
问题分析:
可以肯定的是这一题通过递归的方式是肯定能做出来,但是这样会有一个很大的问题,那就是递归大量的重复计算会导致内存溢出。另外可以使用迭代法,用fn1和fn2保存计算过程中的结果,并复用起来。下面我会把两个方法示例代码都给出来并给出两个方法的运行时间对比。
示例代码:
采用迭代法:
int Fibonacci(int number) { if (number <= 0) { return 0; } if (number == 1 || number == 2) { return 1; } int first = 1, second = 1, third = 0; for (int i = 3; i <= number; i++) { third = first + second; first = second; second = third; } return third; }
采用递归:
public int Fibonacci(int n) { if (n <= 0) { return 0; } if (n == 1||n==2) { return 1; } return Fibonacci(n - 2) + Fibonacci(n - 1); }
运行时间对比:
假设n为40我们分别使用迭代法和递归法计算,计算结果如下:
- 迭代法
- 递归法
二 跳台阶问题
题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
问题分析:
正常分析法:
a.如果两种跳法,1阶或者2阶,那么假定第一次跳的是一阶,那么剩下的是n-1个台阶,跳法是f(n-1);
b.假定第一次跳的是2阶,那么剩下的是n-2个台阶,跳法是f(n-2)
c.由a,b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
d.然后通过实际的情况可以得出:只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
找规律分析法:
f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5, 可以总结出f(n) = f(n-1) + f(n-2)的规律。
但是为什么会出现这样的规律呢?假设现在6个台阶,我们可以从第5跳一步到6,这样的话有多少种方案跳到5就有多少种方案跳到6,另外我们也可以从4跳两步跳到6,跳到4有多少种方案的话,就有多少种方案跳到6,其他的不能从3跳到6什么的啦,所以最后就是f(6) = f(5) + f(4);这样子也很好理解变态跳台阶的问题了。
所以这道题其实就是斐波那契数列的问题。
代码只需要在上一题的代码稍做修改即可。和上一题唯一不同的就是这一题的初始元素变为 1 2 3 5 8.....而上一题为1 1 2 3 5 .......。另外这一题也可以用递归做,但是递归效率太低,所以我这里只给出了迭代方式的代码。
示例代码:
int jumpFloor(int number) { if (number <= 0) { return 0; } if (number == 1) { return 1; } if (number == 2) { return 2; } int first = 1, second = 2, third = 0; for (int i = 3; i <= number; i++) { third = first + second; first = second; second = third; } return third; }
三 变态跳台阶问题
题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
问题分析:
假设n>=2,第一步有n种跳法:跳1级、跳2级、到跳n级
跳1级,剩下n-1级,则剩下跳法是f(n-1)
跳2级,剩下n-2级,则剩下跳法是f(n-2)
......
跳n-1级,剩下1级,则剩下跳法是f(1)
跳n级,剩下0级,则剩下跳法是f(0)
所以在n>=2的情况下:
f(n)=f(n-1)+f(n-2)+...+f(1)
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2*f(n-1) 又f(1)=1,所以可得f(n)=2^(number-1)
示例代码:
int JumpFloorII(int number) { return 1 << --number;//2^(number-1)用位移操作进行,更快 }
补充:
java中有三种移位运算符:
- “<<” : 左移运算符,等同于乘2的n次方
- ">>" : 右移运算符,等同于除2的n次方
- ">>" 无符号右移运算符,不管移动前最高位是0还是1,右移后左侧产生的空位部分都以0来填充。与>>类似。
例:
int a = 16;
int b = a << 2;//左移2,等同于16 2的2次方,也就是16 4
int c = a >> 2;//右移2,等同于16 / 2的2次方,也就是16 / 4
欢迎关注我的微信公众号(分享各种Java学习资源,面试题,以及企业级Java实战项目回复关键字免费领取):
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Lucene7.2.1系列(三)查询及高亮
系列文章: Lucene系列(一)快速入门 Lucene系列(二)luke使用及索引文档的基本操作 Lucene系列(三)查询及高亮 一 准备 创建项目并添加Maven依赖 <dependency> <groupId>junit</groupId> <artifactId>junit</artifactId> <version>4.12</version> <scope>test</scope> </dependency> <!-- https://mvnrepository.com/artifact/org.apache.lucene/lucene-core --> <!-- Lucene核心库 --> <dependency> <groupId>org.apache.lucene</groupId> <artifactId>lucene-core</artifactId> <...
- 下一篇
(2)剑指Offer之二维数组查找和替换空格问题
一 二维数组查找 题目描述: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 问题解析: 这一道题还是比较简单的,我们需要考虑的是如何做,效率最快。这里有一种很好理解的思路: 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增, 因此从左下角开始查找,当要查找数字比左下角数字大时。右移 要查找数字比左下角数字小时,上移。这样找的速度最快。 示例代码: public boolean Find(int target, int [][] array) { //基本思路从左下角开始找,这样速度最快 int row = array.length-1;//行 int column = 0;//列 //当行数大于0,当前列数小于总列数时循环条件成立 while((row >= 0)&& (column< array[0].length)){ if(array[row][column] > target){ row--; }else if(arr...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS关闭SELinux安全模块
- 2048小游戏-低调大师作品
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Red5直播服务器,属于Java语言的直播服务器
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS7,8上快速安装Gitea,搭建Git服务器
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7