【笔试训练】day12

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")