牛客春招刷题训练营-2025.4.3题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 找出字符串中第一个只出现一次的字符

开数组记录字符出现次数即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    vector<int> cnt(256);
    for (auto it : s)cnt[it]++;
    for (auto it : s) {
        if (cnt[it] == 1) {
            cout << it;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

中等题 字符统计

排序：第一关键字为字符出现次数降序，第二关键字为字符ASCII码升序。
输出出现次数非 的字符。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    vector<pair<char, int>> cnt(256);
    for (auto it : s)cnt[it].second++;
    for (int i = 0; i < 256; i++)cnt[i].first = i;
    sort(cnt.begin(), cnt.end(), [](auto & a, auto & b) {
        return a.second != b.second ?
               a.second > b.second :
               a.first < b.first;
    });
    for (int i = 0; i < 256 && cnt[i].second; i++)
        cout << cnt[i].first;
    return 0;
}

困难题 相差不超过k的最多数

对每个 ，二分查找 为第一个 的数的下标，不存在则设为 。
答案为 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, (int)(upper_bound(a.begin(), a.end(), a[i] + k) - a.begin()) - i);
    cout << ans << '\n';
    return 0;
}