刷题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;
}
