【C++】刷题强训(day13)--牛牛冲钻五、最长无重复字数组、重排字符串

目录

1、牛牛冲钻五

1. 题目

1.2 思路

1.3 代码实现

2、最长无重复子数组

2.1 题目

2.2 思路

2.3 程序实现

 3、重排字符串

3.1 题目

3.2 思路

3.3 代码实现

---

刷题汇总：传送门！

1、牛牛冲钻五

1. 题目

1.2 思路

由题可知，赢一局则得一颗星，输一局扣一颗星，连胜三局则会触发连胜机制，获得额外 的k颗星，最终输出得了多少星星。本题按照题目模拟实现即可。

1.3 代码实现

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

2、最长无重复子数组

2.1 题目

2.2 思路

由题可知，要求求一个长度为n的数组中最长无重复元素的子数组 的长度，其中注意：该子数组中元素全不相同，并且位置是连续的，但是与值的大小无关。这里可以使用滑动窗口的思路来解决。

1. 进窗口：利用哈希表统计当前字符个数
2. 判断：遍历到字符串，判断字符是否已经出现过；如果出现两次，则计数为2，并出窗口
3. 出窗口：将左指针位置的元素出窗口，向右移动
4. 更新结果：一次循环结束后，判断最大长度即可。

2.3 程序实现

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

 3、重排字符串

3.1 题目

3.2 思路

读完题，知道让处理一组由小写字母组成的字符串，进行重排，使得重排后，相邻字母不相同。如果能成功重排，则输出"yes"和重排后的字符串，否则输出"no"。

那么，根据题目内容，需要推导重排字符之间的关系，比如位置关系、数量关系，比如以a、a、b、b、c、c、c7个字符为例，使得满足重排，那么放置a后可以放b或c，第二个位置放置b后，可以放置a或c，如果此时再放a，那么之后放b或继续放置b，那么就是abab之后随便放c都会失败，所以推导出，存在多个字符时，以一定的顺序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 代码实现

#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;
}

---

本篇完，下篇见！