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

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

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

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

第一题：

牛牛拥有一个长度为 n 的01 串，现在他想知道，对于每个字符，在它前面的最近的不同字符的下标是多少？

输入描述

本题为多组测试数据，第一行输入一个正整数 T(1<=t<=100)，代表测试数据组数。对于每组测试数据，第一行输入一个正整数 n(1<=n<=1000)，代表初始 01串的长度。第二行输入一个长度为 n的01 串，代表初始字符串。

输出描述

对于每组测试数据，一行输出 n 个整数 a1,a2,...,an，其中 ai 代表初始字符串中第 i 个位置的字符前面，最近的不同字符的下标是 ai，特殊的，如果前面不存在不同字符，则输出 -1 表示不存在。

示例 1

输入

1 4 1101

输出

-1 -1 2 3

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

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int p0 = -1, p1 = -1;
        vector<int> res(n, -1);
        
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c == '0') {
                res[i] = p1;
                p0 = i + 1;
            } else {
                res[i] = p0;
                p1 = i + 1;
            }
        }
        
        for (int i = 0; i < n; ++i) {
            if (i > 0) cout << " ";
            cout << res[i];
        }
        cout << endl;
    }
    return 0;
}

第二题

给定n个数字A1,A2,..An，请求出这些数字中出现次数小于等于k的最小的数。

输入描述

第一行正整数n,k，接下来一行n个正整数，第i个表示Ai 1<=k<=n<=10^5,1<=Ai<=10^9

输出描述

一行一个整数，表示答案。如果不存在出现次数少于等于k次的数字，输出-1

示例 1

输入

5 2 1 1 1 2 3

输出

2

说明

1出现了三次，不合法；2,3均只出现了一次，其中2最小

示例 2

输入

8 2 1 1 4 5 7 1 3 3

输出

3

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int solve(int n, int k, const vector<int>& nums) {
    unordered_map<int, int> counter;
    for (int num : nums) {
        counter[num]++;
    }

    vector<int> sorted_keys;
    for (const auto& pair : counter) {
        sorted_keys.push_back(pair.first);
    }
    sort(sorted_keys.begin(), sorted_keys.end())