呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

【2018秋招笔试】2018.9.9 第四范式 图像应用工程师

前言

第四范式对象投的 图像应用工程师,90分钟,选择题30道,编程题2道。

选择题做的一般,编程题全部AC。

第一题


思路:

查找有序矩阵中的某个元素,要求尽量给出高效的解法,并列出时间复杂度和空间复杂度。

我采用了常见的线性查找,时间复杂度为 O(m+n),空间复杂度为 O(m*n)。

提交后AC。

代码:

/*
线性查找
时间复杂度为 O(m+n)
空间复杂度为 O(m*n)
*/

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAXN 3010

int a[MAXN][MAXN] = {0};
int m,n;


bool Find(int a[][MAXN], int k)
{
     int i = 0, j = n - 1;
     int var = a[i][j];
     while (true)
     {
         if (var == k)
         {
             return true;
         }
         else if (var < k && i < n - 1)
         {
             var = a[++i][j];
         }
         else if (var > k && j > 0)
         {
             var = a[i][--j];
         }
         else
         {
             return false;
         }
     }
}

int main()
{
    int k,i,j;
    scanf("%d%d",&m,&n);
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d",&k);

    if(Find(a,k))
        printf("true");
    else
        printf("false");

    return 0;
}

第二题

题目描述:

第二题的输入意思是5个点7条边,然后1与2之间边,2与3之间右边,3与4之间有边,4与1之间有边……然后判断这个图是不是二分图。

思路:

题目已经赤裸裸的告诉你是一道典型的二分图的题,套模板解决。

提交后AC。

代码:

#include <queue>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 999;
int col[N], Map[N][N];

//0为白色,1为黑色
bool BFS(int s, int n)
{
    queue<int> p;
    p.push(s);
    col[s] = 1;  //将搜索起始点涂成黑色
    while(!p.empty())
    {
        int from = p.front();
        p.pop();
        for(int i = 1; i <= n; i++)
        {
            if(Map[from][i] && col[i] == -1) //如果从from到i的边存在(为邻接点) && i点未着色
            {
                p.push(i);          //将i点加入队列
                col[i] = !col[from];//将i点染成不同的颜色
            }
            if(Map[from][i] && col[from] == col[i])//如果从from到i的边存在(为邻接点) && i点和from点这一对邻接点颜色相同,则不是二分图
                return false;
        }
    }
    return true;  //搜索完s点和所有点的关系,并将邻接点着色,且邻接点未发现相同色则返回true
}

int main()
{
    int i, n, m, a, b;
    memset(col, -1, sizeof(col));
    cin >> n >> m;  //n 为有多少点,m为有多少边
    for( i = 0; i < m; i++)
    {
        cin >> a >> b;
        Map[a][b] = Map[b][a] = 1;
    }
    bool flag = false;
    for(i = 1; i <= n; i++)  //遍历并搜索各个连通分支
    {
        if(col[i] == -1 && !BFS(i, n)) //每次找没有着色的点进行判断,如果从它开始BFS发现相同色邻接点则不是二分图
        {
            flag = true;
            break;
        }
    }
    if(flag)
        cout << "No" <<endl;
    else
        cout << "Yes" <<endl;
    return 0;
}

原创声明

转载请注明:呓语 » 【2018秋招笔试】第四范式 图像应用工程师