最频繁的字母子串

Question

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

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

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

示例：
输入：坏蛋
4
0 8
1 4
0 5
2 7
输出：
b
一个
一个
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;
  }
}

Answer 1

下面的代码有很多内存浪费，但是每个查询都在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;
}

Answer 2

你听说过segment trees吗？

通常，遇到某个区间上的某个值的问题时，我们通常会部署线段树来处理这类问题。这棵树给出了 n*log(n) 的复杂度，非常好，我非常喜欢它们 :)

如果您还没有听说过 recursion/segment tree/map/，请停止阅读。

A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time

首先，我们不考虑出现频率最高的字母，而是考虑整个字符串中所有字符的出现。如果我们有所有字符的出现次数，我们可以很容易地找出出现次数最多的字符。

很好，让我们看看您需要的操作：

从字符串构建线段树
从线段树查询区间

如果您查看 internet 上通常的线段树实现，它们通常是一个区间内的最大值或最小值，因此它们将使用 std 构建它们的线段::最大（...）.

在我们的例子中，我们关心所有字符的出现，因此我们将使用整个字母表（仅 26 个 lol）构建我们的段

void build(int id, int l, int r, std::string str, std::vector<std::map<char, int>>& seg_tree) 
{
    if(l == r) {
        seg_tree[id][str[l]]++;
        return;
    }
    int mid = (l+r)/2;

    build(id*2, l, mid, str, seg_tree);
    build(id*2+1, mid+1, r, str, seg_tree);

    for(int i=97;i<=122;i++) {
        seg_tree[id][(char)i] = seg_tree[id*2][(char)i] + seg_tree[id*2+1][(char)i];
    }
    return;
}

查询遵循相同的格式，我们将递归地下降到树中直到间隔为 1，然后我们将返回以将较小的查询组合成较大的查询。

std::map<char, int> query(int id, int l, int r, int q, int p, std::vector<std::map<char, int>>& seg_tree) {
    std::map<char,int> mp;
    if(p < l || q > r) {
        return mp;
    }

    if(l <= q && p <= r) {
        return seg_tree[id];
    }

    int mid = (l+r)/2;

    std::map<char,int> mp1 = query(id*2, l, mid, q, p, seg_tree);
    std::map<char,int> mp2 = query(id*2+1,mid+1, r, q, p, seg_tree);

    for(int i=97;i<=122;i++) {
        mp[(char)i] = mp1[(char)i] + mp2[(char)i];
    }

    return mp;
}

然后，这里是关于如何使用线段树的总体思路

int main() {
    std::string str;
    std::cin >> str;
    
    
    std::vector<std::map<char, int>> seg_tree(4*str.size()+1);
    
    build(1,0,str.size()-1,str,seg_tree);

    std::map<char, int> mp = query(1, 0, str.size()-1, 0,str.size()-1, seg_tree);

    std::cout << mp.size() << std::endl;


    for(int i=97;i<=122;i++) {
        std::cout << (char)i << " " << mp[(char)i] << std::endl;
    }
    return 0;
}

尽管如此，线段树对于较小规模的问题来说有点矫枉过正。它的强大之处在于您可以将它概括为解决许多相同格式的问题。

然而，了解线段树数据结构对您在竞争性编程甚至编码面试中有很大帮助。

请就如何回答您的问题或更好地解释我的回答提供更多反馈:)

Answer 3

使用地图是多余的。您可以使用查找 table。它又快又小。 Demo.

#include <iostream>
#include <string>
#include <array>

using namespace std;

char find(const string& s, int left, int right)
{
  // declare an array for all 26 letters and initialize it with 0;
  // indexes are alphabet letters
  // values are letters appearances
  array<int, 26> t{};

  // fill in the array with letter count between left & right indexes
  for (int i = left; i <= right; ++i)
    t[s[i] - 'a']++; // 'a' must be index 0, so we subtract it form current letter

  // look for the maximum value; the index plus 'a' is the letter - see the table comment
  int m = -1, idx = -1;
  for (size_t i = 0; i < t.size(); ++i)
  {
    if (t[i] > m)
    {
      m = t[i]; // we have a new maximum
      idx = i; // remember where the new maximum is
    }
  }

  // the index starts from zero, so we add 'a'
  return idx + 'a';
}


int main()
{
  //
  string s;
  if (!(cin >> s))
    return -1; // bad input

  //
  int query_count;
  if (!(cin >> query_count))
    return -2;

  //
  for (int i = 0; i < query_count; ++i)
  {
    int left, right;
    if (!(cin >> left >> right))
      return -3;
    cout << find(s, left, right) << endl;
  }

  return 0;
}

Answer 4

我不认为 std::map 是错误的方法。更好的是 std::unordered_map，因为它使用快速哈希访问。

解决方案可以直接实施。但是，老实说，我怀疑这将是最快的解决方案。下面解决方案中的 usecontainers 很快，但没那么快。我需要多考虑一下。

总之。让我们画出设计草图：

从std::cin
读取测试用例数
运行一个简单的 while 循环中的所有测试用例
对于每个测试用例，获取要评估的子字符串的开始和结束位置
计算子字符串中的每个字符
使用最大堆排序并输出结果

对于所有这些，我们需要 main 中的 8 个语句。

请检查：

#include <iostream>
#include <utility>
#include <unordered_map>
#include <queue>
#include <vector>
#include <type_traits>
#include <string>

// Some Alias names for later easier reading --------------------------------------------------------------------------
using Pair = std::pair<char, size_t>;
using Counter = std::unordered_map<Pair::first_type, Pair::second_type>;
using UnderlyingContainer = std::vector<Pair>;
struct LessForSecondOfPair { bool operator ()(const Pair& p1, const Pair& p2) { 
        return (p1.second == p2.second)?(p1.first > p2.first):(p1.second < p2.second); }};
using MaxHeap = std::priority_queue<Pair, UnderlyingContainer, LessForSecondOfPair>;

// Main test code ------------------------------------------------------------------------------------
int main() {

    // Get string to be evaluated 
    if (std::string toBeEvaluated; std::cin >> toBeEvaluated)

        // And the number of test cases
        if (int numberOfTestCases{}; (std::cin >> numberOfTestCases) and numberOfTestCases > 0)

            // Now, for all testcases
            while (numberOfTestCases--)

                // Get start end end position of sub string
                if (size_t start, end; std::cin >> start >> end) {

                    // Count occurences of characters
                    Counter counter{};
                    for (char c : toBeEvaluated.substr(start, end-start-1)) counter[c]++;

                    // Output result
                    std::cout << MaxHeap(counter.begin(), counter.end()).top().first << '\n';
                }
}

最频繁的字母子串

Most frequent Alphabet Substring

c++

c++17