网站首页 / 精品软件 / 正文
welcome to my blog
剑指offer面试题牛客_递归和循环_跳台阶(java版):
题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
思路
- 设f(n)表示跳上n阶台阶的跳法数量, 因为青蛙一次能跳一阶或者两阶, 所以f(n)和f(n-1),f(n-2)满足递归关系式: f(n) = f(n-1) + f(n-2)
- 可以使用递归函数求解, 递归函数的逻辑: 计算跳上n阶台阶的跳法数量
- 递归终止条件, 跳上1阶时,返回1; 跳上2阶时返回2
- 使用递归函数求解是自顶向下的求解方式, 会产生很多重复计算, 可以使用循环替代递归函数, 循环是自底向上的, 可以利用已有的结果, 从而避免重复计算
递归版
public class Solution {
public int JumpFloor(int target) {
/*
思路: 设f(n)是跳上n级台阶的跳法, 青蛙一次能跳一阶或者两阶, 所以有f(n) = f(n-1) + f(n-2)
很明显,可以用递归. 递归终止条件f(1)=1, f(2)=2, f(3)=f(2)+f(1)=3
递归函数的逻辑: 计算跳上n阶台阶的跳法数量
*/
if(target == 1) return 1;
if(target == 2) return 2;
return JumpFloor(target-1) + JumpFloor(target-2);
}
}
循环版(推荐, 因为避免了很多重复计算)
public class Solution {
public int JumpFloor(int target) {
//input check
if(target <=0) return 0;
//execute
if(target == 1) return 1;
if(target == 2) return 2;
// 使用数组表示跳上i阶台阶的跳法数量
int[] arr = new int[target+1];
arr[1] = 1;
arr[2] = 2;
for(int i=3; i<= target; i++){
arr[i] = arr[i-1] + arr[i-2];
}
return arr[target];
}
}
Tags:
猜你喜欢
你 发表评论:
欢迎- 控制面板
- 搜索
- 文章归档
-
- 2020年7月 (1)
- 2019年12月 (2)
- 2019年11月 (2)
- 2019年10月 (3)
- 2019年9月 (17)
- 2019年8月 (14)
- 2019年7月 (45)
- 2019年6月 (153)
- 2019年5月 (3)
- 2019年4月 (6)
- 2019年3月 (3)
- 2019年2月 (2)
- 2019年1月 (5)
- 2018年12月 (40)
- 2018年11月 (57)
- 2018年10月 (29)
- 2018年9月 (41)
- 2018年8月 (9)
- 2018年7月 (4)
- 2018年6月 (5)
- 2018年5月 (1)
- 2018年4月 (19)
- 2018年3月 (11)
- 2018年2月 (11)
- 2018年1月 (2)
- 2017年12月 (1)
- 2017年9月 (4)
- 2017年7月 (1)
- 2017年1月 (1)
- 2016年7月 (1)
- 2014年10月 (1)
- 2014年8月 (1)
- 2013年8月 (1)
- 2013年5月 (1)
- 2013年4月 (1)
- 2013年1月 (2)
- 2012年12月 (4)
- 2012年11月 (1)
- 2012年10月 (1)
- 2012年8月 (3)
- 2012年6月 (5)
- 2012年5月 (2)
- 2012年3月 (1)
- 2012年1月 (2)
- 2011年10月 (15)
- 2011年9月 (4)
- 2010年5月 (1)
- 2009年12月 (1)
- 2009年8月 (1)
- 2008年10月 (1)
本文暂时没有评论,来添加一个吧(●'◡'●)