C++日常刷题积累
今日刷题汇总 - day013
1、牛牛冲钻五
1.1、题目
1.2、思路
读完题,知道让我们统计牛牛T组游戏胜负最终获取的星数,其中规定连胜三局触发连胜建立机制获得额外的k个星数,输入n和k表示,该组完成n场比赛和连胜后可额外获得的星数k。那么,对于此题,认真理解题意,按照题目规则模拟实现即可。接下来,就是程序实现。
1.3、程序实现
理解到题意,就能想到逻辑,遍历每组字符串如果是‘L’则start–,如果是’W’则start++,其次,如果是连续WWW’就触发获得k颗星。注意判断的字母是小写和边界控制即可。
#include <iostream>
#include <string>
using namespace std;
int main()
{
int T;
cin >> T;
int n,k;
string str;
while(T--)
{
cin >> n >> k;
cin >> str;
int start = 0;
int len = str.size();
for(int i = 0;i < len; i++)
{
if(str[i] == 'L')
start-=1;
else if(i-1>=0 && i-2>=0 && str[i-1] == 'W' && str[i-2] == 'W')
{
start += k;
}
else
start+=1;
}
cout << start << endl;
}
return 0;
}
2、最长无重复子数组
2.1、题目
2.2、思路
读完题,知道让求一个长度为n的数组中,最长无重复元素的子数组长度,其中注意无重复子数组意思是该子数组中所有数字不同,且位置是连续的,与值的大小无关。容易被示例带偏思路。通过思考和分析,这里最好采用滑动窗口的思路解决问题,因为如果是蛮力法这里是操作两个指针通向的移动,所以使用滑动窗口进行优化。那么滑动窗口的思路主要分为以下四个步骤:
(1)、进窗口:利用哈希统计当前字符个数;
(2)、判断:遍历到字符串,判断字符是否已经出现过;如果出现两次,那么计数为2,则执行出窗口
(3)、出窗口:将左指针位置的元素出窗口,并向右移动;
(4)、更新结果:一次循环结束后,判断最大长度即可。
接下来,就是程序实现。
2.3、程序实现 – 滑动窗口
首先,定义哈希用于窗口统计数目,再定义两个指针lfet和right,right从首字母开始遍历,将遍历的字符进窗口,直到判断到当前字符已经存在窗口里,则将left位置的元素出窗口,再向右滑动窗口,最后不断更新最大长度即可。滑动窗口的巧妙之处在于,通过hash[arr[i]]同步窗口元素的计数,达成滑动窗口的效果。因为arr[i]决定的是相同元素,所以在hash中的下标位置是相同的从而完成hash[arr[right]] > 1判断逻辑。
class Solution {
public:
int hash[100010] = { 0 };
int maxLength(vector<int>& arr)
{
int left = 0, right = 0, n = arr.size();
int ret = 0;
while (right < n)
{
hash[arr[right]]++; // 进窗⼝
while (hash[arr[right]] > 1)// 判断
{
hash[arr[left]]--; // 出窗⼝
left++;
}
ret = max(ret, right - left + 1); // 更新结果
right++;
}
return ret;
}
};
3、重排字符串
3.1、题目
3.2、思路
读完题,知道让处理一组由小写字母组成的字符串,进行重排,使得重排后,相邻字母不相同。如果能成功重排,则输出"yes"和重排后的字符串,否则输出"no"。那么,根据题目内容,需要推导重排字符之间的关系,比如位置关系、数量关系,比如以a、a、b、b、c、c、c 7个字符为例,使得满足重排,那么放置a后可以放b或c,第二个位置放置b后,可以放置a或c,如果此时再放a,那么之后放b或c,继续放置b,那么就是abab之后随便放c都会失败,所以推导出,存在多个字符时,以一定的顺序依次放入,则acbacbc这样就能满足重排,输出“yes”. 然后数量关系,如果其中一个字符c数量大于整个字符串的一半时,a,a,b,b,c,c,c,c,c,c,c,c这种情况也会导致失败,直接输出"no"即可,所以能否重排受最多元素的数量影响。那么,就可以先处理字符多的字母先放置,其余字符按照一定的次序放置即可。既然如此,进一步分析,就可以将同一组相同字符错位放置,所以综上所述,主要分为以下几个步骤:
(1)、每次循环处理同一批相同字符;
(2)、优先处理出现次数最多的字符;
(3)、每一次放置都错位放置,即隔一个奇数位置放置;
(4)、对于是否能重排的处理(max)c <= (n+1)/2,则能重排;否则不满足重排。
3.3、程序实现
首先,根据思路分析写好输入n和需要的处理的str数组,然后定义hash数组利用哈希统计最多的哪个字符,结合循环遍历str将得到的最多字符的下标以及最多字符的个数分别存放在maxIndex和maxcount中,然后,根据最多字符的个数判断能否重排,不能输出“no”,能则输出“yes”,再进行下一步处理。
#include <iostream>
using namespace std;
const int N = 100010;
int n;
char str[N];
int main()
{
cin >> n >> str;
int hash[26] = { 0 }; // 统计每个字符的频次
int maxIndex, maxCount = 0;
for(int i = 0; i < n; i++)
{
if(maxCount < ++hash[str[i] - 'a'])
{
maxCount = hash[str[i] - 'a'];
maxIndex = s[i] - 'a';
}
}
if(maxCount > (n + 1) / 2)
cout << "no" << endl;
else
{
cout << "yes" << endl;
}
// 打印结果
for(int i = 0; i < n; i++) cout << ret[i];
cout << endl;
return 0;
}
接着,处理输出重排后的数组情况,那么可以先定义一个返回数组ret,用于存放处理好的数组元素方便返回输出,然后,按照思路步骤处理最多字符且按照偶数位置相隔1个奇数位放置即可,然后将剩余的字符,依次按照第一个奇数位顺序放置空余位置,这里发现处理好奇偶位的关系后,奇数位任意放置都不会相邻字符相同。其中注意越界的处理和判定index超出后置1再放置即可。最后再利用循环遍历rets数组输出结果即可。
#include <iostream>
using namespace std;
const int N = 100010;
int n;
char str[N];
char ret[N];
int main()
{
cin >> n >> str;
int hash[26] = { 0 }; // 统计每个字符的频次
int maxIndex, maxCount = 0;
for(int i = 0; i < n; i++)
{
if(maxCount < ++hash[str[i] - 'a'])
{
maxCount = hash[str[i] - 'a'];
maxIndex = str[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(hash[i] && i != maxIndex)
{
while(hash[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;
}