【错题集-编程题】重排字符串（贪心 + 构造）

牛客对应题目链接：重排字符串 (nowcoder.com)

力扣对应题目链接：1054. 距离相等的条形码 - 力扣（LeetCode）

一、分析题目

二、代码

1、没看题解之前AC的代码

//牛客代码(看了题解之后AC的代码)
#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    string res=s;
    char maxValue=0;
    int maxCount=0;
    unordered_map<char, int> hash;
    for(auto x : s)
    {
        hash[x]++;
        if(hash[x]>maxCount)
        {
            maxCount=hash[x];
            maxValue=x;
        }
    }
    int k=0;
    while(maxCount--)
    {
        res[k]=maxValue;
        if(k>=n)
        {
            cout << "no" << endl;
            return 0;
        }
        k+=2;
    }
    hash[maxValue]=0;
    for(auto& [a, b] : hash)
    {
        while(b>0)
        {
            if(k>=n) k=1;
            res[k]=a;
            k+=2;
            b--;
        }
    }
    cout << "yes" << endl;
    cout << res << endl;
    return 0;
}

//力扣AC代码
class Solution {
private:
    unordered_map<int, int> hash;
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int n=barcodes.size();
        vector<int> res(n);
        int maxValue=0;
        int maxCount=0;
        for(auto x : barcodes)
        {
            hash[x]++;
            if(hash[x]>maxCount)
            {
                maxCount=hash[x];
                maxValue=x;
            }
        }
        int k=0;
        while(maxCount--)
        {
            res[k]=maxValue;
            k+=2;
        }
        hash[maxValue]=0;
        for(auto& [a, b] : hash)
        {
            while(b>0)
            {
                if(k>=n) k=1;
                res[k]=a;
                k+=2;
                b--;
            }
        }
        return res;
    }
};

2、值得学习的代码

//牛客
#include <iostream>

using namespace std;

const int N = 100010;

int n;
char s[N];
char ret[N];

int main()
{
    cin >> n >> s;
 
    int hash[26] = { 0 }; // 统计每个字符的频次
    int maxIndex, maxCount = 0;
    for(int i = 0; i < n; i++)
    {
        if(maxCount < ++hash[s[i] - 'a'])
        {
            maxCount = hash[s[i] - 'a'];
            maxIndex = s[i] - 'a';
        }
    }
 
    if(maxCount > (n + 1) / 2) cout << "no" << endl;
    else
    {
        cout << "yes" << endl;
        int index = 0;
        // 先去摆放出现次数最多的
        while(maxCount--)
        {
            ret[index] = maxIndex + 'a';
            index += 2;
        }
        // 处理剩下的
        for(int i = 0; i < 26; i++)
        {
            if(hash[i] && i != maxIndex)
            {
                while(hash[i]--)
                {
                    if(index >= n) index = 1;
                    ret[index] = i + 'a';
                    index += 2;
                }
            }
        }
        // 打印结果
        for(int i = 0; i < n; i++) cout << ret[i];
        cout << endl;
    }
    return 0;
}