当前位置：首页 > news >正文

【C++】 —— 笔试刷题day_13

news 2025/4/18 10:31:37

一、牛牛冲钻五

题目描述

在这里插入图片描述

题目说，牛牛在玩炉石传说，现在牛牛进行了n场游戏，让我们判断牛牛上了几颗星。

首先输入一个T，表示T组数据；

然后输入n和k，表示一个进行了n场数据，k表示连胜三场及以上获得的分数

然我们输出最后的星数和起始星数的差；

其中L表示失败，减一颗星；W表示胜利，如果连胜超过3场就获得k颗星，否则获得1可星。

算法分析

这道题算是比较简单的，我们只需要模拟一下整个过程就好了；

题目中是连胜超过3场，就获得k颗星；

这里我们就要定义一个变量来记录连胜，当连胜场次超过3就获得k颗星；否则获得1颗星。

代码实现

#include<iostream>
using namespace std;int main()
{int T;cin>>T;while(T--){int n,k;cin>>n>>k;int count = 0;int ret = 0;for(int i = 0;i<n;i++){char ch;cin>>ch;if(ch == 'L'){ret-=1;count = 0;}else{count++;if(count>=3)ret+=k;elseret+=1;}}cout<<ret<<endl;}return 0;
}

二、最长无重复子数组

题目描述

在这里插入图片描述

这道题，给定一个数组arr，让我们找到其中没有重复元素的最长子数组；返回这个最长子数组的长度。

算法分析

看到这道题，了解过滑动窗口的可以说是一眼秒了，这种找子串问题。

现在我们先来看暴力解法：

分别从0、1、…n位置向后遍历，寻找没有重复字符的子串；

这里在寻找没有字符元素的子串时，我们需要记录区间内每一个元素出现的次数，那这里就要用到一个hash去记录。

在这里插入图片描述

我们看上图，当i在第一个位置找到没有重复元素的最长子数组时；

如果我们i++后，让j再从i位置开始向后遍历，如果i位置对应的元素不等于j位置对应的元素，那肯定还是走到和从0位置最长的那一个位置。

那这样我们就没有必要让j再从i位置向后遍历了，而是i++，直到i遍历过和j位置元素相等的那一个位置。

那这样我们还得窗口的主要思想就出来了：

入窗口：将right位置的元素放到hash表中。
出窗口：当区间[left , right]内出现了重复的元素，那就进行出窗口操作，直到区间内没有重复的元素。
更新结果：出窗口操作之后，区间[left , right]一定是满足条件的，更新结果即可。

代码实现

class Solution {
public:int hash[100001]={0};int maxLength(vector<int>& arr) {// write code hereint ret = 0;int left = 0, right = 0;while(right<arr.size()){hash[arr[right]]++;while(hash[arr[right]] > 1){hash[arr[left]]--;left++;}ret = max(ret,right - left+1);right++;}return ret;}
};

三、重排字符串

题目描述

在这里插入图片描述

题目给了我们一个字符串，然后让我们判断，这个字符串能否通过重新排列（只改变字母的顺序，不改变数量），让相邻的字母都不相同。

如果不可以就输出no；如果可以，就输出yes，并输出其中一种排列方式。

算法分析

这里这道题，题目描述很简单，但是我们会感觉到无从下手；

这个就直接说思路了，就是使用贪心

我们先来看它们示例：aabbccc，它可以通过排列变成相邻字符都不相同的字符；

这里，我们先来排列ccc，因为c出现的次数最多

在这里插入图片描述

观察上图，很显然，每隔一个位置，放置一个字符，这样那个放置一样的字符数最多（那我们就可以使用这一点来判断，是否能够通过排列组成相邻元素是否都不相同）

什么意思呢？

如果每隔一个位置，放置一个字符，这样如果我们出现次数最多的字符，如果它从第一个位置开始，每隔一个位置放置一个，直到最后，还有剩余，那肯定不能通过排列变成满足条件的字符串。

如果还没到最后一个，次数最多的字符就放置完了，那其他的还是按照每隔一个位置放置一个，就肯定能够通过排列变成满足条件的字符串。

我们在分析，当出现数量最多的字符，它出现的次数 > 给定字符串的长度+1的一半，那可以就不能通过排列来满足条件了。（这里就不叙述原因了，通过分析上述每隔一个位置放置一个字符，极端情况可以分析出来。

那如果可以通过排列满足条件，那我们就要进行排列了。

排列我们遵循的大体规则还是每隔一个位置，放置一个字符。

这里我们需要先对出现此时最多的字符先进行放置，放置完再依次放置其他字符即可

代码实现

#include <iostream>
#include <string>
using namespace std;
int main()
{int n;int cnt[26] = {0};cin>>n;int MaxCount = 0;char MaxChar = 0;for(int i=0;i<n;i++){char ch = 0;cin>>ch;cnt[ch-'a']++;if(cnt[ch-'a'] > MaxCount){MaxCount = cnt[ch-'a'];MaxChar = ch;}}if(MaxCount > (n+1)/2)cout<<"no"<<endl;else{cout<<"yes"<<endl;string ret(n,0);//先放置出现次数最多的字符int i =0;while(MaxCount--){ret[i] = MaxChar;i+=2;}//放置其他字符for(int j = 0;j<26;j++){if(j+'a' != MaxChar){while(cnt[j]--){if(i>=n) i = 1;ret[i] = j+'a';i+=2;}}}cout<<ret<<endl;}return 0;
}