L1-003 个位数统计：从数字取模到字符串处理的进阶之路

刷题的时候看到“L1-003 个位数统计 - 15 分”这个标题第一反应是这不就是数一下每个数字出现了几次吗循环取余不就行了。但你真动手写尤其是用 C 语言在拼题 A 的在线评测系统里提交之后才会意识到这个 15 分的入门题里藏着一个很重要的分水岭——你到底是在“处理数字”还是在“处理字符串”。这篇博客就围绕“个位数统计”的完整解法展开包括为什么网络上几乎所有正规解答都用字符串读入、完整可提交的 C 语言代码、新手最容易踩的坑、以及如何把这一题的思路迁移到其他字符统计类题目上。不管你是刚开始刷 PTA 的大一学生还是想快速捡起基础语法的在职党这篇内容都能让你少走几步弯路。1. 题目到底在考什么先别急着写代码1.1 题目原意与输入输出形式“L1-003 个位数统计”出自拼题 APTA的 L1 基础题集。题面本身不复杂给定一个正整数 N要求统计 N 中每一个数字 0-9 出现的次数并按“数字:次数”的格式输出且只输出出现过的数字。例如输入100311输出应该是0:2 1:3 3:1这里有个细节容易被忽略输出要求考虑的是“N 中的每一位数字”而不是“数字本身作为整数的数值”。比如100311的开头是 1末尾也是 1中间有两个 0、两个 1、一个 3所以 1 一共出现了 3 次。这个统计对象是“位”不是“数值”。1.2 15 分题目的真实考点很多人看到这题只有 15 分觉得随便用 long long 存下 N然后循环% 10和/ 10就能过。在相当一部分评测数据里这样确实能拿到一部分分数但它恰恰踩中了这个题目的核心陷阱——N 的长度可能远超任何整数类型的表示范围。在 PTA 的常见数据设计里这类题目往往不会明确给你 N 的上限或者即使给了也大到unsigned long long都装不下。你想想unsigned long long最大能表示大约 1.8 × 10^19也就是 20 位。而“个位数统计”这类题一旦用于考察字符串处理N 是有可能给出 100 位甚至 1000 位的。所以这道题真正想考察的不是“你会不会用 % 和 /”而是你能不能意识到当数字大过机器整数能表达的范围时我们必须把它看作一串字符来处理。这个认知比写出正确答案更重要。1.3 输出格式里容易扣分的暗桩题目要求输出格式是“数字”后跟英文冒号“:”再跟次数每行一个“数字:次数”。注意三点是英文冒号不是中文冒号。每个键值对占一行行尾有没有多余空格通常不判但最好不要画蛇添足。只输出出现过的数字没出现的不要输出。这三点字面上都写了但考场上一紧张就容易忽略。尤其“只输出出现过的数字”这条会让很多同学在循环 0 到 9 时直接把所有数字都打印一遍结果 2、4、5、6、7、8、9 等次数为 0 的也被输出直接错误。正确做法是循环时判断一下cnt[i] ! 0。2. 为什么几乎所有正规解法都选择字符串读入三个层次的原因2.1 第一层整数类型根本装不下的数据范围先做一道简单的算术题。如果 N 是一个 100 位的正整数C 语言里最大的标准整数类型是unsigned long long它能表示的最大值约 18446744073709551615也就是 20 位。100 位数字显然远远超出了这个范围。你可能说那我用__int128它也只有大约 39 位依然不够。在竞赛环境里没有原生的 100 位整数类型可用。所以只要题目没有明确说“N 不超过 10^9”最稳妥的处理方式就是把它当成字符串读进来。哪怕这一题的数据恰好都很短用字符串也完全不会错而且逻辑更简单。这是一种“先保证不炸再追求优雅”的思路。2.2 第二层取模运算虽然可行但代码可读性差假设题目数据确实很小比如 N 是123456你完全可以这样写while (n 0) { int digit n % 10; cnt[digit]; n / 10; }这段代码本身没有错但它有两个隐性问题。第一个问题是如果 N 是 0循环一次都不会执行而题目说“正整数”有的变体会输入 0此时上面的循环输出就是空的明显不符合统计需求。第二个问题是统计顺序和数字在字符串中的顺序是反的。用取模得到的是从个位开始的而字符串遍历是从最高位开始的。本题只需要频次顺序无所谓但一旦题目改成“按第一次出现的顺序输出”取模写法就要额外反转字符串写法却天然满足。更重要的是当代码变复杂之后字符串遍历的语义更直观看到s[i]就是第 i 位的字符然后cnt[s[i]-0]一眼就知道在统计第 i 位数字的频次。而% 10那套写法在逻辑上绕了一层“取余数”的抽象对初学者来说并不友好。2.3 第三层字符到数字的映射是天然的下标设计字符串读入后每一位都是字符类型例如1对应的 ASCII 码是 490是 48。所以我们只要把当前字符减去0就能得到对应的数字 0 到 9而这个数字恰好可以作为数组下标cnt[s[i] - 0];这是一个极其自然的映射数字字符和它的数值相差一个固定的偏移量0。很多初学者一开始不明白s[i] - 0到底在干嘛其实就是在问“当前字符在 ASCII 表里和字符 0 差了多少”字符7的 ASCII 是 550是 48差了 7正好是它代表的数字。这种“字符偏移量作为下标”的技术后面你在统计字符串里字母出现次数、统计词频、做字符映射时都会用到。它也是本题最有迁移价值的知识点。3. 可提交的完整 C 代码与逐行注释3.1 先放完整代码#include stdio.h #include string.h int main() { char s[1005]; scanf(%s, s); int cnt[10] {0}; int len strlen(s); for (int i 0; i len; i) { cnt[s[i] - 0]; } for (int i 0; i 10; i) { if (cnt[i] 0) { printf(%d:%d\n, i, cnt[i]); } } return 0; }3.2 代码里每个关键点的意图数组大小char s[1005]怎么定一般题目数据不会超过 1000 位开 1005 留出多余空间足够。如果你不确定可以开char s[1000005]来应对极长的数据。但注意数组开太大在某些嵌入式环境下可能有栈空间风险PTA 这类在线评测通常没问题。也可以用char *s malloc(...)但入门阶段完全没必要动态分配。scanf(%s, s)的读取特性%s会跳过前置空白字符空格、换行、Tab然后读入连续的非空白字符并在末尾自动补\0。因为题目输入只有单独一个 NN 内部没有空格所以%s是最合适的读法。如果你用gets在较新版本的 C 标准中已经被移除不建议用。用fgets(s, sizeof(s), stdin)也可以但要记得它会把换行符也读进来后续处理要小心。int cnt[10] {0}为什么能全部初始化为 0在 C 语言中用 {0}初始化一个数组时第一个元素被明确赋为 0其余元素会被自动补 0。这是标准行为很多初学者写成int cnt[10];就直接用导致数组里存的是不确定的垃圾值后面cnt[s[i]-0]算出来的次数必然全错。记住局部数组不初始化内容是不确定的不是默认 0。int len strlen(s)放在循环外strlen每次调用都要遍历整个字符串找\0如果你把strlen(s)写在for循环的条件里比如for (int i 0; i strlen(s); i)那么每次循环都会重新数一遍字符串长度时间复杂度变成 O(n^2)。对于 1000 位字符串影响不大但这是一个非常不好的习惯。提前用len保存结果既是性能优化也是好习惯的养成。输出循环里的if (cnt[i] 0)这个判断对应题目要求的“只输出出现过的数字”。如果去掉那么 0 到 9 全部打印其中大部分次数是 0答案错误。3.3 时间和空间复杂度字符串长度为 n遍历一遍统计是 O(n)输出循环固定 10 次所以总时间复杂度 O(n)。空间上s数组是 O(n)cnt数组固定 O(10)可以认为是 O(1) 的附加空间。这套写法在任何评测系统里都能轻松跑进时间限制性能不是问题。4. 实测中我踩过的坑和完整的排查过程4.1 坑一忘记初始化计数器数组输出了几个天文数字第一次提交时我写的是int cnt[10];然后直接进行cnt[s[i] - 0]。本机跑的时候偶尔输出是正常的但每次运行结果不一样。后来我意识到局部变量的初始值来自栈上的残留数据完全不可控。最典型的表现是用不同的输入测试可能大多数情况正常但某一次输入后某个数字的次数突然变成了32767之类。排查方法是在循环前打印一遍cnt数组的初始值发现根本不是 0。修复方式就是改回int cnt[10] {0};。这也是我给所有初学者的第一条建议——数组初始化是肌肉记忆级别的习惯。4.2 坑二把s[i]直接当成索引导致数组越界另一个很常见的错误是cnt[s[i]];注意s[i]是字符比如0的 ASCII 码是 48。如果直接作为cnt的下标cnt[48]已经越过了cnt[10]的边界属于未定义行为程序可能崩溃也可能悄悄覆盖其他内存。我在调试时用printf(%d , s[i])打印出来的全是 48、49 这样的数字一开始还以为是输入问题后来才反应过来字符和数字是有差别的。C 语言里字符类型本质是整数但它所表示的数值是 ASCII 码而不是字面意义上的“字符内容”。所以必须做s[i] - 0的偏移把 ASCII 码映射到 0-9 区间。4.3 坑三使用getchar()时把换行符当成了数字有些同学想用逐字符读取的方式实现char c; while ((c getchar()) ! \n) { cnt[c - 0]; }这段代码在面对100311\n时看似没问题但有两个隐患。第一如果文件末尾没有换行符评测系统的输入文件通常没有多余的换行getchar()会返回EOF而EOF是-1转成char后变成一个无法预期的字符然后c - 0可能弄出负下标直接数组越界。第二题目输入可能在 N 之后还有其他内容吗本题没有但一旦下一道题目在同一行有其他字符这样读会把空格等也统计进去。最稳妥的写法是int c; while ((c getchar()) ! EOF c ! \n) { if (c 0 c 9) { cnt[c - 0]; } }可这样代码显然没有scanf(%s, s)来得简洁。所以我个人推荐入门阶段老老实实用字符串读入把getchar的细节放在后面练习。4.4 坑四输出时把循环变量搞错有个朋友问我为什么输出结果只有一行。我看他的代码for (int i 1; i 10; i) { if (cnt[i] 0) printf(%d:%d\n, i, cnt[i]); }这里循环从 1 到 10不仅漏掉了数字 0而且cnt[10]又是一次越界。输出格式要求包括 0所以循环必然是for (int i 0; i 10; i)。这个坑很蠢但在时间紧张的评测里确实容易犯。我自己的排查习惯是先拿单个数字5作为输入预期输出5:1如果程序输出5:1正常再测试0和10基本能定位循环边界问题。4.5 坑五使用strlen时忘记包含头文件如果你在代码里用了strlen但没有#include string.h有的编译器可能报隐式声明警告链接时找不到符号。虽然 PTA 的编译环境通常比较宽松但这属于规范性问题。我在本地用的编译器是 GCC不带头文件时能编译通过但会有 warning到了更严格的评测环境可能直接编译错误。所以写完代码第一件事就是检查#include是否覆盖你所用到的所有库函数。5. 测试用例与边界验证清单5.1 常规用例拿题目给的100311预期输出0:2 1:3 3:1跑一遍没问题。再试123456789应该输出 1 到 9 每一个都是 1。这验证了循环从 0 到 9 以及判断cnt[i]0的逻辑。5.2 单数字用例输入7预期输出7:1这个用例可以迅速发现你循环是否漏掉 0、数组是否越界。5.3 输入为 0 的情况虽然题目说是正整数但作为程序员要考虑健壮性。如果输入0字符串读入后s[0]0统计结果应该是0:1。但如果用取模写法while(n0)循环不会执行答案就变成了没有输出这是两种写法的一个重要差异。字符串写法天然兼容 0我看到很多变体题目会把 0 放进去所以尽量用字符串。5.4 全 0 数字的大数输入000000会怎样注意用%s读入时前导零会被保留在字符串中所以统计结果是0:6。这符合“统计位”的定义。但如果用整数读入000000会被当成 0统计结果就错了。所以这题使用字符串的另一个理由它不会丢失前导零的信息。5.5 超长用例输入一个 1000 位的字符串比如由1234567890重复 100 次组成。预期每一个数字出现 100 次。我的代码能正确输出。这个用例主要验证数组大小是否够大以及是否有性能问题。5.6 验证小技巧在本地批量跑测试我习惯把这个题的输入输出放在一个test.txt文件中然后使用命令./a.out test.txt比对输出。对于更复杂的批量测试可以写一个简单的 shell 循环把多个输入依次跑一遍。初期养成自动验证的习惯比在评测系统里反复提交要高效得多。6. 从个位数统计到字符串字符统计一套通用模板6.1 把统计数组扩展为任意字符集合“个位数统计”最核心的技术是用字符减去基准字符得到偏移量再以偏移量作为数组下标。这个思想可以扩展到任意有固定范围的字符集合。比如统计一个句子中英文字母出现次数忽略大小写初始化一个int cnt[26] {0};然后遍历字符串中的每个字符char c str[i]; if (c A c Z) c 32; // 转为小写 if (c a c z) { cnt[c - a]; }这里c - a就是字母 a 到 z 的偏移量和s[i] - 0完全是一回事。统计 ASCII 可打印字符总个数时也可以开int cnt[128]用c本身作为下标但需要小心空格和换行这些特殊字符的处理。6.2 如果数字不是字符而是其他形态怎么办有时我们要统计的不是“数字 0-9”而是“二进制串中 0 和 1 的个数”。这时可以用cnt[c - 0]但数组只需要 2 个元素。本质上还是同一套方法确定取值范围规划好偏移量。如果待统计的元素是一个字符串数组比如统计一篇英文文章中每个单词出现的次数简单数组就不够用了需要哈希表或者字典。但在 PTA 初级题库里绝大多数“XX 统计”题都可以用固定数组解决。先掌握这一套遇到更复杂的情况再去学散列表。6.3 推荐的后续练习如果你把这题吃透了我建议按这个顺序练几个同类型题目统计一句话中数字字符、大写字母、小写字母、空格分别有多少个。统计一个字符串中每个英文字母出现的次数并按照字母顺序输出非零的项。给定一个身份证号18 位统计其中各数字出现的频次并判断校验位是否正确。给定一个可能超出 long long 范围的十进制数求它各数位之和。这题很多人用整数做然后发现溢出用字符串做就非常轻松。这些练习的核心都一样识别出“这是一个字符处理问题而不是数学问题”然后套用“偏移量映射数组”的模板。7. 我最后想补充的一点小体会刷完这道题我最大的感受是简简单单一个 15 分题其实是一面照妖镜。它照出了你有没有养成“先想数据范围再选数据类型”的习惯有没有下意识地初始化数组有没有区分字符和数字的本质差异。以前我也觉得这种入门题写一遍就完事但后来带过几次新同学发现很多人卡就卡在s[i] - 0这个点上。为什么要减因为我们要的是数值 0-9不是 ASCII 码。为什么要用数组下标因为数字 0-9 正好对应 10 个桶。这个映射关系是 C 语言处理字符统计最重要的肌肉记忆。如果你现在还是对字符处理和数字处理有点混淆建议你亲手把这两种写法各写一遍一种是用long long做取模另一种是用字符串做映射。故意输入一个 25 位的数看看第一种怎么溢出第二种怎么从容通过。这个对比过程比看十篇题解都有用。“个位数统计”只是第一步但由它展开的字符统计思想会在你之后刷题路上反复出现。希望这篇博客能帮你把这一步走得扎实一点。