【笔试训练】day4

简介: 【笔试训练】day4

不到5分钟写完,今天的题又又又难一点啦!

1.Fibonacci数列

思路:

直接模拟一遍斐波那契数列的递增过程,大于n就直接结束。因为后面只会越来越大,跟题目求的最小步数不符。在这个过程中用一个变量去维护这个当前的元素与目标n还差多少,这个差值就是n变成这个当前元素的步数。整个过程取min就欧克了。

代码:
#include <iostream>
#include<algorithm>
using namespace std;
 
int main() {
    int n;
    cin>>n;
    int a=0;
    int b=1;
    int ans=min(abs(0-n),abs(1-n));//初始化
    while(a+b<n){
        ans=min(ans,abs(n-(a+b)));
        int c=a+b;
        a=b;
        b=c;
    }
    ans=min(ans,abs(n-(a+b)));
    cout<<ans;
    return 0;
}

2.单词搜索

思路:

没什么可说,数据小,直接dfs。

先搜索一下整个字符数组,如果有字符和word[0]相等,那么说明这个点可以作为dfs的起点。

直到搜索到一条完整的路径匹配word。

剩下的就是老掉牙的搜索过程了。一共有四个方向,用两个数组分别模拟坐标位移的横纵偏移量。每个点只能走一次,每次搜这个点对应的字符必须与目标字符相同,因为我们是带着目的去搜索的,下一个点要搜索到什么字符,可以用一个变量pos去维护.

代码:
#define _CRT_SECURE_NO_WARNINGS 1
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
bool ans;
int n, m;
bool st[110][110];
class Solution {
public:
 
    void dfs(int x, int y, vector<string>& board, string word, int pos) {
        if (pos == word.size()) {
            ans = true;
            return;
        }
 
        for (int i = 0; i < 4; i++) {
            int a = dx[i] + x;
            int b = dy[i] + y;
            if (a >= 0 && a < n && b >= 0 && b < m && board[a][b] == word[pos] && !st[a][b]) {
                st[a][b] = true;
                dfs(a, b, board, word, pos + 1);
                st[a][b] = false;
            }
        }
    }
 
    bool exist(vector<string>& board, string word) {
        n = board.size();
        m = board[0].size();
        ans = false;
        memset(st, false, sizeof st);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == word[0]) {
                    st[i][j] = true;
                    dfs(i, j, board, word, 1);
                    st[i][j] = false;
                    if (ans)return true;
                }
            }
        }
        return false;
 
    }
};

3.杨辉三角

思路:

没思路,直接模拟一遍就行了。

要注意的是,题目要求的是每个输出宽度为5,并不是输出带空格。只是样例看起来样例带了空格

代码:
 
#include <iostream>
using namespace std;
const int N = 35;
int a[N][N];
int main() {
    int n;
    cin >> n;
    a[1][1] = 1;
    printf("%5d\n", 1);
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
            printf("%5d", a[i][j]);
 
        }
        if (i != n)cout << endl;
    }
    return 0;
}


目录
打赏
0
0
0
0
18
分享
相关文章
基于SpringBoot+Vue+uniapp的中国剪纸微信小程序的详细设计和实现(源码+lw+部署文档+讲解等)
基于SpringBoot+Vue+uniapp的中国剪纸微信小程序的详细设计和实现(源码+lw+部署文档+讲解等)
151 1
一起挑战pythontip的题目(19)
一起挑战pythontip的题目(19)
107 0
loadrunner 脚本优化-检查点设置
loadrunner 脚本优化-检查点设置
331 0
C#编程-102:泛型集合类概述
C#编程-102:泛型集合类概述
138 0
C#编程-102:泛型集合类概述
esc使用体验心得
在我看来云服务器有以下优点:省力,不需要专门花时间去维护服务器的硬件,看服务器是否运行正常;稳定,这应该是最主要的有点;安全,做web开发最怕的当然是攻击,所以选择大厂的服务器,自然是最香的;省钱,这当然也是很重要的,尤其对于我们学生用户还是很友好的,爆赞!
在工作中常用到的集合有哪些?
作为一个新人,最关心的其实有一点:这个技术在工作中是怎么用的。换个说法:“工作中常用到的Java集合有哪些,应用场景是什么”
366 0
在工作中常用到的集合有哪些?
MaxCompute(原ODPS)开发入门指南——数据上云篇
根据《MaxCompute(原ODPS)开发入门指南——计量计费篇》的了解,大家清楚了MaxCompute可以做什么,计费模式如何,想必大家也开通了MaxCompute想进行一次POC,但是大家遇到第一个问题一定是我的数据如何上云?
10712 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问