科大讯飞嵌入式软件笔试编程题

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《嵌入式软件笔试-2023年真题汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

《嵌入式软件笔试-2024年真题汇总》：https://blog.nowcoder.net/zhuanlan/04yYym

第一题：

题意

给出一个长度为n的序列a1, a2, a3…an，请你按照以下规则输出序列的中位数: 1.如果序列的大小为奇数，则中位数是按照升序排序后中间的数字。 2.如果序列的大小为偶数:

• 按照升序排序后，中间的两个数字x=y时输出任意一个即可;
• 按照升序排序后，中间的两个数字x!=y时输出min(x,y)，即 x 和 y 中较小的那个数。当输出中位数 mid时，该中位数 mid从序列 a中消失，再输出消失后的序列 a’ 的中位数。

重复上述步骤，直至全部将序列 a全部输出。

输入描述

第一行输入一个正整数 n代表序列长度。第二行输入n 个正整数a1, a2, a3…an代表序列元素

输出描述

在一行上输出 n 个整数代表依次提取出的中位数

输入

4

1 8 9 5

输出

5 8 1 9

输入

6

6 6 6 6 6 6

输出

6 6 6 6 6 6

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 找到当前序列的中位数
int findMedian(vector<int>& a) {
    sort(a.begin(), a.end());
    int n = a.size();
    if (n % 2 == 1) {
        return a[n / 2];
    } else {
        return min(a[n / 2 - 1], a[n / 2]);
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> result;
    while (!a.empty()) {
        int median = findMedian(a);
        result.push_back(median);
        // 只删除一个中位数
        auto it = find(a.begin(), a.end(), median);
        if (it != a.end()) {
            a.erase(it);
        }
    }

    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}

第二题：

题意

给定一个仅由小写字母组成、长度为n的字符串 s则字符串有(2^n)-1个非空子序列。请你求出所有子序列中不同字符的个数总和，由于答案较大，你需要输出对(10^9)+7取模后的结果。

输入描述