您的位置:首页 > 汽车 > 新车 > 山西太原建站哪家强_传媒公司业务范围介绍_seo做关键词怎么收费的_网站制作费用一览表

山西太原建站哪家强_传媒公司业务范围介绍_seo做关键词怎么收费的_网站制作费用一览表

2025/3/14 10:32:09 来源:https://blog.csdn.net/LH__1314/article/details/146244707  浏览:    关键词:山西太原建站哪家强_传媒公司业务范围介绍_seo做关键词怎么收费的_网站制作费用一览表
山西太原建站哪家强_传媒公司业务范围介绍_seo做关键词怎么收费的_网站制作费用一览表

刷题day_4

继续加油!!!

一、Fibonacci数列

题目链接:Fibonacci数列

题目解析

在这里插入图片描述

题目要求,输入一个数N,我们可以对N进行+1/-1操作;题目让我们输出对N进行至少多少步可以变成Fibonacci数。

这里题目上说了我们对N的操作是+1或者-1,那我们就可以理解成求离N最近的Fibonacci数。

算法思路

我们需要寻找离N最近的Fibonacci

这里定义三个变量abc用来求Fibonacci数;在求的过程中,让N处于bc之间即可

最后返回N-bc-N的最小值即可。

代码实现

#include<iostream>
using namespace std;
int main()
{int a=0,b=1;int c=a+b;int n;cin>>n;while(n>c){a = b;b = c;c = a+b;}cout<<min(n-b,c-n)<<endl;return 0;
}

二、单词搜索

题目链接:单词搜索

题目描述

在这里插入图片描述

这里时一道经典的搜索题

题目给定一个二维字符数组board,给定一个单词word

让我们在这个字符数组中查找单词word(单词由相邻单元格的字母组成)并且同一个单元格的字符不能重复使用。

如果存在就返回true,如果不存在就返回false

算法思路

这一个经典的查找题目,在第一次做的时候可以说毫无思路;这里就直接说解法了。

首先,我们在二维字符数组中查找到单词word的第一个字符;

然后从这个位置开始进行深度优先遍历,来查找字符存在。

这里对于dfs深度优先遍历,来看一下如何实现

首先,遍历结束的条件(递归结束):当我们的pos遍历到word单词的结尾时,递归就结束了。

其次,我们要先修改当前位置的标记,修改成true;意思是已经查找过

然后,依次遍历当前位置的上、下、左、右四个位置,继续进行深度优先遍历,如果遍历查找到word单词就返回true

最后,执行完for循环(查找结束其上、下、左、右四个位置没有返回true,就表示没有查找到),我们需要将当前位置标记修改回来,再返回false

代码实现

Ok,有了思路,直接开始写代码

class Solution {
public:int m,n; //表示二维字符数组的长和宽bool vis[101][101]; //用来标记每个位置是否被使用int dx[4] = {0,0,1,-1}; //上、下、左、右位置的x坐标变化int dy[4] = {1,-1,0,0}; //上、下、左、右位置的y坐标变化bool exist(vector<string>& board, string word) {m = board.size();n = board[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j] == word[0]){if(dfs(board,i,j,word,0))return true;}}}//如果执行完for循环还没有返回,就说明没有找到//返回 falsereturn false;}bool dfs(vector<string>& board, int i,int j,string& word, int pos){if(pos == word.size() -1){return true;}vis[i][j] = true;//修改当前位置标记//依次遍历其上下左右四个位置for(int k=0;k<4;k++){int a = i+dx[k];int b = j+dy[k];//如果这个位置没有越界,当前位置没有用过;当前位置与要查找的字符相同if(a>=0 && a<m && b>=0 && b<n && vis[a][b] == false && board[a][b] == word[pos+1]){//深度优先遍历这个位置if(dfs(board,a,b,word,pos+1)){return true;}}}vis[i][j] = false;return false;}
};

三、杨辉三角

题目链接:杨辉三角

题目解析

在这里插入图片描述

对于题目,杨辉三角再熟悉不过了;这里需要注意的是

  • 输出时需要注意,每个数输出域宽为5

算法思路

杨辉三角,相信都早已熟悉了,这里提供两个做法

1. 使用vector来存储杨辉三角的数据

  • 定义vector<vector<int>> vp,对vp的第i行开辟i+1个空间,并且都初始化为1(方便进行数据操作)
  • 然后从第二行(下标为2),第一个(下标为1)位置开始填充数据。
  • 填充完成之后进行输出(注意输出使用printf%5d来保证每个数据宽为5

2. 定义一个dp表

  • 定义一个dp[31][31]的表,表中存储的是杨辉三角的数据;将表中所以数据初始化为0
  • dp[1][1]初始化成1,然后进行填充数据
  • 这里dp[31][31]确保了我们在进行操作时不会越界。

代码实现

对于第一种做法

#include<iostream>
#include<vector>using namespace std;int main()
{int n;cin>>n;vector<vector<int>> vp(n);for(int i=0;i<n;i++){vp[i].resize(i+1,1);}for(int i=2;i<n;i++){for(int j=1;j<i;j++){vp[i][j] = vp[i-1][j] + vp[i-1][j-1];}}for(int i=0;i<n;i++){for(int j =0;j<=i;j++){printf("%5d",vp[i][j]);}cout<<endl;}return 0;
}

第二种,定义一个dp

#include <iostream>
using namespace std;int dp[31][31];
int main() {int n;cin>>n;dp[1][1] = 1;for(int i=2;i<=n;i++){for(int j = 1;j<=i;j++){dp[i][j] = dp[i-1][j] + dp[i-1][j-1];}}for(int i=1;i<=n;i++){for(int j = 1;j<=i;j++){printf("%5d",dp[i][j]);}cout<<endl;}return 0;
}dp[i][j] = dp[i-1][j] + dp[i-1][j-1];}}for(int i=1;i<=n;i++){for(int j = 1;j<=i;j++){printf("%5d",dp[i][j]);}cout<<endl;}return 0;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com