牛客对应题目链接：重排字符串 (nowcoder.com)
力扣对应题目链接：1054. 距离相等的条形码 - 力扣（LeetCode）
一、分析题目
- 每次去处理一批相同的字符。
- 优先处理出现次数最多的字符。
- 每次拜访字符的时候，间隔一个格子。
能否进行重排的判定标准：
- x <= (n+1)/2：能进行重排
- x > (n+1)/2：不能进行重排
二、代码
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; }
三、反思与改进
因为这道题目之前在力扣上做过类似的，所以基本思路很清晰，不过最后不知道是哪块细节没有处理好，导致只过了 33.33% 的样例。崩溃了，看了题解之后，发现是在正解前面少打印了一个 "yes"，审题不仔细！！这种低级错误不能再犯，否则以后笔试会吃大亏！
