《剑指offer》– 斐波那契数列、跳台阶问题 、变态跳台阶问题、矩阵覆盖

《剑指offer》– 斐波那契数列、跳台阶问题 、变态跳台阶问题、矩阵覆盖

一、斐波那契数列:

1、题目:
现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0).n<=39。

2、什么是斐波那契数列?

斐波那契数列指的是这样一个数列: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ……,可以观察到,从第3个数开始,每个数的值都等于前连个数之和。

3、解题思路:

这里可以使用递归的方法实现,但是递归的方式的时间复杂是输入规模的指数级别,不建议使用,因此这里采用迭代的方法实现。

4、代码实现:

	 public static int Fibonacci(int n) {
		    if(n<=0){
		        return 0;
		    }
		    
		    int first,second,result;
		    first=0;second=1;result=1;
		    if(n==1){
		        return n;
		    }      
		    for(int i=2;i<=n;i++){
		        result=first+second;
		        first=second;
		        second=result;
		    }       
		    return result;
		}

 

二、跳台阶问题:

1、题目:

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

2、解题思路:

(1)可以考虑,小青蛙每一步跳跃只有两种选择:一是再跳一级阶梯到达第 i 级阶梯,此时小青蛙处于第 i-1 级阶梯;或者再跳两级阶梯到达第 i 级阶梯,此时小青蛙处于第 i-2 级阶梯。

(2)于是,i级阶梯的跳法总和f(i)依赖于前 i-1 级阶梯的跳法总数f(i-1)和前 i-2 级阶梯的跳法总数f(i-2)。因为只有两种可能性,所以,f(i)=f(i-1)+f(i-2);

(3)通过上面的分析,我们可以很清晰地看到,这其实就是一个Fibonacci数列。

3、代码实现:

public int JumpFloor(int target) {
        if(target<1){
            return 0;
        }else if(target<2){
            return target;
        }else{
             int first=0,second=1,result=1;
             for(int i=2;i<=target;i++){
                 first=second;
                 second=result;
                 result=first+second;
             }
            return result;
        }      
    }

 

三、变态跳台阶问题:

本部分参考博客:https://blog.csdn.net/friendbkf/article/details/50060239

1、题目:

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法?

2、问题分析:

分析:用Fib(n)表示跳上n阶台阶的跳法数。如果按照定义,Fib(0)肯定需要为0,否则没有意义。但是我们设定Fib(0) = 1;n = 0是特殊情况,通过下面的分析就会知道,强制令Fib(0) = 1很有好处。ps. Fib(0)等于几都不影响我们解题,但是会影响我们下面的分析理解。

当n = 1 时, 只有一种跳法,即1阶跳:Fib(1) = 1;

当n = 2 时, 有两种跳的方式,一阶跳和二阶跳:Fib(2)  = 2;

到这里为止,和普通跳台阶是一样的。

当n = 3 时,有三种跳的方式,第一次跳出一阶后,对应Fib(3-1)种跳法; 第一次跳出二阶后,对应Fib(3-2)种跳法;第一次跳出三阶后,只有这一种跳法。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;

当n = 4时,有四种方式:第一次跳出一阶,对应Fib(4-1)种跳法;第一次跳出二阶,对应Fib(4-2)种跳法;第一次跳出三阶,对应Fib(4-3)种跳法;第一次跳出四阶,只有这一种跳法。所以,Fib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4) 种跳法。

当n = n 时,共有n种跳的方式,第一次跳出一阶后,后面还有Fib(n-1)中跳法; 第一次跳出二阶后,后面还有Fib(n-2)中跳法……………………..第一次跳出n阶后,后面还有 Fib(n-n)中跳法。Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+……….+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+…….+Fib(n-1)。

通过上述分析,我们就得到了通项公式:

                 Fib(n) =  Fib(0)+Fib(1)+Fib(2)+…….+ Fib(n-2) + Fib(n-1)

因此,有 Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+…….+Fib(n-2)

两式相减得:Fib(n)-Fib(n-1) = Fib(n-1)         =====》  Fib(n) = 2*Fib(n-1)     n >= 3

这就是我们需要的递推公式:Fib(n) = 2*Fib(n-1)     n >= 3

