【C++】 —— 笔试刷题day_4

刷题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循环还没有返回，就说明没有找到
        //返回 false
        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];
            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;
}