字节青训-比赛配对问题 、组成字符串ku的最大次数
比赛配对问题
问题描述
小R正在组织一个比赛，比赛中有
n支队伍参赛。比赛遵循以下独特的赛制：
- 如果当前队伍数为 偶数，那么每支队伍都会与另一支队伍配对。总共进行
n / 2场比赛，且产生n / 2支队伍进入下一轮。- 如果当前队伍数为 奇数，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行
(n - 1) / 2场比赛，且产生(n - 1) / 2 + 1支队伍进入下一轮。小R想知道在比赛中进行的配对次数，直到决出唯一的获胜队伍为止。
测试样例
样例1：
输入：
n = 7
输出：6样例2：
输入：
n = 14
输出：13样例3：
输入：
n = 1
输出：0
解题思路：
问题理解
你需要计算从 n 支队伍开始，直到决出唯一获胜队伍为止，总共进行的配对次数。每次配对都会减少队伍的数量，直到只剩下一个队伍。
关键点
- 偶数队伍：每轮配对后，队伍数量减半。
- 奇数队伍：随机轮空一支队伍，其余队伍配对，队伍数量减少一半多一个。
解题思路
- 初始条件：如果
n为 1，直接返回 0，因为不需要任何配对。 - 递归或迭代：
- 如果
n是偶数，配对次数为n / 2，剩余队伍数为n / 2。 - 如果
n是奇数，配对次数为(n - 1) / 2，剩余队伍数为(n - 1) / 2 + 1。
- 如果
- 累加配对次数：每次递归或迭代时，累加当前的配对次数，直到队伍数变为 1。
最终代码：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int solution(int n) {
// 如果只有一支队伍，不需要配对
if (n == 1) return 0;
int pairs = 0; // 初始化配对次数
// 循环直到队伍数变为1
while (n > 1) {
if (n % 2 == 0) {
// 偶数队伍的处理
pairs += n / 2; // 当前轮次的配对次数
n /= 2; // 剩余队伍数减半
} else {
// 奇数队伍的处理
pairs += (n - 1) / 2; // 当前轮次的配对次数
n = (n - 1) / 2 + 1; // 剩余队伍数减半多一个
}
}
return pairs; // 返回总的配对次数
}
int main() {
cout << (solution(7) == 6) << endl;
cout << (solution(14) == 13) << endl;
cout << (solution(1) == 0) << endl;
return 0;
}
运行结果：
组成字符串ku的最大次数
问题描述
给定一个字符串 ss，该字符串中只包含英文大小写字母。你需要计算从字符串中最多能组成多少个字符串
"ku"。每次可以随机从字符串中选一个字符，并且选中的字符不能再使用。字符串中的字符大小写可以忽略，即大写和小写字母视为相同。例如，输入
"AUBTMKAxfuu"，从中最多能组成 1 个"ku"。
测试样例
样例1：
输入：
s = "AUBTMKAxfuu"
输出：1样例2：
输入：
s = "KKuuUuUuKKKKkkkkKK"
输出：6样例3：
输入：
s = "abcdefgh"
输出：0
解题思路：
问题理解
我们需要从给定的字符串 s 中，计算最多能组成多少个字符串 "ku"。字符的大小写可以忽略，即大写和小写字母视为相同。
数据结构选择
为了统计字符 'k' 和 'u' 的数量，我们可以使用一个计数器来记录每个字符的出现次数。由于字符的大小写不敏感，我们可以将所有字符转换为小写（或大写）来统一处理。
算法步骤
- 初始化计数器：创建两个计数器，分别用于统计字符
'k'和'u'的出现次数。 - 遍历字符串：遍历字符串
s，将每个字符转换为小写（或大写），然后根据字符是'k'还是'u'来增加相应的计数器。 - 计算结果：字符串
"ku"的组成次数取决于'k'和'u'中数量较少的那个。因此，结果为min(count_k, count_u)。
最终代码：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // for std::min
using namespace std;
int solution(const string& s) {
int count_k = 0;
int count_u = 0;
// 遍历字符串，统计 'k' 和 'u' 的数量
for (char c : s) {
char lower_c = tolower(c); // 转换为小写
if (lower_c == 'k') {
count_k++;
} else if (lower_c == 'u') {
count_u++;
}
}
// 返回 'k' 和 'u' 中数量较少的那个
return min(count_k, count_u);
}
int main() {
cout << (solution("AUBTMKAxfuu") == 1) << endl;
cout << (solution("KKuuUuUuKKKKkkkkKK") == 6) << endl;
cout << (solution("abcdefgh") == 0) << endl;
}运行结果：
原文地址：https://blog.csdn.net/m0_73302939/article/details/143633371
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！