gpt4 book ai didi

c++ - 最常见的字母子串

转载 作者:行者123 更新时间:2023-12-02 01:52:38 24 4
gpt4 key购买 nike

我的逻辑适用于较小的输入,我如何才能更好地接受较大的输入。

问)
该程序必须接受仅包含小写字母的字符串 S 和 Q 查询作为输入。每个查询包含两个整数,表示 S 中子字符串的起始索引和结束索引。对于每个查询,程序必须打印指定子字符串中最常出现的字母表。如果有两个或多个字母相同的频率,那么程序必须打印按字母顺序排列最少的字母。

边界条件:
2 <= S 的长度 <= 1000
1 <= Q <= 10^5

示例:
输入:坏坏床
4
0 8
1 4
0 5
2 7
输出:
b
一个
一个

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char** argv)
{
string s;
cin >> s;
int k;
cin >> k;
int x, y;
while (k--)
{
cin >> x >> y;
map<char, int>counter;
string ss = s.substr(x, y - x + 1);
set <char>sample;
for (auto i : ss)
sample.insert(i);
int maxx = -1, st; char anss;
for (auto i : sample)
if ((st = count(ss.begin(), ss.end(), i)) > maxx)
{
maxx = st;
anss = i;
}
cout << anss << endl;
}
}

最佳答案

以下代码会浪费大量内存,但每个查询的查找时间都是O(1):

int main() {
std::string s;
int q = 0, start = 0, end = 0;
std::cin >> s;
std::cin >> q;

auto mem = std::make_unique<int[]>(26 * s.length());
for (int i = 0; i < s.length(); i++) {
mem[i * 26 + s[i] - 'a']++;
if (i < (s.length()-1)) {
for (int l = 0; l < 26; l++) {
mem[(i+1) * 26 + l] = mem[i * 26 + l];
}
}
}

for (int i = 0; i < q; i++) {
std::cin >> start >> end;
int max_val = 0;
int max_idx = -1;
for (int l = 0; l < 26; l++) {
auto v = (mem[end * 26 + l] - mem[start * 26 + l]);
if (v > max_val) {
max_val = v;
max_idx = l;
}
}

std::cout << (char)('a' + max_idx) << std::endl;
}

return 0;
}

关于c++ - 最常见的字母子串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/70043418/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com