刷题day_4
继续加油!!!
一、Fibonacci数列
题目链接:Fibonacci数列
题目解析
题目要求,输入一个数
N
,我们可以对N
进行+1
/-1
操作;题目让我们输出对N
进行至少多少步可以变成Fibonacci
数。
这里题目上说了我们对N
的操作是+1
或者-1
,那我们就可以理解成求离N
最近的Fibonacci
数。
算法思路
我们需要寻找离N
最近的Fibonacci
数
这里定义三个变量
a
,b
,c
用来求Fibonacci
数;在求的过程中,让N
处于b
和c
之间即可最后返回
N-b
和c-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;
}