蓝桥杯 第 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 } 。

运行限制

总通过次数: 2697  |  总提交次数: 4096  |  通过率: 65.8%

难度: 中等

思路和解题方法

1. #include ：包含输入输出流库，提供与标准输入输出设备的接口。
2. #include ：包含无序哈希映射库，用于存储字符和对应的出现次数。
3. using namespace std：使用std命名空间，简化对标准库的调用。
4. int main()：主函数，程序的入口。
5. int t;：声明一个整型变量t，用于记录测试用例的数量。
6. string str;：声明一个字符串变量str，用于记录输入的字符串。
7. cin >> t;：从标准输入读取一个整数，赋值给变量t。
8. for (int i = 0; i < t; i++) { ... }：循环t次，执行测试用例。
9. cin >> str;：从标准输入读取一个字符串，赋值给变量str。
10. bool flag = false;：声明一个布尔型变量flag，用于标记是否存在出现次数为3的字符。
11. unordered_map map;：声明一个无序哈希映射，用于存储字符和对应的出现次数。
12. for (int j = 0; str[j]; j++) { ... }：遍历字符串中的每个字符，统计字符出现的次数。
13. map[str[j]]++;：将字符str[j]作为键，在哈希映射map中查找并使对应的值加1。
14. for (auto &x : map) { ... }：遍历哈希映射map，查找出现次数为3的字符。
15. if (x.second == 3) { ... }：如果字符的出现次数为3，则将flag设为true，并退出循环。
16. if (flag == true)：如果flag为true，即存在出现次数为3的字符。
17. cout << "Yes" << endl;：输出"Yes"到标准输出。
18. else：否则，即不存在出现次数为3的字符。
19. cout << "No" << endl;：输出"No"到标准输出。
20. return 0;：返回0，表示程序正常结束。

复杂度

        时间复杂度:

                O(n)

时间复杂度为O(n)，其中n是输入字符串的长度。代码中有两个嵌套循环，分别遍历字符串和哈希映射，但每个字符只会被遍历一次，因此总体上是线性时间复杂度。

        空间复杂度

                O(k)

空间复杂度为O(k)，其中k是字符串中不同字符的数量。代码使用了一个无序哈希映射来存储字符和对应的出现次数，最坏情况下会存储所有不同的字符，因此空间复杂度为O(k)。另外还有几个变量和固定大小的辅助空间，对总体空间复杂度的影响很小。

c++ 代码

#include 
#include 
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) { // 字符出现次数为3
                flag = true;
                break;
            }
        }
 
        // 输出结果
        if (flag == true)
            cout << "Yes" << endl; // 如果存在出现次数为3的字符，则输出"Yes"
        else
            cout << "No" << endl; // 如果不存在出现次数为3的字符，则输出"No"
    }
 
    return 0;
}

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。