ABC248A Lacked Number
题意分析¶
给定一个长度为 $9$ 的字符串 $S$，其由 互不相同的数字字符组成，也就是说，$S$ 是从 $0$ 到 $9$ 这 $10$ 个数字中选出 $9$ 个。
题目要求你找出 缺失的那一个数字 并输出。
解题思路¶
本题可以抽象为一个 字符统计问题，属于字符串处理中的常规题型。
核心思想：¶
我们需要从 $0$ 到 $9$ 这 $10$ 个数字中，找出 哪个不在字符串 $S$ 中出现。由于 $S$ 中的字符都互不相同，因此只会缺失一个数字。
具体做法：¶
- 准备一个布尔数组或标记数组
vis[10]，初始全为false； - 遍历字符串 $S$ 中的每一个字符
c，将其转为整数（即c - '0'），并标记在vis中； - 最后扫描
vis[0]到vis[9]，哪个为false，说明该数字没有出现； - 输出该缺失的数字即可。
类似题型的延伸方法：字母映射技巧¶
在处理字母统计类字符串问题时，通常会将 'a' 映射为 0，'z' 映射为 25，即：
ch - 'a'对应 0～25 范围，用于映射小写字母；ch - '0'用于映射数字字符（0～9）；
这种映射方式便于建立计数数组，例如 vis[26] 或 vis[10]。
时间与空间复杂度分析¶
- 时间复杂度：$O(9 + 10) = O(1)$，因为字符串固定长度为 $9$；
- 空间复杂度：$O(1)$，标记数组
vis[10]占用常数空间。
总结¶
- 本题为经典的字符串映射与计数问题；
- 将字符映射为整数后使用布尔数组快速判断；
- 思维简单清晰，适合练习基础字符串操作。