时间戳

首页 > 解决方案 > 在最少的操作中实现字符串所有字符的相同频率。（所有字符都从 'a' 到 'z'）

c++ - 在最少的操作中实现字符串所有字符的相同频率。（所有字符都从 'a' 到 'z'）

问题描述

我们需要找到使给定字符串中所有字符的频率相等所需的最小替换次数，其中替换意味着我们可以将字符串中的任何字符替换为其他字符。

**所有字符应从“a”到“z”范围。

我找到了字符串中所有字符的频率，然后对其进行排序以找到中位数，然后以中位数为参考计算达到相同频率所需的成本。我不知道我哪里出错了。不是实际的逻辑，但最轻微的想法将不胜感激。

#include <bits/stdc++.h>
using namespace std;
long int min(int A[], long int n)
{
    long int cost = 0;
    sort(A, A + n);
    long int K = A[n / 2];
    for (long int i = 0; i < n; ++i) {
        if (A[i] - K)
            cost += abs(A[i] - K);
    }
    if (n % 2 == 0) {
        long int tempcost = 0;
        K = A[(n / 2) - 1];
        for (long int i = 0; i < n; ++i) {
            if (A[i] - K)
                tempcost += abs(A[i] - K);
        }

        cost = min(cost, tempcost);
    }
    return cost;
}

int main()
{
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;

        long int arr[26];
        for (int i = 0; i < 26; i++) {
            arr[i] = 0;
        }

        long int n = s.length();

        long int count = 0;
        for (long int i = 0; i < n; i++) {
            arr[s[i] - 'a']++;
        }

        for (int i = 0; i < n; i++) {
            if (arr[i]) {
                count++;
            }
        }
        int a[count], j = 0;

        for (long int i = 0; i < n; i++) {
            if (arr[i]) {
                a[j++] = arr[i];
            }
        }

        cout << min(a, count) << endl;
    }

    return 0;
}

预期结果：输入：1 aaaaabbbbccd 输出：3

标签： c++

解决方案

注意：我在最后提出了一个建议，但关于 OP 程序：

所有字符都应该是从“a”到“z”的范围

在主要 

arr[s[i] - 'A']++;

一定是

arr[s[i] - 'a']++;

这样做改变执行是：

pi@raspberrypi:/tmp $ ./a.out

1
aab
1

    long int arr[26];
    for (int i = 0; i < 26; i++) {
        arr[i] = 0;
    }

可能就是这样：

    long int arr[26] = { 0 };

使用蛮力的解决方案

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

bool isAsolution(const string & s)
{
  int count['z' - 'a' + 1] = { 0 };

  for (auto c : s)
    count[c - 'a'] += 1;

  string::const_iterator it = s.begin();
  int count0 = count[*it++ - 'a'];

  while (it != s.end())
    if (count[*it++ - 'a'] != count0)
      return false;

  return true;
}

void search(string & s, size_t pos, unsigned nChanges, unsigned & minChanges, string & sol)
{
  if (pos == s.length()) {
      // nChanges <  minChanges, useless to check
    if (isAsolution(s)) {
      minChanges = nChanges;
      sol = s;
    }
  }
  else if (nChanges < (minChanges - 1)) {
    for (char c = 'a'; c <= 'z'; c += 1) {
      // the string is modified to avoid a lot of copies
      char old = s[pos];

      s[pos] = c;
      search(s, pos + 1, (old == c) ? nChanges : (nChanges + 1), minChanges, sol);
      s[pos] = old;
    }
  }
}

int main(int argc, char ** argv)
{
  if (argc == 1) {
    cout << "Usage : " << *argv << " <string> ...  <string>" << endl;
    return 0;
  }

  while (*++argv) {
    string s = *argv;

    for (auto c : s) {
      if ((c < 'a') || (c > 'z')) {
        cout << "invalid input, chars must be between a and z" << endl;
        return 0;
      }
    }

    if (s.empty() || isAsolution(s))
      cout << s << " is already a solution" << endl;
    else {
      unsigned min = ~0u;
      string sol;

      search(s, 0, 0, min, sol);
      cout << min << " changes to do " << sol << " from " << s << endl;
    }
  }

  return 0;
}

而不是读取字符串的数量然后读取它们在参数中给出的，更实用

例子 ：

pi@raspberrypi:/tmp $ g++ -pedantic -Wall c.cc
pi@raspberrypi:/tmp $ ./a.out aab aze aaaaabbbbccd
1 changes to do aaa from aab
aze is already a solution
2 changes to do aaaacbbbbccc from aaaaabbbbccd

在valgrind下：

pi@raspberrypi:/tmp $ valgrind ./a.out aab aze aaaaabbbbccd
==8364== Memcheck, a memory error detector
==8364== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==8364== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==8364== Command: ./a.out aab aze aaaaabbbbccd
==8364== 
1 changes to do aaa from aab
aze is already a solution
2 changes to do aaaacbbbbccc from aaaaabbbbccd
==8364== 
==8364== HEAP SUMMARY:
==8364==     in use at exit: 0 bytes in 0 blocks
==8364==   total heap usage: 2 allocs, 2 frees, 21,248 bytes allocated
==8364== 
==8364== All heap blocks were freed -- no leaks are possible
==8364== 
==8364== For counts of detected and suppressed errors, rerun with: -v
==8364== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)

正如您看到的aaaaabbbbccd只需要 2 处更改，而不是 3 处 :-)

推荐阅读