C++笔试强训day13

目录

1.⽜⽜冲钻五

2.最长无重复子数组

​编辑

3.重排字符串

---

1.⽜⽜冲钻五

链接

简单逻辑题，按照题目意思模拟就能过。

详细代码：

#include <iostream>
 
using namespace std;
 
int n,k;
void solve()
{
    cin >> n >> k;
    
    string s;
    cin >> s;
    
    int sum = 0;
    int cnt = 0;
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] == 'W')
        {
            if(cnt >= 2)
            {
                sum += k;
            }
            else
            {
                sum += 1;
            }
            cnt++;
        }
        else
        {
            sum -= 1;
            cnt = 0;
        }
    }
    cout << sum << endl;
}
 
int main()
{
    int t;
    cin >> t;
    while(t--)
        solve();
    
    return 0;
}

2.最长无重复子数组

链接

这种题目一眼双指针，然后晋升为滑动窗口解题：

注意进窗口和出窗口的位置以及len的更新就能AC。

// 哈希＋双指针
class Solution {
public:
    int cnt[100010] = { 0 };
    int maxLength(vector<int>& arr) {
        int n = arr.size();
 
        int l = 0;
        int r = 0;
        int len = 0;
        while(r < n)
        {
            cnt[arr[r]]++;// 进窗口
            while(cnt[arr[r]] > 1)// 出窗口（条件）
            {
                cnt[arr[l]]--;
                l++;
            }
            len = max(len, r - l + 1);
            r++;
        }
        return len;
    }
};

3.重排字符串

链接

找到填入规律就很好办，先找到次数最多的字母，隔空填入：

（例如）

然后将剩下的字母依次填入即可，注意一个细节即可：

当超出范围时，记得将填入位置的下标修改为1。

还有就是要会判断是否能重排的临界：

如上图，若是多出一个C,必然不可能重排，即C的数量 ＞（n + 1） /  2的话，直接输出noi就行了。

否则，考虑后者。

详细代码：

#include <iostream>
using namespace std;
const int N = 100010;
int n;
char s[N];
char ret[N];
int main()
{
    cin >> n >> s;
 
    int cnt[26] = { 0 }; // 统计每个字符的频次
    int maxIndex, maxCount = 0;
    for (int i = 0; i < n; i++)
    {
        if (maxCount < ++cnt[s[i] - 'a'])
        {
            maxCount = cnt[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 (cnt[i] && i != maxIndex)
            {
                while (cnt[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;
}