目录

WY22 Fibonacci数列题目解析解法暴力解法贪心代码

NC242 单词搜索题目解析例子1解析例子2解析例子3解析解法深度优先遍历dfs实现最终代码

BC140 杨辉三角解法线性dp问题代码

感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接

🐒🐒🐒

个人主页

🥸🥸🥸

C语言

🐿️🐿️🐿️

C语言例题

🐣🐣🐣

python

🐓🐓🐓

数据结构C语言

🐔🐔🐔

C++

🐿️🐿️🐿️

文章链接目录

🏀🏀🏀

笔试练习题

WY22 Fibonacci数列

链接WY22 Fibonacci数列

题目解析

这道题不是让我们求斐波那契数,而是让我们将一个数通过加或减的方式去让他变成一个斐波那契数,每次变化的绝对值为1,要求我们得到最小变化的次数

解法

我们以示例1为例子

N=15时只需要求出他距离那个斐波那契数最近就可以了,比如15-13=2 21-15=6,显然15距离13最近,因此输出2

当N=13的时候,距离应该是0,因为N就是斐波那契数

所以我们得出了一个结论就是首先我们需要判断N是否是斐波那契数,如果是就返回0,如果不是那就说明N是在两个斐波那契数中间夹着的,我们只需要求出他距离最近两个斐波那契数的最小距离就可以了

暴力解法

我们可以创建一个数组Fib来记录所有的斐波那契数,然后遍历一遍数组,找出N在哪两个数字中间,之后求出距离就可以了

贪心

我们用3个变量a b c 来记录斐波那契数,因为c=a+b,所以我们只需要先给abc都初始化就可以了

我们假设N=6

因为N是大于c=1的,在上面有说过N是要在两个斐波那契数之间夹着的(也就是5和8之间),所以abc要一直变化直到c=8,b=5,然后让c-N,N-b,最后求出最小值

代码

<code>#include <iostream>

using namespace std;

int n;

int main() { -- -->

cin>>n;

int a=0,b=1,c=1;

while(n>c)

{

a=b;

b=c;

c=a+b;

}

cout<<min(c-n,n-b);

return 0;

}

NC242 单词搜索

链接NC242 单词搜索

题目解析

例子1解析

例子1中要找到XYZZED,首先我们要先找到字符串数组中X所在的位置,这里有两个X,我们先找第一个X,找到X后可以在上下左右相邻格内去找Y,注意这里是相邻格

X的相邻格内正好有一个Y,找到Y后就需要在Y相邻格内去找Z

后面就是直接按照这个方法去找

例子2解析

例子2有两个s

但是因为找到s后要在他相邻格内找出E,所以我们可以直接排除左边的s

s的临格有两个E,但是上面E的临格没有E,所以我们选择S的下面的E

例子3解析

例子3给出的字符串是XYZY

还是先找X,有两个X,但是我们选择上面一个

在找到Z后要注意,Z的临格确实是有Y的,但是这个Y我们已经用过了,不能在用他,所以Z的临格没有Y可以用了,因此返回 false

解法

深度优先遍历

首先因为这是一个二维字符数组,所以需要我们求出他的总的大小(用m表示),和一行的大小(用n表示)

因为在搜索的时候题目规定使用过的字母是不可以重复使用的,所以需要用一个bool类型的二维数组(bool vis[101][101]={0})去记录字母是否已经被使用过的

用两个方向数组(dy[4]={0,0,1,-1})和(dx[4]={1,-1,0,0})

之后用两层for循环去找第一个字母,当找到后就用dfs函数去递归展开找下一个字母

dfs实现

<code> 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],b=j+dy[k];

if(a>=0&&a<m&&b>=0&&b<n&&!vis[a][b]&&board[a][b]==word[pos+1])

{

if(dfs(board,a,b,word,pos+1))

return true;

}

}

vis[i][j]=false;

return false;

}

pos是当前搜索字母所在字符串的位置,当pos为最后一个字母的时候(\0不算),就说明已经搜索完了,就返回true

因为进入这个函数的时候board[i][j]是等于word[pos]的,所以我们需要用vis[i][j]对此时的board[i][j]进行标记

标记后需要对board[i][j]位置的上下左右进行搜索,我们用a=i+dx[k]表示x方向的下标,b=j+dy[k]表示y方向的下标

这个时候需要补充说明一下为什么dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},上面的k表示的是循环次数,意思是用for循环4次去找他上下左右的字母

k=0的时候坐标(dx,dy)=(1,0),表示的是查找字母的右边

k=1的时候坐标(dx,dy)=(-1,0),表示的是查找字母的左边

k=2的时候坐标(dx,dy)=(0,1),表示的是查找字母的下边

k=3的时候坐标(dx,dy)=(0,-1),表示的是查找字母的上边

这几个坐标中没有出现(1,1)和(-1,-1)是因为我们要找的是上下左右的位置

在搜索的过程中需要判断a=i+dx[k]和b=j+dy[k]的范围,0<=a<m,0<=b<n,vis[a] [b]=vis[i+dx[k]] [j+dy[k]]表示的是vis[i][j]附近的字母,我们需要判断附近的字母是否有标记过true的,如果标记过的就不考虑这个字母,此外board[a][b]还必须要等于wordpos+1

当满足上面的条件时就进行递归if(dfs(board,a,b,word,pos+1)),当括号内的条件满足时就然后true

如果在board[i][j]附近找不到word[pos+1]的字母,那就说明boar[i][j]位置找错了

这时候需要将vis[i][j]更改为false(表示虽然vis[i][j]的确是我们要找的字母,但是他附近没有我们要找的下一个字母)

最终代码

<code>class Solution { -- -->

public:

int m,n;

bool vis[101][101]={ 0};

int dx[4]={ 0,0,1,-1};

int dy[4]={ 1,-1,0,0};

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;

}

}

}

return 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],b=j+dy[k];

if(a>=0&&a<m&&b>=0&&b<n&&!vis[a][b]&&board[a][b]==word[pos+1])

{

if(dfs(board,a,b,word,pos+1))

return true;

}

}

vis[i][j]=false;

return false;

}

};

注意m=board.size()表示的是二维数组的行数,他与以前C语言学的二维数组有点不同

例如 int arr[5][5]表示5行5列的二维数组,m=sizeof(arr)表示的是有多少个元素,也就是m=5*5=25

而上面的代码中m=board.size(),由于是vector中的size(可能内部实现不同),导致m表示的是行数

BC140 杨辉三角

链接BC140 杨辉三角

解法

线性dp问题

这道题根据杨辉三角的性质我们可以用二维数组去解决

所以创建一个二维数组dp[31][31],在填表的过程中,因为杨辉三角的n>=1,所以我们从dp[1][1]开始填,而dp[0]或者dp[1][0]这些就不填默认初始化为0

此外这样的好处还有dp[1][0]+dp[1][1]是不会影响dp[2][1]的

所以通过dp[i][j]=dp[i-1][j]+dp[i-1][j-1]就可以实现

代码

<code>#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<<"\n";

}

return 0;

}

注意%5d是因为题目要求输出域宽为5,用%5d打印就是不足的用空格填上