3、代码实现:

public static int JumpFloorII(int target) {
		if(target<=0){
			return 0;
		}else if(target<3){
			return target;
		}else{
			Integer[] array = new Integer[target+1];
			array[0]=1;
			array[1]=1;
			array[2]=2;
			
			for(int i=3;i<=target;i++){
				array[i]=2*array[i-1];
			}
			return array[target];
		}
    }

 

四、矩阵覆盖:

1、题目:

可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

2、思路:

思路:  对于n>=3的情况, 不管前面矩形是怎样覆盖的。我们只考虑最后一次怎么覆盖。
最后一次只有两种覆盖方式:1.用1个小矩形竖着覆盖。2.用两个小矩形横着覆盖。
所以总的方法数无外乎–>你用各种方法覆盖到只剩1个再竖着覆盖或者你用各种方法覆盖到只剩两个再横着覆盖。
即:总的方法数F(n) = n-1次的方法数F(n-1)(接着用一个小矩形竖着覆盖) + n-2次的方法数F(n-2)(接着用两个小矩形横着覆盖)

3、代码实现:

        //4.2迭代方式实现:
	public int RectCover(int target) {
		if(target==0 || target==1 || target==2){
			return target;
		}else{
			int first=1,second=2,result=0;
			for(int i=3;i<=target;i++){
				result=first+second;
				first=second;
				second=result;
			}
			return result;
		}
	}
	
	
	//4.1递归方式
	public int RectCover1(int target) {

		if(target==0 || target==1 || target==2){
			return target;
		}else{
			return RectCover1(target-1)*RectCover1(target-2);
		}
        }    

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114701.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • pip安装scrapy失败_scrapy框架运行

    pip安装scrapy失败_scrapy框架运行错误如图所示,running setup.py install for Twisted…..errorTwisted依赖库安装报错,重新下载手动安装一下下载网址:https://www.lfd.uci.edu/~gohlke/pythonlibs注意:看下安装的python是什么版本,我安装的python 3.9.0,就下载cp39,64位的下载安装的版本不对,就会报:Twisted-20.3.0-cp38-cp38-win_amd64.whl is not a support…

  • 华硕老毛子Padavan使用IPV6+Aliddns远程管理路由

    华硕老毛子Padavan使用IPV6+Aliddns远程管理路由华硕老毛子Padavan使用IPV6远程管理路由前言一、pandas是什么?二、使用步骤1.引入库2.读入数据总结前言提示:以下是本篇文章正文内容,下面案例可供参考一、pandas是什么?示例:pandas是基于NumPy的一种工具,该工具是为了解决数据分析任务而创建的。二、使用步骤1.引入库代码如下(示例):importnumpyasnpimportpandasaspdimportmatplotlib.pyplotaspltimportseaborna

  • 《大型网站技术架构》读书笔记一:大型网站架构演化

    思维导图一、大型网站系统特点(1)高并发、大流量:PV流量巨大(2)高可用:7*24小时不间断服务(3)海量数据:文件数目分分钟XXTB(4)用户分布广泛:网络情况复杂(5)安全环境恶劣:

    2021年12月29日
  • java string 转 object_java 类型转换 Object和String互转

    java string 转 object_java 类型转换 Object和String互转Long,Float等Object转为String方法1.toString()使用范围:任何继承Object的类都具有这个方法但是,使用toString()的对象不能为null,否则会抛出异常java.lang.NullPointerException/**返回:该对象的字符串表示*/Integerx=newInteger(100);if(x!=null)System.out.printl…

  • exosip

    exosip

    2021年11月30日
  • jdk1.8ArrayList主要方法和扩容机制(源码解析)

    jdk1.8ArrayList主要方法和扩容机制(源码解析)ArrayList简介:ArrayList实现了List接口它是一个可调整大小的数组可以用来存放各种形式的数据。并提供了包括CRUD在内的多种方法可以对数据进行操作但是它不是线程安全的,外ArrayList按照插入的顺序来存放数据。ArrayList的主要成员变量:privatestaticfinalintDEFAULT_CAPACITY=10;//数组默认初始容…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号