本文主要是介绍蓝桥杯 第 1 场算法双周赛 第1题 三带一 c++ map 巧解 加注释,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
三带一【算法赛】https://www.lanqiao.cn/problems/5127/learning/?contest_id=144
问题描述
小蓝和小桥玩斗地主,小蓝只剩四张牌了,他想知道是否是“三带一”牌型。
所谓“三带一”牌型,即四张手牌中,有三张牌一样,另外一张不与其他牌相同,换种说法,四张手牌经过重新排列后,可以组成 AAAB 型。
输入格式
第一行输入一个整数 T ,代表斗地主的轮数。
接下来 T 行,每行输入一个长度为 44 的字符串,代表小蓝的手牌。
字符 { 'A','2','3','4','5','6','7','8','9','X','J','Q','K'
} 对应代表牌面 { A,2,3,4,5,6,7,8,9,10,J,Q,K } 。
牌面中不包含大小王。
输出格式
输出 T 行,每行一个字符串,如果当前牌是“三带一”牌型,输出 Yes
,否则输出 No
。
样例输入
5
AAAA
33X3
JQKX
6566
KKKQ
样例输出
No
Yes
No
Yes
Yes
说明
“四炸”牌型不属于“三带一”牌型。
评测数据范围
数据范围:1≤501≤T≤50 。
字符中只包含:{ A,2,3,4,5,6,7,8,9,X,J,Q,K } 。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
总通过次数: 2697 | 总提交次数: 4096 | 通过率: 65.8%
难度: 中等
思路和解题方法
#include <iostream>
:包含输入输出流库,提供与标准输入输出设备的接口。#include <unordered_map>
:包含无序哈希映射库,用于存储字符和对应的出现次数。using namespace std
:使用std命名空间,简化对标准库的调用。int main()
:主函数,程序的入口。int t;
:声明一个整型变量t,用于记录测试用例的数量。string str;
:声明一个字符串变量str,用于记录输入的字符串。cin >> t;
:从标准输入读取一个整数,赋值给变量t。for (int i = 0; i < t; i++) { ... }
:循环t次,执行测试用例。cin >> str;
:从标准输入读取一个字符串,赋值给变量str。bool flag = false;
:声明一个布尔型变量flag,用于标记是否存在出现次数为3的字符。unordered_map<char, int> map;
:声明一个无序哈希映射,用于存储字符和对应的出现次数。for (int j = 0; str[j]; j++) { ... }
:遍历字符串中的每个字符,统计字符出现的次数。map[str[j]]++;
:将字符str[j]作为键,在哈希映射map中查找并使对应的值加1。for (auto &x : map) { ... }
:遍历哈希映射map,查找出现次数为3的字符。if (x.second == 3) { ... }
:如果字符的出现次数为3,则将flag设为true,并退出循环。if (flag == true)
:如果flag为true,即存在出现次数为3的字符。cout << "Yes" << endl;
:输出"Yes"到标准输出。else
:否则,即不存在出现次数为3的字符。cout << "No" << endl;
:输出"No"到标准输出。return 0;
:返回0,表示程序正常结束。
复杂度
时间复杂度:
O(n)
时间复杂度为O(n),其中n是输入字符串的长度。代码中有两个嵌套循环,分别遍历字符串和哈希映射,但每个字符只会被遍历一次,因此总体上是线性时间复杂度。
空间复杂度
O(k)
空间复杂度为O(k),其中k是字符串中不同字符的数量。代码使用了一个无序哈希映射来存储字符和对应的出现次数,最坏情况下会存储所有不同的字符,因此空间复杂度为O(k)。另外还有几个变量和固定大小的辅助空间,对总体空间复杂度的影响很小。
c++ 代码
#include <iostream>
#include <unordered_map>
using namespace std;int main() {int t; // 用于记录测试用例的数量string str; // 用于记录输入的字符串cin >> t;for (int i = 0; i < t; i++) { cin >> str; // 输入字符串bool flag = false; // 用于标记是否存在出现次数为3的字符unordered_map<char, int> map; // 使用无序哈希映射存储字符和对应的出现次数// 遍历字符串中每个字符,统计字符出现的次数for (int j = 0; str[j]; j++) {map[str[j]]++; // 字符出现次数加1}// 遍历哈希映射,查找出现次数为3的字符for (auto &x : map) {if (x.second == 3) { // 字符出现次数为3flag = true;break;}}// 输出结果if (flag == true)cout << "Yes" << endl; // 如果存在出现次数为3的字符,则输出"Yes"elsecout << "No" << endl; // 如果不存在出现次数为3的字符,则输出"No"}return 0;
}
觉得有用的话可以点点赞,支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
这篇关于蓝桥杯 第 1 场算法双周赛 第1题 三带一 c++ map 巧解 加注释的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!