建站公司杭州,营销网址,如何查一个网站的备案,静宁门户网站目录 70#xff1a;爬楼梯
题目要求#xff1a;
解题思路#xff1a;#xff08;类似斐波那契数#xff09;
递归解法#xff1a;
非递归解法#xff1a;
126#xff1a;斐波那契数
题目要求#xff1a;
解题思路#xff1a;
递归解法#xff1a;
非递归解…目录 70爬楼梯
题目要求
解题思路类似斐波那契数
递归解法
非递归解法
126斐波那契数
题目要求
解题思路
递归解法
非递归解法
都看到这了点个赞再走呗谢谢谢谢谢 70爬楼梯 题目要求 解题思路类似斐波那契数 递归解法 由题可知每次可以爬1个或者2个台阶假如有n个台阶会有多少种走法那么我们就想第一次爬一个台阶那方法数就是爬这一次台阶加上剩下n-1个台阶的走法爬两个台阶那方法数就是爬完这两个台阶再加上剩下n-2个台阶的走法很容易就想到递归的解法了而使用递归我们要找到终止条件也要写出递归公式 但是这么递归的时间复杂度很高LeetCode上通过不了会有很多重复计算的斐波那契数我们可以用HashMap来解题每次往下找之前都记录一下map里面有没有n这个斐波那契数有就不用继续往下找了直接返回这个斐波那契数没有就继续往下找有了HashMap的引用我们时间复杂度就变成了O(N)在LeetCode上也就能通过了。 递归公式如下 代码如下 class Solution {HashMapInteger, Integer hashmap new HashMap();public int climbStairs(int n) {if(n 1) {return 1;}if(n 2) {return 2;}//每次递归都判断map有没有n个台阶爬楼梯方法数没有算出当前n阶台阶的方法数放进map里放进map里后就不用继续往下递归了直接返回这个方法数因为hashmap已经存了n阶台阶的方法数了有就不用继续递归了直接返回n台阶的方法数if(hashmap.get(n) ! null) {return hashmap.get(n);} else {int result climbStairs(n - 1) climbStairs(n - 2);hashmap.put(n, result);return result;}}
} 非递归解法 从此图我们可以看出要求n的斐波那契数必须求前一个和前两个的斐波那契数也就是上图的公式非递归的解法我们就用循环来解决从下至上来求n的斐波那契数我们定义一个pre和prePre变量来记录前一个和前两个的斐波那契数result来记录n的斐波那契数每循环一次都要更改pre和prePre的下标时间复杂度为O(N). 代码如下 public int climbStairs(int n) {//非递归思想if(n 1) {return 1;}if(n 2) {return 2;}int result 0;int pre 2;int prePre 1;for(int flg 3; flg n; flg) {result pre prePre;//pre和prePre都要往前推prePre pre;pre result;}return result;} 126斐波那契数 题目要求 解题思路 这题和爬楼梯思路一样解法也一样递归和非递归也一样不过他的递归公式和结束条件和爬楼梯不一样公式如下图 递归思路因为递归会重复计算很多次所以我们可以用一个HashMap来记录n的斐波那契数每递归一次都判断map里面有没有n的斐波那契数有就不用继续往下递归了直接返回这个斐波那契数没有就往下递归把1后面的斐波那契数列都记录在map中这样时间复杂度就是O(N)了LeetCode也能通过。 非递归思路用循环从下至上求得每个斐波那契数我们定义result放n的斐波那契数pre放n的前一个斐波那契数prePre放n的前两个斐波那契数每循环一次都要更新一次pre和prePre的下标往上走。 递归解法 代码如下 MapInteger, Integer map new HashMap();public int fib(int n) {if(n 0 || n 1) {return n;}if(map.containsKey(n)) {return map.get(n);}//n的斐波那契数不在map里int result (fib(n - 1) fib(n - 2)) % 1000000007;//int result (fib(n - 1) fib(n - 2));map.put(n, result);return result;} 非递归解法 public int fib(int n) {//非递归if(n 0 || n 1) {return n;}int result 0;int pre 1;int prePre 0;for(int i 2; i n; i) {result (pre prePre) % 1000000007;prePre pre;pre result;}return result;} 都看到这了点个赞再走呗谢谢谢谢谢
