1.牛牛冲砖五
思路：
看懂样例即可。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> using namespace std; int main() { int t; cin >> t; string str; while (t--) { int n, k; cin >> n >> k >> str; int ans = 0; for (int i = 0; i < n; i++) { if (str[i] == 'L')ans--; else { if (i >= 2 && str[i] == str[i - 1] && str[i] == str[i - 2]) { ans += k; } else ans++; } } cout << ans << endl; } }
2.最长无重复子数组
思路：
最古老的双指针。用两个指针维护一个没有重复元素的区间，基于计数。如果新加进来的一个元素导致了出现重复元素，那么我们就收紧左区间，直到没有重复元素为止。
代码：
class Solution { public: int maxLength(vector<int>& arr) { unordered_map<int,int> mp; int ans=1; for(int i=0,j=0;i<arr.size();i++){ mp[arr[i]]++; while(j<=i&&mp[arr[i]]>=2){ mp[arr[j]]--; j++; } ans=max(ans,i-j+1); } return ans; } };
3.重排字符串
思路：
基于贪心重构字符串。为了让字符串中的每个元素都“平均”的出现，我们可以每次然出现次数最多的字符和次多的字符去“凑成”一对。为什么要尽量把出现次数多的凑成一对呢？因为这些字符最危险，越是靠后处理这些字符，越容易出现相邻重复。用一个堆去维护当前每个字符出现的次数，当堆的元素大于1的时候，我们就可以取出最多的两个字符，这两个字符一定不同，我们把这两个字符依次加入到答案中。
如果最后堆的元素为空，说明正好处理完了。如果最后堆顶元素还剩下1，说明还有一种字符还没被“安排”。如果最后这个字符的次数还剩下超过1，那么说明一定会相邻。如果最后还剩一个元素，直接加到ans末尾就行了。
代码：
#include <iostream> #include<algorithm> #include<queue> using namespace std; typedef pair<int, int> PII; int main() { int n; string str; int a[26] = {0}; priority_queue<PII> q; cin >> n >> str; if (n == 1) { cout << "yes" << endl; cout << str << endl; return 0; } for (int i = 0; i < n; i++) { int u = str[i] - 'a'; a[u]++; } for (int i = 0; i < 26; i++) { if (a[i])q.push({ a[i], i }); } string ans = ""; while (q.size() > 1) { auto t1 = q.top(); q.pop(); auto t2 = q.top(); q.pop(); char u1 = t1.second + 'a'; char u2 = t2.second + 'a'; ans += u1; ans += u2; if (t1.first - 1 > 0)q.push({ t1.first - 1, u1 - 'a' }); if (t2.first - 1 > 0)q.push({ t2.first - 1, u2 - 'a' }); } if (!q.empty() && q.top().first >= 2) { cout << "no" << endl; } else { if (!q.empty()) { char u = q.top().second + 'a'; ans += u; } } cout << "yes" << endl; cout << ans << endl; } // 64 位输出请用 printf("%lld")
