题目讲解
题目要求:
我们需要判断一个压缩后的字符串是否被充分压缩。充分压缩的定义是:相邻的两个压缩元素的字符互不相同。也就是说,对于压缩后的字符串中的每一个元素(由字符和长度组成),不能有连续的两个元素具有相同的字符。
输入格式:
* 第一行是一个整数 kkk,表示压缩后的字符串的元素数量。
* 接下来的 kkk 行,每行是一个字符 cic_ici 和一个整数 numinum_inumi ,表示第 iii 个压缩元素的字符和长度。
输出格式:
* 如果字符串被充分压缩,输出 Yes;否则输出 No。
示例分析:
* 示例1:
* 输入:
* 解释:三个元素的字符分别是 aaa、bbb、ccc,相邻字符均不相同,因此输出 Yes。
* 示例2:
* 输入:
* 解释:前两个元素的字符都是 aaa,相邻字符相同,因此输出 No。
代码讲解
代码注释
1. 头文件和命名空间:
* #include <bits/stdc++.h> 是一个万能头文件,包含了所有标准库头文件。
* using namespace std 允许直接使用标准库中的名称(如 cin、cout)而不需要加 std:: 前缀。
2. 主函数:
* 程序的入口点。
3. 读取输入:
* 读取压缩元素的数量 kkk。
4. 初始化变量:
* ppp 用于存储前一个字符,初始化为空字符 '\0'。
* flagflagflag 是一个布尔标记,初始为 true(即 1),表示默认是充分压缩的。
5. 循环处理每个压缩元素:
* 循环 kkk 次,每次读取一个字符 ccc 和一个整数 numnumnum。
6. 检查相邻字符是否相同:
* 如果当前字符 ccc 与前一个字符 ppp 相同,则将 flagflagflag 设为 false(即 0),表示未充分压缩。
7. 更新前一个字符:
* 将 ppp 更新为当前字符 ccc,以便下一次比较。
8. 输出结果:
* 根据 flagflagflag 的值输出 Yes 或 No。
9. 程序结束:
* 返回 0,表示程序正常结束。
总结
* 算法思路:
* 遍历所有压缩元素,检查当前字符是否与前一个字符相同。
* 如果发现任何相邻字符相同的情况,立即标记为未充分压缩。
* 最后根据标记输出结果。
* 时间复杂度:
* 只需要一次遍历,时间复杂度为 O(k)O(k)O(k),其中 kkk 是压缩元素的数量。
* 由于 kkk 最多是 10610^6106,这种复杂度是完全可行的。
* 空间复杂度:
* 只使用了常数个额外变量(ppp 和 flagflagflag),空间复杂度为 O(1)O(1)O(1)。
这个解法高效且简洁,能够正确处理题目中的所有情况。