笔试时间：2024年04月10日

历史笔试传送门：2023秋招笔试合集

第一题

题目：找出最可疑的嫌疑人

民警侦办某商场店面盗窃案时，通过人脸识别针对嫌凝人进行编号1～100000。现在民警在监控记录中发现某个嫌疑人在被窃店面出现的次数超过了所有嫌疑人总出现次数的一半，请帮助民警尽可能高效的找到该嫌疑人的编号。

输入描述

给定一个嫌疑人的标号数组men,其中1<length(men)<1000,嫌疑人编号满足1<=men[i]<=100000

输出描述

返回出现次数超过一半的嫌疑人的编号。如果总次数是偶数，例如4，则需要超过2次即最少3次，如果总次数是奇数，例如5，则需要超过2.5,满足条件最少是3次。若没有嫌凝人满足该条件，返回0。

样例输入一

1,2,3,2,2

样例输出一

2

解释

第一行是嫌疑人出现记录，代表1号和3号嫌疑人出现一次，2号嫌疑人出现3次。因为2号嫌疑人出现3次，超过5次的一半，因此2号嫌疑人即为需要寻找的编号，输出2。

样例输入二

1,1,2,2,3,3

样例输出二

0

解释

第一行是嫌疑人出现记录，代表1号、2号和3号嫌疑人各出现2次因为各个嫌疑人均只出现2次，未超过6次的一半，因此没有嫌疑人满足要求，输出0。

参考题解

模拟。

C++：[此代码未进行大量数据的测试，仅供参考]

#include<iostream>
#include<vector>
#include<sstream>
using namespace std;
vector<int> vv;
string s;
int x,sum;
int a[100005];
int main()
{
    getline(cin, s);
    stringstream ss(s);
    while(ss>>x) {
        a[x] += 1;
        sum ++;
        if (ss.peek() == ',') ss.ignore();
    }
    sum = sum/2;
    for(int i = 1; i<=100000; i++) {
        if(a[i] > sum) {
            printf("%d", i);
            return 0;
        }
    }
    printf("0");
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int[] a = new int[100005];
        int sum = 0;
        
        StringTokenizer st = new StringTokenizer(s, ",");
        while (st.hasMoreTokens()) {
            int x = Integer.parseInt(st.nextToken().trim());
            a[x] += 1;
            sum++;
        }
        
        sum = sum / 2;
        for (int i = 1; i <= 100000; i++) {
            if (a[i] > sum) {
                System.out.println(i);
                return;
            }
        }
        System.out.println(0);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

import sys

def main():
    s = input().strip()
    a = [0] * 100005
    sum = 0
    
    numbers = s.split(',')
    for num in numbers:
        x = int(num.strip())
        a[x] += 1
        sum += 1
    
    sum //= 2
    for i in range(1, 100001):
        if a[i] > sum:
            print(i)
            return
    
    print(0)

if __name__ == "__main__":
    main()

第二题

题目：会议通知转发总人数

在一个办公区内，有一些正在动公的员工，当员工A收到会议通知，他会将这个会议通知转发给周围四玲邻（上下左右工位的同事）团队内的同事，周围收到该邮件的同事会继续转发给周围四邻（上下左右工位的同事团队内的同事，直到周围没有再需要往下传播的同事则会停止；同时此扩散还有前提条件，给定一可收到该邮件的团队列表relations,扩散时若该同事所在团队在relations列表中，则可进行扩散，否则不可进行扩散。办公室用一个二维数组office表示，其中office[i][j]表示该同事的团队名称，其中团队名称用整数t范围内的数字表示，i，j表示该同事的工位位置。

现给定办公区的工位总行数与每一行的具体工位人员分布以及收到会议通知员工A的工位位置的坐标位置i，j:还有与该邮件关联的团队编号列表relations,请分析得出最终会有多少同事收到该会议的转发通知。

注意：1、该办公区位置用二维数组表示，该二维数组以左上角的工位为起点(0,0),按照横轴向右纵轴向下的方向展开；原始收到会议通知的员工A不包含在总人数中。2、扩散时若该同事与收到初始收到邮件的员工A属于同一团队，若该团队名不在可收到通知的团队列表relations中，依然不可收到该邮件转发。

输入描述

第一行是一个整数n,表示该办公区共有多少排，即就是office.length

第二行是一个整数m,标识该办公区共有多少列，即就是offce[i].length

接下来n行表示每一排员工的具体分布情况，每个工位上的员工所在的团队号x用空格隔开

接下来一行是两个数字用空格隔开，表示收到会议通知员工的工位位置，i表示横坐标位置，j表示纵坐标位置

最后一行是一个字符串，表示可收到该邮件的团队列表relations,团队名称之间用空格隔开

提示：

0<=i<=1000

0<=j<=1000

1<=t<=50

1<=relations.length<=50

输出描述

输出收到转发会议通知的总人数。

样例输入一

5

5

1 3 5 2 3

2 2 1 3 5

2 2 1 3 3

4 4 1 1 1

1 1 5 1 2

2 2

1

样例输出一

5

样例输入二

2

2

1 1

2 2

0 0

2

样例输出二

2

参考题解

bfs，将收到会议通知员工的工位位置(x,y)点作为生长起点，对于在relations里的才可以继续广度优先搜索。

C++：[此代码未进行大量数据的测试，仅供参考]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<string>
#include<sstream>
#include<queue>
using namespace std;
int n,m,x,y;
int a[1005][1005];
string s;
set<int > S;
int nx[4] = {1,0,-1,0};
int ny[4] = {0,1,0,-1};
int vis[1005][1005];
int main()
{
    cin>>n>>m;
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=m; j++) {
            cin>>a[i][j];
        }
    }
    cin>>x>>y;
    x++,y++;
    vis[x][y] = 1;
    queue<pair<int, int> > q;
    q.push(make_pair(x,y));
    getchar();
    getline(cin, s);
    str