【备战秋招】——算法题目训练和总结day4

   
😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

前言🙌

    哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘 都是精华内容，可不要错过哟！！！😍😍😍

Fibonacci数列

题目链接: Fibonacci数列

我的题解思路分享

算法思路：贪心。

1. 首先是认真审题，结合示例理解。
2. 可以利用三个变量，再用wile 循环进行移动求解出每一个Fib数。
3. 利用贪心的思想，很容易想到，我们应该对一个数只进行++ 或者 - - 操作。因为既++ 又 - - ，会抵消从而浪费步数。因此我们找到 n 值 离它最近的 左、右两个Fib数即可。
4. 取他们的差值的最小值即可。

代码分享

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a = 0, b = 1 ,c = 1;
    while(c < n)
    {
        a = b;
        b = c;
        c = a + b;
    }
    cout << min(c - n, n - b);
}

单词搜索

题目链接: 单词搜索

我的题解思路分享

算法思路：深度优先遍历dfs

1. 首先是认真审题，结合示例理解。
2. 定义一个 vis 二维数组，记录dfs时，访问过的字符数组位置，从而避免重复访问已走过的位置。
3. 定义dx和dy的数组，记录该位置的上下左右四个方向。根据题目可知，我们每次都是可以从该位置的上下左右进行搜索。
4. dfs的设计：你给我一个需要搜索的数组，并告诉我开始搜索的位置，以及目标单词开始查找的pos下标位置。
5. 当我们查找到单词的下标已经到达单词的最后一个下标位置时，说明我们已经找到了该单词，返回true。
6. 每次先找到要单词字符串的起点（首字母）,然后进行从该位置进行一次dfs，如果可以形成目标字符串，那么就返回true
7. 如果不能，就进行回溯，恢复现场。然后再找到一个匹配字符的起点位置，继续进行dfs。
8. 当两次for循环后，依旧没有返回true，那么就表明该字符串数组中，不能形成单词字符串。

代码分享

class Solution {
public:

    bool vis[101][101];//记录访问过的位置
    int dx[4] = {0,0,1,-1};//形成方向坐标
    int dy[4] = {1,-1,0,0};//形成方向坐标
    int row;
    int col;
    string target;
    bool dfs(vector<string>& board, int i , int j, int pos)
    {
    	//说明已经搜索出目标word
        if(pos == target.size() - 1)
            return true;
        for(int k = 0; k < 4; k++)
        {
        	//形成坐标方位
            int x = dx[k] + i;
            int y = dy[k] + j;
            if(x >= 0 && x < row && y >= 0 && y < col  && !vis[x][y] && board[x][y] == target[pos + 1])
            {
                vis[x][y] = true;
                if(dfs(board,x,y,pos + 1))
                {
                	//剪枝：搜索到了单词，就直接返回了
                    return true;
                }
                //恢复现场
                vis[x][y] = false;
            }
        }
        //四个方位都没有路可走，说明搜索不了word。
        return false;
    }
    bool exist(vector<string>& board, string word) {
        target = word;
        row = board.size();
        col = board[0].size();
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(board[i][j] == word[0])
                {
                    vis[i][j] = true;
                    if(dfs(board,i,j,0))
                    {
                    	//剪枝：搜索到了单词，就直接返回了
                        return true;
                    }
                    //恢复现场
                    vis[i][j] = false;
                }
            }
        }
        //遍历完整个数组，还是没有返回true，说明该本次dfs单词搜索不成功
        return false;
    }
};

杨辉三角

题目链接: 杨辉三角

我的题解思路分享

算法思路：动态规划

1. 首先是认真审题，结合示例理解。
2. 题目阐述已经非常清楚了，根据题目意思我们就可以得出我们的动态转移方程。 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
3. 3.我们最好从[1,1]开始填表,而不是从[0,0]开始，这样可以节省很多边界条件的特判。比较容易控制代码，不容易出错。
4. 由于这里要求格式化输出，因此我们用c语言的 printf 打印结果是比较方便的。

代码分享

#include <cstdio>
#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]);
        }
        printf("\n");
    }
    return 0;
}

总结撒花💞

   本篇文章旨在分享的是题解知识。希望大家通过阅读此文有所收获！
   😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