剑指offer--C++--2-7-8-9-10--替换空格--斐波那契数列--跳台阶--变态跳台阶--矩阵覆盖

桃扇骨 2022-11-07 11:36 107阅读 0赞

### 剑指offer ###

*  目录:
 *   *  JZ-2-替换空格
     *  JZ-7-斐波那契数列
     *  JZ-8-跳台阶
     *  JZ-9-变态跳台阶
     *  JZ-10-矩阵覆盖

**概述**:  
因为对于C++的知识还没有完善,一些东西还没有学习到,所以剑指是对学过的进行写的,等到后面C++逐渐的完善,我会把其余剩下的会补全!加油!

# 目录: #

## JZ-2-替换空格 ##

**题目描述:**  
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

**自我理解:**  
对于替换空格这个就比较简单了,就是在检测到空格的时候将其对应的空格改变即可,不难

class Solution{ 
    	
    public:
    		string replaceSpace(string s){ 
    			
    			int len =s.size();		//这里的size函数是结构体中本来有的,直接调用,求长度
    			for(int i=0;i<len;++i){ 	//循环遍历字符串中的每一个字符
    				
    				if(s[i]=' '){ 		//遇到空格
    					s.replace(i,1,"%20");	//执行交换函数,将其与%20进行交换
    					len+=2;		//因为%20是三个字符,而空格是一个字符,所以在每一次
    					i+=2;		//交换后都要对其进行+2的操作,保证所有的字符都可以输出!
    				}
    			}
    			return s;
    		}
    };

## JZ-7-斐波那契数列 ##

**题目描述:**  
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

**自我理解:**  
大家都知道,斐波那契数列是前两项的和,所以我们进行简单的逻辑实现,不利用递归,因为递归会执行多次的重复调用,消耗时间比较大!对于斐波那契数列不太熟悉的看之前C中讲过的[点击此处][Link 1].  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]

class Solution { 
    public:
    	int Fibonacci(int n) { 
    		if(n<2)			//等于其本身,不需要执行,减少时间复杂度
    			return n;
    		
    		int a=0,b=1,c;	//定义出除之前外开始的位置
    		for(int i=2;i<=n;++i){ 	//循环执行,注意!!!这里有=
    			c=a+b;		//上图清晰讲解
    			a=b;
    			b=c;
    		}
    		return c;	
    	}
    };

## JZ-8-跳台阶 ##

**题目描述:**  
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

**自我理解:**  
对于青蛙跳台阶来说就不存在0的数字,它只能选择跳一次或者跳两次,一般都是通过递归实现,但是今天不用,也相当于一个斐波那契数列.代码讲解:

class Solution { 
    public:
    	int jumpFloor(int number) { 
    		if(number<3)
    			return number;
    
    		int a=1,b=1,c;		//基本一致,就只有这里对于a的值有所改变,我们可以具体画图理解一下
    		
    		for(int i=2;i<number;++i){ 
    			
    			c=a+b;
    			a=b;
    			b=c;
    		}
    		return c;
    	}
    };

不过多讲解,简单的.

## JZ-9-变态跳台阶 ##

**题目描述:**  
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

**自我理解:**  
对于这种跳台阶的方式来说,当台阶数小于3的时候,还是等于其本身的,在大于3的时候,就相当于一个n阶的循环,比如在5个台阶的时候,我们就需要让其等于1 2 3 4 5共有5种跳的方法,可以交替出现,所以我们就要对上面这5种进行分类,再将分类后的结果进行相加,最终得到最后的结果.

**单个的跳台阶**:**a\[n\]=a\[n-1\]+a\[n-2\]**,**那么能跳1,2,3个**台阶时**a\[n\]=a\[n-1\]+a\[n-2\]+a\[n-3\]**,…

相当于是对每一可能性进行一对一的处理,再将所有的可能性相加!

class Solution { 
    public:
    	int jumpFloorII(int number) { 
    
    		int n;
    		if (number<3)
    			return number;
    
    		int a = 1, b = 2;		
    		int sum = a + b;						//这里就相当于一个单独的a[n]
    		int res = 0;
    		for (int i = 3; i <= number; ++i){ 		//从第三个开始
    
    			res = sum + 1;
    			sum += res;
    		}
    		return res;
    	}
    };

主要在于理解!

## JZ-10-矩阵覆盖 ##

**题目描述:**  
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

**自我理解:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]

class Solution { 
    public:
    	int rectCover(int number) { 
    		if(number<3)
    			return number;		
    	
    		int a=1,b=2,c;		//注意这里定义的a和b的初值不一样
    		
    		for(int i=3;i<=number;++i){ 	//循环,依次相加操作
    			c=a+b;
    			a=b;
    			b=c;
    		}
    		return c;
    	}
    };

后面要一起加油,多敲代码,多理解!!!今天主要的都运用了同一个思路,主要还是在对于变量上的赋值是不同的,一起加油!!! 多敲代码!!!

[Link 1]: https://blog.csdn.net/weixin_46554582/article/details/109536914
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221023/32328381affd42189a80f0b5635f8a67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221023/7e5eff531caa4097b23d3cb9d587e6fe.png