白色网站源码,网络运营商自动选择,乐都企业网站建设公司,wordpress音乐页面下载【问题描述】
大家都知道斐波那契数列#xff0c;现在要求输入一个整数n#xff0c;请你输出斐波那契数列的第n项#xff08;从0开始#xff0c;第0项为0#xff09;。 n39
【解答思路】
1.递归#xff08;面试避免#xff09; O(n^2) public class Solution {pu…【问题描述】
大家都知道斐波那契数列现在要求输入一个整数n请你输出斐波那契数列的第n项从0开始第0项为0。 n39
【解答思路】
1.递归面试避免 O(n^2) public class Solution {public int Fibonacci(int n) {if (n 0) return 0;if (n 1) return 1;return Fibonacci(n - 1) Fibonacci(n - 2);}
}2.一般循环 O(n) 空间复杂度O(n)
public class Solution {public int Fibonacci(int n) {int ans[] new int[40];ans[0] 0;ans[1] 1;for(int i2;in;i){ans[i] ans[i-1] ans[i-2];}return ans[n];}
}3.循环优化 O(n) 空间复杂度O(1)
0 1 1 2 3 5 8 f(6) f(5) f(4)只需要保存f(5) f(4) 由f(5) -f(3) 得出 计算8 53时只需要保存5 3由5-2得出 public class Solution {public int Fibonacci(int n) {int a 0, b 1;for (int i 1; i n - 2; i) {a a b;b a - b;}return a;}
}【总结】
递归需要定义出口从传递的参数过渡到出口综合考虑时间复杂度和空间复杂度
