目录
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,最后求出最小值
代码
#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实现
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]的确是我们要找的字母,但是他附近没有我们要找的下一个字母)
最终代码
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]就可以实现
代码
#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打印就是不足的用空格填上