前言
今天的三个题目分别是:WY22 Fibonacci数列、NC242 单词搜索、BC140 杨辉三角。
1. Fibonacci数列
1.1 题目描述
1.2 解题思路
一道非常简单的dp问题,甚至连动态转移方程都给给出了。状态表示就是:到达第n个位置,F[n]的值为多少,状态转移方程就是:F[i] = F[i-1] + F[i-2]。 因此用一个for循环就可以解决问题了。然后找到第一个大于n的数,将n与第一个大于它的数和第一个小于它的数进行比较,算出差值就可以了。
1.3 代码实现
#include <iostream>
using namespace std;
#include <vector>
int main()
{
int n = 0;
cin >> n;
vector<int> dp(1000, 0);
int ret = 0x3f3f3f3f;
dp[0] = 0, dp[1] = 1;
for (int i = 2; dp[i - 1] < 1e6 + 1; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
if (n <= dp[i])
{
ret = min(ret, dp[i] - n);
ret = min(ret, n - dp[i - 1]);
break;
}
}
cout << ret;
return 0;
}
2. 单词搜索
2.1 题目描述
2.2 解题思路
这是一道典型的dfs(深度优先搜索)的题目,实际上也就是暴力搜索,将每一个格子当作起点,再将其余格子当成第二步,……,也就是将所有情况都枚举出来,看看有没有符合条件的路径。
2.3 代码实现
class Solution {
public:
int m, n;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool vis[101][101];
bool dfs(vector<string>& board, string word, int i, int j, int pos)
{
vis[i][j] = true;
if (board[i][j] != word[pos])
{
return false;
} else
{
if (pos == word.size() - 1) return true;
if (board[i][j] == word[pos])
{
for (int k = 0; k < 4; k++)
{
int x = i + dx[k], y = j + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y])
{
if (dfs(board, word, x, y, pos + 1)) return true;
vis[x][y] = false;
}
}
}
}
return false;
}
bool exist(vector<string>& board, string word)
{
memset(vis, 0, sizeof vis);
m = board.size(), n = board[0].size();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
if (dfs(board, word, i, j, 0)) return true;
vis[i][j] = false;
}
return false;
}
};
3. 杨辉三角
3.1 题目描述
3.2 解题思路
这一道题也是一道基础的dp问题,照着题目描述进行模拟即可,状态表示和状态状态转移方程都已经给出了,这就相当于一道模拟题了。不过需要注意的是,答案要求输出域宽为5,也很简单,大家看代码即可。(用C语言的printf)文章来源:https://www.toymoban.com/news/detail-856338.html
3.3 代码实现
#include <iostream>
using namespace std;
#include <vector>
int main()
{
int n = 0;
cin >> n;
vector<vector<int>> nums(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
{
nums[i][0] = nums[i][i] = 1;
for (int j = 1; j <= i; j++)
{
nums[i][j] = nums[i - 1][j] + nums[i - 1][j - 1];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
printf("%5d", nums[i][j]);
}
cout << endl;
}
return 0;
}
总结
今天的第一题和第三题都比较简单,就是两道模拟题,第二道题稍微有些难度,但是只要学会了dfs,相信不成问题。我上面写的dfs就是一个比较基础的模板,可以套用大部分的dfs题目,如果有不会的小伙伴,可以私信我,之后会出一期专门的文章来进行讲解。
那么第三天的内容就到此结束了,如果大家发现有什么错误的地方,可以私信或者评论区指出喔。我会继续坚持训练的,共勉!!!那么本期就到此结束,让我们下期再见!!觉得不错可以点个赞以示鼓励!文章来源地址https://www.toymoban.com/news/detail-856338.html
到了这里,关于强化训练:day3的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!