【C++】 —— 笔试刷题day_13
一、牛牛冲钻五标题描述
https://i-blog.csdnimg.cn/direct/4cf5035ddc054c509898724ce266deb4.png#pic_center
标题说，牛牛在玩炉石传说，现在牛牛进行了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;
else
ret+=1;
}
}
cout<<ret<<endl;
}
return 0;
}
二、最长无重复子数组
标题描述
https://i-blog.csdnimg.cn/direct/ce7bb08fe87549f0b1575ee8c48e61b3.png#pic_center
这道题，给定一个数组arr，让我们找到其中没有重复元素的最长子数组；返回这个最长子数组的长度。
算法分析
看到这道题，了解过滑动窗口的可以说是一眼秒了，这种找子串题目。
现在我们先来看暴力解法：
分别从0、1、…n位置向后遍历，寻找没有重复字符的子串；
这里在寻找没有字符元素的子串时，我们需要记载区间内每一个元素出现的次数，那这里就要用到一个hash去记载。
https://i-blog.csdnimg.cn/direct/ab1b6a04e5524b1da3ded647e80efb6c.png#pic_center
我们看上图，当i在第一个位置找到没有重复元素的最长子数组时；
如果我们i++后，让j再从i位置开始向后遍历，如果i位置对应的元素不等于j位置对应的元素，那肯定还是走到和从0位置最长的那一个位置。
那这样我们就没有须要让j再从i位置向后遍历了，而是i++，直到i遍历过和j位置元素相称的那一个位置。
那这样我们还得窗口的主要思想就出来了：
[*]入窗口：将right位置的元素放到hash表中。
[*]出窗口：当区间内出现了重复的元素，那就进行出窗口操纵，直到区间内没有重复的元素。
[*]更新结果：出窗口操纵之后，区间肯定是满足条件的，更新结果即可。
代码实现
class Solution {
public:
int hash={0};
int maxLength(vector<int>& arr) {
// write code here
int ret = 0;
int left = 0, right = 0;
while(right<arr.size())
{
hash]++;
while(hash] > 1)
{
hash]--;
left++;
}
ret = max(ret,right - left+1);
right++;
}
return ret;
}
};
三、重排字符串
标题描述
https://i-blog.csdnimg.cn/direct/0af01b06d78147b884326dd6135020c5.png#pic_center
标题给了我们一个字符串，然后让我们判断，这个字符串可否通过重新排列（只改变字母的顺序，不改变数目），让相邻的字母都不相同。
如果不可以就输出no；如果可以，就输出yes，并输出其中一种排列方式。
算法分析
这里这道题，标题描述很简单，但是我们会感觉到无从动手；
这个就直接说思路了，就是使用贪心
我们先来看它们示例：aabbccc，它可以通过排列变成相邻字符都不相同的字符；
这里，我们先来排列ccc，由于c出现的次数最多
https://i-blog.csdnimg.cn/direct/4df75fb1b80d4195b1fb090d0accbb2c.png#pic_center
观察上图，很显然，每隔一个位置，放置一个字符，这样那个放置一样的字符数最多（那我们就可以使用这一点来判断，是否能够通过排列构成相邻元素是否都不相同）
什么意思呢？
如果每隔一个位置，放置一个字符，这样如果我们出现次数最多的字符，如果它从第一个位置开始，每隔一个位置放置一个，直到末了，还有剩余，那肯定不能通过排列变成满足条件的字符串。
如果还没到末了一个，次数最多的字符就放置完了，那其他的还是按照每隔一个位置放置一个，就肯定能够通过排列变成满足条件的字符串。
我们在分析，当出现数目最多的字符，它出现的次数 > 给定字符串的长度+1的一半，那可以就不能通过排列来满足条件了。（这里就不叙述原因了，通过分析上述每隔一个位置放置一个字符，极端情况可以分析出来。
那如果可以通过排列满足条件，那我们就要进行排列了。
排列我们遵循的大体规则还是每隔一个位置，放置一个字符。
这里我们需要先对出现此时最多的字符先进行放置，放置完再依次放置其他字符即可
代码实现
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n;
int cnt = {0};
cin>>n;
int MaxCount = 0;
char MaxChar = 0;
for(int i=0;i<n;i++)
{
char ch = 0;
cin>>ch;
cnt++;
if(cnt > MaxCount)
{
MaxCount = cnt;
MaxChar = ch;
}
}
if(MaxCount > (n+1)/2)
cout<<"no"<<endl;
else
{
cout<<"yes"<<endl;
string ret(n,0);
//先放置出现次数最多的字符
int i =0;
while(MaxCount--)
{
ret = MaxChar;
i+=2;
}
//放置其他字符
for(int j = 0;j<26;j++)
{
if(j+'a' != MaxChar)
{
while(cnt--)
{
if(i>=n) i = 1;
ret = j+'a';
i+=2;
}
}
}
cout<<ret<<endl;
}
return 0;
}
到这里，本日刷题就结束了
简单总结：本日标题解决方法：模拟整个过程、滑动窗口、贪心。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]