​​​​​​​​48days强训——day13

admin管理员组

文章数量:1438857

​​​​​​​​48days强训——day13

​第一题：牛牛冲钻五

链接：牛牛冲钻五

题目描述 牛牛最近在玩炉石传说，这是一款一对一对战的卡牌游戏，牛牛打算努力冲上钻五分段，获得丰厚的天梯奖励。 炉石传说的段位可以用星数来表示，具体规则为：若牛牛本场失败，则扣除一星；若牛牛本场获胜，需要看牛牛是否触发了连胜奖励，若牛牛获得了至少三连胜（即本局对局的上一局和上上局都获胜）则获得kkk星，否则获得一星。 现在给出牛牛游玩的nnn场记录，请你判断牛牛最终的星数和初始星数的差。 输入描述: 第一行输入一个整数T(1≤T≤104)T(1\leq T\leq 10^4)T(1≤T≤104)，测试组数。 每个测试的第一行输入两个整数n(3≤n≤105)n(3\leq n\leq 10^5)n(3≤n≤105)和k(2≤k≤100)k(2\leq k \leq 100)k(2≤k≤100)，牛牛共打了几场比赛与连胜奖励的星数。 接下来一行输入一个长为nnn的字符串，之中WWW表示获胜，LLL表示失败，保证只含有这两种字母。 保证所有用例的Σn≤105\Sigma n\leq 10^5Σn≤105。 输出描述: 对每个测试用例，输出一个整数，表示牛牛最终的星数和初始星数的差。 示例1 输入 2 5 3 WWWLW 5 3 WLLLL 输出 5 -3

题解：这是一道简单的模拟题，知道了游戏规则就不难了。

代码：

代码语言：javascript代码运行次数：0运行复制

#include<bits/stdc++.h>
using namespace std;
int t,n,k;
string s;
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n >> k >> s;
        int ret = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == 'L') ret--;
            else
            {
                if(i - 1 >= 0 && i - 2 >= 0 && s[i - 1] == 'W' && s[i - 2] == 'W')
                    ret += k;
                else
                    ret += 1;
            }
        }
        cout <<  ret << endl;
    }
    return 0;
}

第二题：最长无重复子数组

链接：最长无重复子数组_牛客题霸_牛客网

描述 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组 数据范围：0≤arr.length≤1050≤arr.length≤105，0<arr[i]≤1050<arr[i]≤105 示例1 输入： [2,3,4,5] 返回值： 4 说明： [2,3,4,5]是最长子数组 示例2 输入： [2,2,3,4,3] 返回值： 3 说明： [2,3,4]是最长子数组 示例3 输入： [9] 返回值： 1 示例4 输入： [1,2,3,1,2,3,2,2] 返回值： 3 说明： 最长子数组为[1,2,3] 示例5 输入： [2,2,3,4,8,99,3] 返回值： 5 说明： 最长子数组为[2,3,4,8,99]

题解：经典的滑动窗口的题目，注意更新值的地方。

代码：

代码语言：javascript代码运行次数：0运行复制

class Solution {
  public:
    int maxLength(vector<int>& arr)
    {
        unordered_map<int, int>hash;
        int cur1 = 0, cur2 = 0, ret = 0;
        while (cur2 < arr.size()) //4
        {
            if (cur2 < arr.size() && hash[arr[cur2]] == 0)
            {
                hash[arr[cur2]]++;
                cur2++;       
            }
            else
            {
                hash[arr[cur1]]--;
                hash.erase(arr[cur1]);
                cur1++;
            }
            ret = max(ret, cur2 - cur1);
        }
        return ret;
    }

};

第三题：重排字符串

链接：重排字符串

题目描述 小红拿到了一个只由小写字母组成的字符串。她准备把这个字符串重排（只改变字母的顺序，不改变数量） 重排后小红想让新字符串不包含任意两个相同的相邻字母。 你能帮帮她吗？ 输入描述: 第一行一个正整数 nnn ，代表字符串的长度。 (1≤n≤105)(1 \leq n \leq 10^5)(1≤n≤105) 第二行为一个长度为 nnn 的、只由小写字母组成的字符串。 输出描述: 如果可以完成重排，请在第一行输出一个“yes”，第二行输出重排后的字符串。如果有多个正解，输出任意即可。 如果不能重排，则直接输出“no” 示例1 输入 5 aaaaa 输出 no 示例2 输入 7 aabbccc 输出 yes cabcabc 说明 bcbcaca也是正确答案（正确答案还有很多，输出任意即可）

题解：先统计字符频率，找出最大频率字符。若其频率不过半则可行，先填最大频率字符，再填其他字符，保证相邻不同

代码：

代码语言：javascript代码运行次数：0运行复制

#include<bits/stdc++.h>
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 i = 0;
        while(maxcount--)
        {
            ret[i] = maxindex+'a';
            i += 2;
        } 
        
        for(int j = 0;j < 26;j++)
        {
            if(hash[j] && j != maxindex)
            {
                while(hash[j]--)
                {
                    if(i >= n) i = 1;
                    ret[i] = j + 'a';
                    i += 2;
                }
            }
        }
    }
    for(int i = 0; i < n; i++) cout << ret[i];
        cout << endl;
    return 0;
}

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-20，如有侵权请联系 cloudcommunity@tencent 删除前往查看字符串hashint测试数组

本文标签： ​​​​​​​​48days强训day13