取自牛客网,剑指Offer编程题
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
首先分析一下为啥是一个斐波拉契序列
对于第N级阶梯,他的情况有下列两种:
第一种是在n-2级的时候.跨两步到达n,此时有f(n-2)种跳法
第二种是在n-1级的时候,跨一步到达n,此时有f(n-1)种跳法
所以,第n级的跳法就有f(n-2)+f(n-1)种,很容易看来是斐波拉契了吧,虽然我第一眼看了很久不知道为啥是斐波拉契...
对于变态跳台阶:
他跟普通版的区别就是青蛙可以跳小于n的任意步,然后问题其实跟之前一样
这里f(n)可以表示为f(n-1)+f(n-2)+......+f(n-n);
f(n-1)可以表示为f(n-2)+f(n-3)+......+f(n-n);
这样化解,就成了f(n) = 2 * f(n-1)
这样,问题就迎刃而解了,做法就跟下面类似,就不赘述了
再说解法
第一:递归
是最常见最普通同时也是最慢的方法了吧,因为这个过程中会产生大量的重复计算
代码贴上来
public static int Fibonacci(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
if (n==2)
return 2;
return Fibonacci(n-1)+Fibonacci(n-2);
}
我这里跑了530ms,太慢了,且看第二种
第二种:存中间结果
既然会产生重复计算,那么从这里出发,我们把中间计算过的都存起来,每次计算的时候只要取出来就行
这样就能节省大量时间
代码:
import java.util.Arrays;
public class Solution {
private int[] temp = new int[1000];//存放中间结果的数组
public Solution(){
Arrays.fill(temp,-1);//所有元素初始化为-1
}
public int JumpFloor(int target) {
if (target==0)
return 0;
if (target==1)
return 1;
if (target==2)
return 2;
if(temp[target]>0)
return temp[target];//直接返回
else
temp[target] = JumpFloor(target-1)+JumpFloor(target-2);
return temp[target];
}
}
这段跑了22ms
第三种:迭代,速度跟第二种差不多,稍微快一丢丢
这里的思路就是计算的时候每次更新n-1和n-2级的跳法,也是避免重复计算
import java.util.Arrays;
public class Solution {
public int JumpFloor(int target) {
int[] n = {0,1,2};
if (target<=2)
return n[target];
int pre = 1;//f(n-2)
int in = 2;//f(n-1)
int after = 0;//f(n)
for (int i = 3;i<=target;i++){
after = pre+in;
pre = in;
in = after;
}
return after;
}
}
跑了20ms,比前面快一点
听说还有一种矩阵快速幂,我还不是很会,待会研究研究
好了,研究矩阵快速幂回来了
首先总结一下学习快速幂
首先,我们从指数出发,将指数转化而二进制,比如二的十次方,我们都知道答案是1024
那么快速幂的思想就是,10转化为1010,那么就是0+2+0+8,按照幂来化简,就是2^0 * 2^2 * 2^0 * 2^8
然后,1010是怎么来的,根据短除法就是10不停除二得到的,好了,快速幂的精髓地方就到了,我们不停除二得到了
一些二进制的数字,说明白点就是取余吧,如果这个余数是0,那么我们就不用计算,但是底数还是照样累乘,然后没
取余一次,因为要往后接着判断余数,所以b就缩小为以前的一半,然后,如果余数为1,就就与答案相乘
不懂还是看代码吧,就明白了
//快速幂
public static long fastPower(int a,int b){
long answer = 1;
while (b>0){
if(b%2==1)
answer = answer * a;
b = b/2;
a = a * a;
}
return answer;
}
这里b每次除二,所以最终计算的次数是肯定要小了很多了,如果指数很大,就更明显了
然后转到矩阵快速幂,矩阵快速幂怎样跟斐波拉契联系起来呢,其实跟之前的快速幂相似,不过是以矩阵的形式
可以参考下面的连接:https://www.cnblogs.com/ranjiewen/p/8998112.html
定义一个初始矩阵int[][] base = {{1,1},{1,0}};单位矩阵int[][] answer = {{1,0},{0,1}};
所以f(n) = base^(n-1)*answer[0][1]
还是看代码吧,不难理解
/*矩阵快速幂学习*/
//2X2矩阵相乘
public static int[][] Matrix(int[][] a,int[][] b){
int[][] temp = {{0,0},{0,0}};
for (int i = 0;i < 2;i++)
for (int j = 0;j < 2;j++)
for (int k = 0;k < 2;k++)
temp[i][j] += a[i][k]*b[k][j];
return temp;
}
//矩阵快速幂解斐波拉契
public static int Fibonacci(int n){
//初始化A
int[][] base = {{1,1},{1,0}};
//answer初始化为单位矩阵
int[][] answer = {{1,0},{0,1}};
while (n>0){
if(n%2==1)
answer = Matrix(answer,base);
base = Matrix(base,base);
n = n /2;
}
return answer[0][0];
}