笔试时间：2024年04月24日 备注：暂无第三题

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：满二叉搜索树查找

给定2^n-1个不同的整数(1<=n<=10,n为整数)，构建一棵平衡满二叉搜索树，二叉搜索树定义如下:

1)节点的左子树只包含小于当前节点的数。

2)节点的右子树只包含大于当前节点的数。

3)所有左子树和右子树自身必须也是二叉搜索树。例7个数字1234567构建的满二叉搜索树如下所示：

4

2 6

1 3 5 7

再给一个待查找数,计算查找路径和结果。

输入描述

输入分2行, 第一行为2^n-1个未排序的整数，空格分隔,用于构建二叉搜索树,其中1<=n<=10；

第二行为待查找的整数。

所有输入整数的取值范围为[-32768，32767]。

输出描述

搜索的路径和结果 路径从根节点开始,用S表示,查找左树用L表示，查找右树使用R表示，找到后使用Y表示，最终未找到使用N表示。

样例输入一

2 1 3 7 5 6 4

6

样例输出一

SRY

解释:从根节点开始，所以路径的第一部分为S，待查找数为6，大于4，所以要查找右树，路径增加R,正好找到。所以最后增加Y,最终输出SRY

样例输入二

4 2 1 3 6 5 7

5

样例输出二

SRLY

解释：从根节点开始,一次往右树,往左树查找,找到结果5,因此最终SRLY

样例输入三

1 2 3 4 5 6 7

8

样例输出三

SRRN

解释:从根节点开始查找，标记s，待查找数8比4大,所以查找右树，标记R, 8比6还大，继续查找右树标记R，8比右树节点7还大,但已经到了叶子,没有找到,因此最终标记SRRN。

参考题解

本质就是一个二叉搜索树的遍历，不过我们不用建立二叉树，可以用二分查找来代替，需要注意的是，访问到叶子节点后，如果还没有找到，此时并不增加路径。

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

#include <sstream>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
int target;

int main()
{
    stringstream ss;
    string s, t;
    getline(cin, s);
    ss << s;
    v.clear();
    while (ss >> t) {
        v.push_back(stoi(t));
    }
   // getchar();
    cin >> target;
    sort(v.begin(), v.end());
    string ans = "S";
    int l = 0, r = v.size() - 1;
    int d = 0;
    while (l <= r) {
        int m = (l + r) / 2;
        d++;
        if (v[m] == target) { ans += "Y"; break; }
        if (v[m] > target) {
            if ((1 << (d)) > v.size()) break;
            ans += "L"; r = m - 1;
        } else {
            if ((1 << (d)) > v.size()) break;
            ans += "R"; l = m + 1;
        }
    }
    if (ans.back() != 'Y') ans += "N";
    cout << ans;
    return 0;
}

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

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> v = new ArrayList<>();
        String s = scanner.nextLine();
        String[] tokens = s.split(" ");
        for (String token : tokens) {
            v.add(Integer.parseInt(token));
        }
        int target = scanner.nextInt();
        Collections.sort(v);
        String ans = "S";
        int l = 0, r = v.size() - 1;
        int d = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            d++;
            if (v.get(m) == target) {
                ans += "Y";
                break;
            }
            if (v.get(m) > target) {
                if ((1 << d) > v.size()) break;
                ans += "L";
                r = m - 1;
            } else {
                if ((1 << d) > v.size()) break;
                ans += "R";
                l = m + 1;
            }
        }
        if (ans.charAt(ans.length() - 1) != 'Y') ans += "N";
        System.out.println(ans);
    }
}

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

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    v = list(map(int, data[:-1]))
    target = int(data[-1])
    
    v.sort()
    ans = "S"
    l, r = 0, len(v) - 1
    d = 0
    
    while l <= r:
        m = (l + r) // 2
        d += 1
        if v[m] == target:
            ans += "Y"
            break
        if v[m] > target:
            if (1 << d) > len(v):
                break
            ans += "L"
            r = m - 1
        else:
            if (1 << d) > len(v):
                break
            ans += "R"
            l = m + 1
    
    if ans[-1] != 'Y':
        ans += "N"
    
    print(ans)

if __name__ == "__main__":
    main()

第二题

题目：足球队员射门能力排序

球队有n个足球队员参与m次射门训练，每次射门进球用1表示，射失则用0表示，依据如下规则对该n个队员的射门能力做排序 1、进球总数更多的队员射门能力更强 2、若进球总数—样多，则比较最多—次连续进球的个数，最多的队员能力更强 3、若最多一次连续进球的个数一样多，则比较第一次射失的先后顺序，其中后射失的队员更强，若第一次射失顺序相同，则按继续比较第二次射失的顺序，后丢球的队员能术更强，依次类推 4、若前3个规则排序后还能力相等，则队员编号更小的能力更强。

输入描述

第1行，足球队员数n，射门训练次数m。(队员编号从1开始，依次递增)

第2行，第1~n个队员从第1到m次训练的进球情况，每个队员进球情况为连续的1和0的组合，不同队员用空格分隔n和m均为正整数，0<n<=10 ^ 3，0<m<=10^3

输出描述

射门能力从强到弱的队员编号,用空格分隔。

样例输入一

4 5

11100 0011110111 01111

样例输出一

4 3 1 2

解释:4个队员，射门训练5次，队员3和4进球数均为4个，比队员1和2的3个更多,队员3连续进球数最多一次为3个,而队员4最大为4，因此队员4射门能力强于队员3,另外队员2比队员1先丢球，因此队员1射门能力强于队员2，排序为4312

样例输入二

2 10

1011100111 1011101101

样例输出二

2 1

解释:2个队员，射门训练10次，两个队员的进球总数均为7个,连续进球最多的均为3个，且第前两次丢球顺序均为第二次和第6次训练射门，而队员2第三次丢球为第9次训练,队员2为第7次训练，因此队员2的射门能力强于队员1,排序为21

参考题解

本质就是一个排序问题，但是排序的规则比较复杂，需要预处理数据，得到每个人的进球数、最多的连续进球个数、失球顺序，然后排序的时候按照题目要求进行返回即可。

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

#include <sstream>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n, m; cin >> n >> m;
    vector<int> goals(n, 0), seq(n, 0);
    vector<vector<int>> fs(n);
    for (int i = 0; i < n; ++i) {
        string s; cin >> s;
        int g = 0, mx_s = 0, cur_s = 0;
        for (int j = 0; j < m; ++j) {
            g += (s[j] == '1');
            if (s[j] == '1') ++cur_s;
            else {
                fs[i].push_back(j);
                mx_s = max(mx_s, cur_s); cur_s = 0;
            }
        }
        goals[i] = g; seq[i] = max(mx_s, cur_s);
    }
    vector<int> idx(n);
    for (int i = 0; i < n; ++i) idx[i] = i;
    sort(idx.begin(), idx.end(), [&](auto& a, auto& b) {
        // 进球数
       if (goals[a] > goals[b]) return true;
       if (goals[a] < goals[b]) return false;
        // 最多连续进球数
       if (seq[a] > seq[b]) return true;
       if (seq[a] < seq[b]) return false;
        // 射失顺序
       int sz = fs[a].size();
       for (int j = 0; j < sz; ++j) {
           if (fs[a][j] > fs[b][j]) return true;
           if (fs[a][j] < fs[b][j]) return false;
       }
        return a < b;
    });
    for (int i = 0; i < n; ++i) {
        cout << idx[i] + 1;
        if (i != n - 1) cout << " ";
    }
    return 0;
}