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

本文主要是介绍【错题集-编程题】重排字符串（贪心 + 构造），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客对应题目链接：重排字符串 (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;
}