东华OJ第46-50题详解：数组、字符串、排序与算法基础入门

1. 先聊聊东华OJ第46-50题这组题目前阵子把东华OJ的题从第1题往后刷刷到46-50这组的时候明显感觉和前面那些纯考语法、考输入输出的题不太一样了。前面十几道题基本就是“照着模板敲”考察的是你会不会用scanf、printf、if-else、for循环。但从这个区间开始题目开始加入了一些“需要自己想清楚再动手”的成分比如对数组做处理、字符串的边界判断、查找和排序的逻辑组织。用大白话说就是从“这个语法我会不会”过渡到“这个问题的解法我想不想得到”。这组题适合两类人看。一类是正在刷东华OJ、刚好卡在40到60题之间的初学者另一类是想了解OJ判题规则、想搞清楚为什么代码本地跑得好好的上传就WAWrong Answer答案错误的同学。我会把每题的题型判断、核心思路、容易踩的坑全部拆开讲一遍也会给出可以直接复用的代码框架。尤其是那些“本地运行正常、OJ上一交就错”的经典原因我会单独拿出来分析因为这可能是刷OJ过程中最打击人、也最能涨经验的地方。先交代一下背景。东华OJ指的是东华大学在线评测系统刷题方式和主流OJ平台完全一样题目会给出若干组输入样例和输出样例你提交的代码通过标准输入读取数据通过标准输出打印结果裁判程序会用隐藏的测试数据来比对你的输出。乍一听很简单但隐藏数据往往专门挑你代码的漏洞比如最大数据量、空数据、重复元素、边界值、数组下标越界等等。46-50这组题几乎把上面这些坑都踩了个遍所以我建议你不要只看“AC了就完事”而是要顺手把这五道题涉及的思维方式梳理出来后续刷到更难的数据结构题时基础会扎实很多。我整理这组题的时候把每一道的题型、考点、难度系数、典型坑点都过了一遍先给一个速查总览后面再逐题展开。题号核心考点难度常见失分点46数组元素统计与去重偏低计数数组初始化、重复输出的处理47字符串处理与边界判断中等字符串结尾符、长度计算48顺序查找/二分查找中等升序前提、找不到时的返回值49最大公约数与最小公倍数偏低数据类型溢出、辗转相除的终止条件50结构体排序与多关键字比较中等偏上比较函数写错、稳定性要求从这个表能看出来第46到第50题正好覆盖了算法入门阶段最核心的几个基础算法数组操作、字符串、查找、数论基础、排序。这也是很多学校OJ在布置作业时比较惯用的出题思路——前几道题巩固语法中间这组题开始考察算法思维。把这一组啃下来后面再做链表、栈、队列、递归这种更抽象的内容至少不会被“读不懂题”卡住。2. 逐题思路拆解从读懂题到写出解法2.1 第46题数组统计与去重先想清楚“用什么存数据”第46题我印象比较深因为它的核心考点在“统计”和“去重”这两个动作上。题目给出一组数据让你输出出现次数满足条件的元素或者输出去重之后的结果。不同学校的OJ版本可能细节略有差异但骨干逻辑是一致的你得在遍历数据的过程中记录下每个元素出现了多少次再根据条件决定输出什么。最容易想到的做法是两层循环外层遍历每个元素内层再从头扫一遍统计它出现了几次。数据量小的时候能过但数据量大一点就容易超时。我这里更推荐用“计数数组”的思路这也是后面很多题的基础如果数据范围有限比如元素是0到100之间的整数直接开一个int 数组下标表示元素值数组存的是这个值出现的次数。遍历原始数据的时候每读到一个数x就执行 count[x]这一步的时间复杂度是O(n)比两层循环的O(n²)快一个量级。这里有一个初学者必踩的坑计数数组一定要先清零。很多人定义 int count[1000]; 就直接用本地跑的时候运气好没问题但OJ的测试数据一来上一次运行残留的脏数据就会导致统计结果完全不对。正确姿势是写完 int count[1000] {0}; 或者用 memset(count, 0, sizeof(count)); 来初始化。再说说去重。如果题目要求按原顺序输出不重复的元素我建议你在遍历原数组的同时用另一个标记数组记录“这个值是否已经输出过”。每访问一个元素先查标记数组如果没输出过就输出然后把标记置为1。这道题的高频错误是把重复元素也输出了一遍原因往往是漏掉了标记数组的更新逻辑。2.2 第47题字符串处理所有问题几乎都出在边界字符串题在OJ里是“看起来简单、做起来全是坑”的典型。第47题通常是回文判断、字符统计或字符串反转这一类。题目本身不难但字符串有几个特殊性结尾有 \0、输入可能包含空格、下标从0开始、长度需要单独计算。任何一个环节没注意WA就等着你。以最常见的回文判断来说最简单的写法是把字符串反转后和原串比较。但很多同学会踩这样一个坑用 char str[100]; gets(str); 读取然后直接计算 strlen(str)却忘记了数组中实际还有一个结尾的 \0。虽然在很多场景下 strlen 已经帮你把 \0 排除在外了但自己写循环时经常会多算一位或少算一位导致判断出错。我个人更推荐用双指针思路一个指针从字符串头部开始另一个从尾部开始两边往中间走直到相遇或交叉。每次比较 str[i] 和 str[j]只要发现不等就说明不是回文。这个写法代码量少也不容易出错而且时间复杂度同样是O(n)。判断结束条件是 i j这个地方不要写成 i j否则中间那个元素会被比较两次虽然不影响结果但逻辑上不够干净。另外要特别提醒如果题目要求处理包含空格的字符串千万不要用 scanf(%s, str)因为 %s 遇到空格就停止读取了。这个时候应该用 gets() 或者 fgets()但需要注意 fgets 会把你敲的回车符也读进来需要手动把结尾的 \n 替换成 \0否则后面的判断就全乱了。这个细节是我自己在刷题时踩过多次的坑列出来给各位提个醒。2.3 第48题查找类题目别忽视“数据是否有序”这个前提第48题是查找题无非是给你一个数列和一个目标值让你输出目标值在数列中的位置或判断是否存在。这类题的解法严重依赖于输入数据是否有序所以拿到题第一步不是写代码而是先判断数据是不是按升序或降序排好的。如果数据无序那只能用顺序查找从第一个元素开始往后逐个比遇到相等的就记下下标循环完了还没找到就输出-1。这个没什么好说的注意下标从0开始还是从1开始和题目要求对齐就行。东华OJ这类题有时候要求输出的是“第几个元素”也就是1-based下标你如果直接输出了数组下标0-based就会导致全部结果都比标准答案小1这种错误很难排查因为样例往往刚好把下标绕过去。如果题目明确说数据已经按升序排序那就要考虑用二分查找。二分查找的模板很固定左边界 l 设为0右边界 r 设为 n-1循环条件是 l r取中点 mid (l r) / 2然后比较 nums[mid] 和目标值的大小决定把区间缩小到左半部分还是右半部分。这里有个隐蔽的坑是 mid (l r) / 2 在 l 和 r 都很大的时候可能溢出虽然OJ题目数据一般不会变态到那种程度但养成写 mid l (r - l) / 2 的习惯总归是好的。写二分查找容易错的地方还有一个循环结束后 l 的位置其实代表了“第一个大于等于目标值的位置”这个性质在后面的“插入位置”类题目里会用到但如果你只是要判断某个值是否存在别忘了在循环里找到匹配时及时 return否则你会得到 l 而不是真实位置答案自然就错了。2.4 第49题最大公约数和最小公倍数记住“先除后乘”第49题是数学类基础题一般让你算两个正整数的最大公约数GCD和最小公倍数LCM。这题的算法本身很固定最大公约数用辗转相除法也叫欧几里得算法。代码短到只有几行但它背后有一个很重要的细节很多人没注意到。辗转相除法的核心是gcd(a, b) gcd(b, a % b)一直递归或循环到余数为0此时的除数就是最大公约数。用循环写就是这样int gcd(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; }这段代码建议直接背熟因为它太常用了。最小公倍数的公式也不是 b 乘 a 再除最大公约数这一种写法需要注意运算顺序lcm(a, b) a / gcd(a, b) * b注意这套写法的顺序很重要。如果写成 a * b / gcd(a, b)当 a 和 b 比较大的时候中间的乘积可能溢出int的范围导致结果完全错乱。先除后乘就不会有这个问题。这也是很多老手反复强调的一个点刷题时千万别忽略。2.5 第50题结构体排序比较函数是唯一难点第50题通常就开始上综合难度了常见考点是“学生信息排序”或者“成绩排名”输入一组记录比如学号、姓名、成绩要求按某个规则排序输出。没有结构体概念的同学可能还在用好几个平行数组分别存学号、姓名、成绩排序的时候手动同步交换几个数组代码写起来又长又容易漏。正确思路是定义一个结构体把每一条记录的所有字段打包在一起然后用C标准库里的 qsort 排序。比如typedef struct { int id; char name[50]; int score; } Student;qsort 的用法是固定的四个参数分别是要排序的数组首地址、元素个数、单个元素大小、比较函数指针。关键是写比较函数。如果你想按成绩从高到低排写成int cmp(const void *a, const void *b) { Student *sa (Student *)a; Student *sb (Student *)b; return sb-score - sa-score; }这里有一个初学者常犯的错误把返回类型写成 int结果return两个分数之差没问题但如果你要对字符串排序直接 return sa-name sb-name 就完全不对了必须用 strcmp。另外如果成绩相同题目可能要求按学号升序排这时比较函数要写成“先比成绩、成绩相等再比学号”的多关键字比较漏掉任何一个排序条件都会导致和标准答案不一致。3. 现场写代码一段能直接复用的参考实现3.1 第50题的完整参考代码C语言很多同学问过我结构体排序到底怎么把输入输出串起来我直接贴一段自己当时提交时能过题的完整代码以“N个学生信息按键值排序输出”为例方便你直接对照。需要注意不同学校OJ的题目细节不太一样但框架可以复用。#include stdio.h #include stdlib.h #include string.h typedef struct { char id[20]; char name[50]; int score; } Student; // 比较规则分数降序分数相同按学号升序 int cmp(const void *a, const void *b) { Student *sa (Student *)a; Student *sb (Student *)b; if (sa-score ! sb-score) { return sb-score - sa-score; } return strcmp(sa-id, sb-id); } int main() { int n; while (scanf(%d, n) ! EOF) { Student stu[1000]; for (int i 0; i n; i) { scanf(%s %s %d, stu[i].id, stu[i].name, stu[i].score); } qsort(stu, n, sizeof(Student), cmp); for (int i 0; i n; i) { printf(%s %s %d\n, stu[i].id, stu[i].name, stu[i].score); } } return 0; }这里有两个点值得说。第一是 while (scanf(%d, n) ! EOF)OJ题目经常用“多组测试数据直到输入结束”的方式给出数据如果你只读一组就退出只能过样例过不了全部分数。第二是 qsort 的比较函数签名必须是 const void * 类型很多第一次用的人在这里犯迷糊强制类型转换之后就对了。3.2 输入输出细节和OJ判题机制聊到OJ就不得不澄清一个很多新手没搞明白的问题OJ的判题系统完全不看你代码里的注释、变量名、代码风格它只看两件事——程序的输出和标准答案是否完全一致以及是否在规定时间和内存内跑完。所以代码长一点、变量名丑一点也不怕怕的是输出多了空格、少了换行、或者末尾多打印了一个空行。这些格式错误PE很多时候只凭肉眼根本看不出来解决办法是下载样例数据自己终端里跑一遍然后用diff命令逐字节比较输出。这也提醒我们刷OJ时第一优先级不是“写出很优雅的代码”而是“写出能精确匹配输出的代码”。再展开说一下“多组输入”的问题。很多题目会写“输入包含多组测试数据每组占一行”但不会明确告诉你一共有几组。这时候 while (scanf(...) ! EOF) 几乎是万能写法它能帮你一直读到文件结束符。使用它的前提是每次循环体内都要重新初始化需要用到的变量或数组否则上一组数据残留的值会污染下一组的计算结果。4. 刷题时踩过的坑常见错误与排查对照表4.1 编译出错和本地能过、OJ过不了的经典原因刷OJ最让人崩溃的一件事就是本地编译器跑得好好的一交上去就报编译错误CE或者答案错误WA。结合我的经验最常见的几个原因如下使用了非标准头文件或函数。比如 Turbo C 环境里常用的 conio.h、getch()在OJ的评测环境里根本不存在。把 int main() 写成了 void main()。部分编译器会容忍但OJ的编译器往往比较严格。中文标点混进了代码。全角分号、全角括号、中文引号肉眼很难看出来但编译器一遇到就报错。数组开小了。题目说数据量最多1000习惯性开了100本地测试用少量数据自然没问题OJ用最大数据一测就数组越界表现可能是WA、RE运行时错误甚至TLE。忘了处理多组输入或者处理完之后没有重置全局变量。我在这里整理了一个“错误类型排查速查表”每次提交WA之后按表格逐项排查效率会高很多错误类型典型表现优先排查方向编译错误 CE提交后直接编译失败头文件是否齐全函数签名是否正确是否有中文符号答案错误 WA程序能跑结果不对边界条件、初始化、比较函数逻辑、多组数据残留运行时错误 RE程序崩溃退出数组越界、除零、空指针、递归无出口时间超限 TLE长时间没有输出算法复杂度过高是否该用更优解法格式错误 PE结果对但多空格/少换行输出格式、行尾空格、末尾空行4.2 边界数据与初始化问题上面这个表里WA是出现频率最高的错误而这个错误里又有很大一部分是“边界数据和初始化”导致的。我举三个具体例子。第一个例子数组统计题。int count[1000] {0}; 写不写初始化本地测试可能都没问题但只要OJ的测试数据里有超过某个阈值的数字count 数组就会越界。更隐蔽的是如果你忘了在每组测试数据之间重置 count上一组数据的统计结果就会叠加到下一组上导致输出错得莫名其妙。第二个例子字符串题。用 char str[100]; scanf(%s, str); 读入正常字符串没问题但如果输入里包含空格scanf 读到空格就停了此时字符串只读了一半后续所有基于完整字符串的逻辑全部错乱。这种错很难从代码本身看出来必须回头去读题目确认输入格式里到底允不允许空格。第三个例子排序题的比较函数。qsort 的比较函数返回正数、零、负数分别表示a排在b后面、两者相等、a排在b前面。很多人写成绩排序时只写了 return a-score b-score返回的是1或0没有负数的情况这会导致排序结果不稳定和标准答案不一致。正确的写法是用差值 return b-score - a-score或者显式判断返回1、-1、0。4.3 实用的调试与排查技巧说完了错误类型再分享几个实际排查问题的小技巧。第一个技巧是“中点打印法”。在代码关键位置加printf输出中间变量比如二分查找里每次更新的 l 和 r统计题里每读一个数后 count 的变化看一遍运行过程的日志基本能定位是逻辑问题还是数据处理问题。不过提交前一定要把调试用的printf删掉或注释掉否则输出多了调试信息必WA。第二个技巧是“用最小样例测试”。遇到WA时不要直接去网上搜答案先试着构造几个极端情况空输入、只有一个元素、所有元素都相同、元素已经是排好序的、元素全部逆序、数值取到题面上限。这些数据往往能瞬间击穿你的代码逻辑。举个简单的例子做回文判断时字符串长度是1是不是回文答案是。如果你没考虑这种情况判断逻辑就可能出错。做去重时所有元素都一样时输出一个还是多个这些都是边界条件。第三个技巧是“重看一遍题目”。有时候WA不是代码问题是读题问题。题目要求“输出元素在序列中的位置”可能说的是第几个位置而不是数组下标题目要求“按成绩降序成绩相同按姓名升序”你只实现了成绩降序漏了姓名。这种低级失误在连续刷题疲劳的时候特别容易犯所以每次WA之后第一件事不是改代码而是重新读三遍题。5. 从46-50题说开去算法入门阶段的刷题建议5.1 做题顺序与时间分配很多人刚开始刷OJ的时候有个误区觉得题目做得越多越好于是一路狂刷遇到不会的题就查题解、背代码表面上看进度很快实际上基础完全没打牢。我个人的体会是像东华OJ 46-50这种“基础算法过渡组”的题目适合慢下来精做。每道题做完之后对比一下自己的解法和其他人的解法看看有没有更优的思路再把题目的条件改一改比如数据量变大、要求变成倒序输出、增加关键字重新写一遍。这种变式训练比闷头刷10道新题更管用。时间分配上我建议每一道题留出“三遍时间”第一遍自己独立思考哪怕想不出来也要先把暴力解法写出来第二遍对照题解或参考代码搞清楚优化点在哪里第三遍关掉所有资料从零开始自己写一遍。这个流程看起来费时间但只要坚持几组题下来你的代码能力会有肉眼可见的提升。我刷46-50这五道题按这个流程走总共花了大概一个周末——第一天做前两题并复盘第二天冲刺后面三题时间也算不亏。5.2 用“错题本”思维复盘刷OJ的另一个建议是建一个自己的错题本。不需要很复杂一个文档就行记录以下信息题号、题目在考什么、我的错误解法是什么、错因是什么、正确思路是什么。尤其要记的是“为什么我没想到这个思路”这比单纯记录代码重要得多。我翻了一下自己的刷题日志46-50这组题里我最常见的错因是三类没有初始化数组、比较函数写错、漏了多组输入这些问题如果不记下来下次换个题目依然会犯。复盘还有一个作用就是帮你发现自己对某个知识点掌握不牢。比如第50题如果你做排序时反复出错说明你对结构体和qsort的理解还停留在“背模板”阶段最好的补救方式不是继续做新排序题而是回头把结构体、指针、内存分配这一节重新过一遍。这也是我认为“从题目回溯知识点”比“按顺序啃教材”更高效的原因——带着问题学习印象会深刻得多。5.3 从AC到理解别急着做完就划掉最后再聊一点心态上的东西。OJ上的ACAccepted只是说你过了评测说明你的输出和标准答案一致但完全不代表你已经理解了解法。我见过不少同学复制粘贴别人的代码过了AC然后开心地标记为“已掌握”等到期中考试或者面试手写代码时大脑一片空白。46-50这组题本身不难但它们是“从模仿到独立解题”的分水岭。如果你能做到拿到题后不查任何资料30分钟内写出能通过全部测试数据的代码那这组题才算真正刷透了。我个人判断一道题是否吃透会问自己三个问题第一如果数据量扩大100倍我的解法还会超时吗第二如果输入数据是特殊值我的代码能正确处理吗第三如果让我给另一个同学讲出这道题的思路我能不看代码把逻辑说清楚吗这三个问题都能答上来这道题才算真正属于你了。46到50这五道题其实每道题都值得用这三个问题自测一遍。数组统计题问自己数据量很大的时候计数数组会不会爆字符串题问自己输入包含空格和超长字符串时怎么办查找题问自己数据完全逆序时二分查找还成立吗数学题问自己两个数都是int上限时先乘后除会不会溢出排序题问自己遇到完全相同学号或者说如果比较函数漏了第二个关键字会怎样。把这些问题在脑子里过一遍比多做十道题有用得多。