科大讯飞嵌入式软件实习笔试

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

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

第一题：小y删数字

给定一个长度为n的数组，数组元素为a1, a2, . . . , an，每次能删除任意a的任意一位，求将所有数字变成0最少需要几步。例如103若删除第1位则变成3;若删除第2位则变成13;若删除第3位则变成10。输入描述第一行一个正整数n代表数组长度。接下来一行n个数第j个数代表a。

1≤n ≤10^5 0≤ai≤10^9

输出描述

输出一行一个数代表答案。

示例1

输入

5

10 13 22 100 30

输出

7

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

int main() {
    int n;
    cin >> n;

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

    int cnt = 0;
    for (int num : nums) {
        while (num > 0) {
            if (num % 10 != 0) cnt++;
            num /= 10;
        }
    }
    cout << cnt << endl;

    return 0;
}

第二题：小红的字符串切割

小红拿到了一个字符串，她希望你帮她切割成若干子串，满足以下两个条件:

子串长度均为不小于3的奇数。

子串内部的字符全部相同。

输入描述

第一行输入一个正整数n，代表字符串长度。第二行输入一个字符串，仅由小写字母组成。1 <n ≤200000输出描述如果无解，请输出-1。否则按顺序输出若干个字符串，用空格隔开。

示例1

输入

8

aaabbbbb

输出

aaa bbbbb

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    cin.ignore();
    string line;
    getline(cin, line);

    vector<string> list;

    char pre = '.';
    string sb = "";

    for (char c : line) {
        if (pre == '.' || c == pre) {
            pre = c;
            sb += c;
        }
        else {
            list.push_back(sb);
            sb = "";
            pre = c;
            sb += c;
        }
    }
    if(!sb.empty()) list.push_back(sb);

    vector<string> res;
    for (const string& s : list) {
        if (s.length() % 2 != 0) {
            res.push_back(s);
        }
        else {
            if (s.length() < 6) {
                cout << -1;
                return 0;
            }
            res.push_back(s.substr(0, 3));
            res.push_back(s.substr(3));
        }
    }
    for (size_t i = 0; i < res.size(); ++i) {
        if (i > 0) cout << " "; // 在单词之间添加空格
        cout << res[i];
    }

    return 0;

}

第三题：小红的数字匹配

定义一个“模板串”为一个由数字字符和′?"组成的字符串。我们可以通过将问号替换成数字字符来得到正整数。显然，一个模板串可能会和多个正整数匹配。例如: "1?2"可以和102或者132等正整数匹配。请注意，匹配的正整数不能包含前导零，例如"??1"可以匹配101，但不能匹配001。小红拿到了一个模板串，她想知道，和这个模板串匹配的正整数中，第k小的是多少?

输入描述

第一行输入一个正整数t，代表询问次数。接下来的2* t行，每两行为一次询问: 第一行输入一个字符串，仅由数字字符和?'组成。第二行输入一个正整数k，代表询问的是第k小。

1≤t ≤ 10^4 1≤k≤10 ^9

字符串长度不超过30。

输出描述

输出t行，每行输出一个答案。如果一共都没有k个匹配的正整数，则输出-1。否则输出第小的匹配的正整数。

示例1

输入

4

??1

1

22?

100000000

2??

3

000???

1

输出

101

-1

202

-1

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

void solve() {
    string input;
    getline(cin, input);
    int k;
    cin >> k;
    cin.ignore();

    int wh = 0; // 问号数量
    for (char c : input) {
        if (c == '?') wh++;
    }

    if ((input[0] == '?' && pow(10, wh - 1) * 9 < k) || (input[0] != '?' && pow(10, wh) < k) || (input[0] == '0')) {
        cout << -1 << endl;
        return;
    }

    string strk = to_string(k - 1); // 将k-1转换为字符串
    reverse(strk.begin(), strk.end()); // 反转字符串

    bool flag = false;
    if (input[0] == '?') flag = true;

    int n = input.length();
    int j = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (input[i] == '?') {
            if (j < strk.length()) {
                input[i] = strk[j++];
            } else {
                input[i] = '0';
            }
        }
    }

    if (flag) input[0] = (input[0] - '0' + 1) + '0'; // 数字字符加1

    cout << input << endl;
}

int main() {
    int t;
    cin >> t;
    cin.ignore();

    while (t--) {
        solve();
    }

    return 0;
}