c++ - 均衡字符串不同字符的最小步骤数

Question

这个问题在这里已经有了答案:





How to find the minimum number of operation(s) to make the string balanced?

(5 个回答)


7 个月前关闭。




我正在尝试编写这个要求用户输入字符串的程序，我的工作是打印出均衡字符串不同字符频率所需的最少步骤数。
示例
输入

6
aba  
abba  
abbc  
abbbc  
codedigger  
codealittle 

输出

1
0
1
2
2
3

这是我的程序:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_map<char, int >m;
    vector<int> vec1, vec2;
    string s;
    int n;

    cin >> n;
    cin.ignore();

    for (int i = 0; i < n; ++i)
    {
        m.clear();
        vec1.clear();
        getline(cin, s);
        for (int i = 0; i < s.size(); i++)
            m[s[i]]++;

        for (auto itr : m)
            vec1.push_back(itr.second);

        sort(vec1.begin(), vec1.end());

        int mid = vec1[vec1.size() / 2];
        int ans = 0;

        for (auto itr : vec1)
            ans += abs(mid - itr);

        vec2.push_back(ans);
    }
    for (int i = 0; i < vec2.size(); ++i)
        cout << vec2[i] << endl;
}

我试图为每个测试用例做的是:

使用 unordered_map计算字符串的字符出现的频率。

将 map 的键值推送到 vector 。

按升序对 vector 进行排序。

计算 vector 的中间元素，以尽可能少的步长来均衡不同的字符。

结果将添加中间元素与当前元素之间的差异。

将结果推送到另一个 vector 并打印出来。

但是我的结果在第 5 个测试用例中是错误的:

1  
0  
1  
2  
3  // The actual result is 2
3  

我不明白为什么我得到错误的结果，任何人都可以帮助我吗？谢谢你的帮助!

Answer 1

问题是您的算法没有找到最佳步数。
考虑您获得错误答案的字符串:codedigger .它有 4 个频率为 1 ( coir ) 的字母和 3 个频率为 2 ( ddeegg ) 的字母。
最佳方法是不要将频率为 2 的一半字母转换为某个新字符(字符串中不存在)以使所有频率为 1。根据我的理解，您的实现正在计算这需要的步骤数。
相反，请考虑:c[o]dedigge[r]如果我更换 o与 c和 r与 i ，我得到:ccdediggei它已经均衡了字符频率。您会注意到我只进行了 2 次编辑。
所以没有给你一个解决方案，我相信这仍然可以回答你的问题？也许考虑到这一点，您可以想出一种不同的算法来找到最佳编辑次数。