★ FEATURED ARTICLE 我最早在DHUOJ上把基础题从1刷到24的时候一直觉得OJ也就那么回事输入、循环、判断、输出套模子而已。但等到25、26、27这三题连在一块做的时候我第一次感觉到自己的“循环”和“边界处理”还远没到家。当时我是在东华大学的在线评测系统DHUOJ上按题单顺序刷的这三题被归在“基础”区虽然题面都不长可它们恰好覆盖了OJ入门阶段三个最容易翻车的地方素数与循环、整数拆位、字符串遍历。今天把这三道题的完整思路、代码和踩坑记录整理出来给正在刷DHUOJ基础题的同学做个参考。先说个前提DHUOJ的题目顺序偶尔会随学期、课程调整你账号里看到的25、26、27可能和我当时的不完全一样但题型一般就是这三类。所以这篇真正想讲的是“这类题该怎么分析”而不是死记题号。1. 关于DHUOJ这三道基础题先对齐几个前提1.1 我刷到的题面是什么以我当时页面上的显示为准这三题分别是第25题输入两个整数 a 和 b1 ≤ a ≤ b ≤ 10000输出区间 [a, b] 内所有的素数素数之间用空格分隔如果一个素数都没有输出None。第26题输入一个整数 n输出它的倒序数保留负号忽略反转后产生的前导零。比如输入-1230输出-321。第27题输入一个字符串判断是否是回文忽略大小写并且忽略所有非字母、非数字的字符。如果是输出YES否则输出NO。这三个题面在各类OJ里都算“祖传题目”很多学校的基础题单里都有类似版本。就算你拿到的实现细节不太一样比如要求输出nuts而不是None或者不要求忽略标点核心思路也是通用的。1.2 三题背后其实是一条知识线把三题放在一起看价值就出来了。25题看起来是数学题本质却是在练“循环遍历 分支判断”26题看起来是数字游戏本质是在练“取余取整拆位”这是处理数字类问题最底层的手法27题看起来是字符串问题本质是在练“下标操作和双指针”后面你做数组反转、链表回文、滑动窗口全都要靠这个底子。我按三题的知识点、核心考点和易错点整理了一个表方便你对照题号题型核心考点最容易翻车的点25区间素数输出循环、素数判断、输出格式1不是素数最后一个数后面的空格2的特判顺序26整数倒序模10、整除10拆位、负数处理负数取模的怪现象前导零int溢出27回文串判断字符串读入、双指针、字符过滤下标越界fgets带入换行大小写转换刷基础题最忌讳的是一路“凭感觉”写错了就瞎改。先看懂自己到底在练哪个能力再动手效率高很多。2. 第25题区间素数输出循环与判断的第一次合体2.1 判断素数的边界条件和为什么只查到 sqrt(n)判断素数的标准定义是“一个大于1的自然数除了1和它本身之外不能被其他自然数整除”。所以有两个边界必须记死小于 2 的都不是素数尤其注意1 不是素数这是新手最容易被样例阴到的地方。2 是素数但 2 又正好是偶数所以在写判断时如果先判x % 2 0就 return 0会把 2 一起误杀。正确顺序应该是if (x 2) return 0; // 排除 0 和 1 if (x 2) return 1; // 2 单独放行 if (x % 2 0) return 0; // 其他偶数直接排除接着查奇数因子。判断一个数是不是素数传统写法是从 2 试到x - 1那在数据范围大的时候会超时。优化点是如果某个数x有一个大于sqrt(x)的因子那它必然同时存在一个小于sqrt(x)的对应因子。换句话说只要在 2 到sqrt(x)范围里找不到因子后面再往下找也找不到。所以循环上限可以砍到平方根级别。代码里我喜欢写i * i x而不是i sqrt(x)好处是不用每次循环都调一次数学库函数对小范围数据更快。不过要注意如果x特别大i * i本身可能溢出。这道题 a、b 只有 10000完全不用担心但养成“评估数据范围”的习惯是没有坏处的。还有一个可以白拿的优化因为单独把 2 处理了后续循环只需检查奇数步长设为 2。for (int i 3; i * i x; i 2) { if (x % i 0) return 0; }这样判断 10000 以内的素数每个数最多测大约 50 次非常快。2.2 完整代码与输出格式处理完整写法如下我直接排好版方便你直接复制去DHUOJ调试#include stdio.h int isPrime(int x) { if (x 2) return 0; if (x 2) return 1; if (x % 2 0) return 0; for (int i 3; i * i x; i 2) { if (x % i 0) return 0; } return 1; } int main() { int a, b; scanf(%d %d, a, b); int first 1; // 标记是否是第一个输出的素数 for (int i a; i b; i) { if (isPrime(i)) { if (!first) { printf( ); } printf(%d, i); first 0; } } if (first) { printf(None); } printf(\n); return 0; }这里有个新手普遍忽略的细节输出格式。OJ评测机比较的是字节级别的输出结果多一个空格、少一个换行哪怕答案的数值全对也会被判成 Presentation ErrorPE这在DHUOJ上非常常见。用first这个标志变量第一个输出的素数前面不加空格之后每个数前补一个空格就能保证末尾不会有多余空格。2.3 我在这题上见过的三种错法第一种把isPrime(1)返回了真。很多初版代码写成for (int i 2; i x; i)如果x是 1循环根本不进函数直接 return 1结果把 1 当成素数输出。“小于 2 直接 false”这一句必须写在最前面。第二种2 被偶数判断误杀。代码顺序写反先写x % 2 0再写x 2导致区间 [2, 2] 输出None。这种错在本地跑样例时极容易漏掉因为样例一般不会专门放一个 2 进去。第三种输出末尾带空格。有人图省事写成printf(%d , i);本地看毫无问题提交后却提示 PE。还有个隐藏坑如果区间不存在素数需要在最后输出None但有些人把None拼在空格后面输出成 None同样会被判格式错误。所以我把“输出None”也放在first变量的控制逻辑里从根上避开这种问题。3. 第26题整数倒序数位拆解里的符号陷阱3.1 模10除10的标准姿势与负数处理整数拆位是几乎所有数字类题目的基本功核心逻辑就两句话n % 10取出最低位n n / 10去掉最低位。循环往复就能把每一位都提出来。倒序输出的过程其实就是边取低位边拼接每取出一位就把之前的倒序结果乘10再加上这一位。比如rev rev * 10 digit输入 123第一轮 rev3第二轮 rev32第三轮 rev321。负数是真正的坑。C语言里负数取模的结果依赖编译器行为按C99标准-123 % 10的结果是-3不是 3。如果你不处理符号就会得到一堆负数拼接的怪结果。安全的做法是在拆位之前先把符号记下来把数转成正数再处理最后输出符号。int sign 1; if (n 0) { sign -1; n -n; }另外要注意的是int能表示的最小值是-2147483648对它取正2147483648已经超出int范围。所以在读取时我直接用long long反转结果也存成long long这样即使输入踩到边界也不会悄悄溢出。刷OJ时有个习惯越早养成越好不确定会不会溢出的地方就用更大范围的类型。3.2 代码实现与溢出意识下面是标准实现#include stdio.h int main() { long long n; scanf(%lld, n); if (n 0) { printf(0\n); return 0; } int sign 1; if (n 0) { sign -1; n -n; } long long rev 0; while (n 0) { rev rev * 10 n % 10; n / 10; } if (sign -1) { printf(-); } printf(%lld\n, rev); return 0; }有人可能会问既然 n 转成了正数为什么循环条件不写n ! 0其实写n 0也一样因为我们已经把负数纠正过了。特别地n 0的情况要单独处理否则循环根本不会执行最后输出一个空行。这种边界条件在OJ题目里是必测项。我再解释一下前导零的问题。用整数拆位法末尾的零天然会消失输入 1200第一次取出的 digit 是 0但rev 0 * 10 0仍然等于0第二次也是直到取出1和2才开始形成 21。所以正确处理出来的结果就是 21不需要额外做任何“跳零”操作。如果你改用字符串反转那就得自己处理反转后开头的零这是两条不同路线最明显的差异。3.3 边界用例自查表我在本地调试的时候每次都会把下面这一组用例跑一遍全部通过才敢提交。你也可以拿它当自查清单。输入期望输出验证的点00单独处理零不能输出空行55一位数反转本身101末尾零的消去10001多个末尾零的消去-123-321负号保留-1230-321负数加末尾零同时出现21474836477463847412int 上限范围内的翻转结果-2147483648-8463847412int 最小值验证溢出是否避开如果某一条输出不对先别急着改代码把sign、rev、n三个中间变量逐轮打印出来看问题一般立刻就清楚了。4. 第27题回文串判断从下标到双指针的跨越4.1 读入含空格字符串的坑fgets与去换行第三题到了字符串最大的变化是“读入”这件事本身就有坑。如果你用scanf(%s, s)读字符串在空格处就会断开那A man, a plan这种句子只能读进去A。这题要求忽略非字母数字说明原始字符串中间很可能有空格、逗号、冒号所以必须用fgets整行读入。fgets(s, sizeof(s), stdin)会把末尾的换行符也存进字符数组里。如果不处理换行符会参与判断结果大概率全错。所以读完要先把换行长度算出来int len 0; while (s[len] ! \n s[len] ! \0) { len; }注意判断顺序先判断s[len] ! \n再判断s[len] ! \0。如果字符串本身没有换行比如文件末尾少了一行直接访问到\0也就安全退出了。还有一个细节数组长度别抠门。题目说最长100你就开s[105]或者s[200]。C语言字符串末尾必须有一个\0加上可能残存的换行刚好开100个字节非常容易踩到数组越界。这一点刷多了之后你自然会形成肌肉记忆输入缓冲区永远多留余量。4.2 双指针比较与大小写、标点过滤回文判断最直观的思路是从两端向中间比这就是双指针的雏形。两个下标left、right分别从首尾出发遇到不合法的字符非字母、非数字就跳过然后统一成小写再比。过滤字符时不要自己写一堆if (c a c z)之类的判断直接用ctype.h里的isalnum和tolower语义清晰也少出错#include stdio.h #include ctype.h int main() { char s[200]; fgets(s, sizeof(s), stdin); int len 0; while (s[len] ! \n s[len] ! \0) len; int left 0, right len - 1; while (left right) { while (left right !isalnum(s[left])) left; while (left right !isalnum(s[right])) right--; if (tolower(s[left]) ! tolower(s[right])) { printf(NO\n); return 0; } left; right--; } printf(YES\n); return 0; }核心是内部那两个过滤循环它们前面必须带上left right条件。如果不带处理一个全标点字符串时left会一路冲到数组末尾或者造成越界访问。这是这题最容易触发 Runtime ErrorRE的地方。4.3 这道题最常见的Runtime Error来源我第一次写这题数组开的是char s[100]fgets(s, sizeof(s), stdin)看起来没问题但实际字符串带上换行和结束符刚好卡满容量边界之后访问s[right]就出格了。后面我把数组扩到200再也没出过事。第二个常见的RE原因是字符串一开始就是空的或者全是空格和标点。此时len - 1是负数right初始值就直接非法。好在外层条件是while (left right)如果right是负数条件不成立程序会输出YES。空字符串算不算回文不同题目有自己的定义但至少不能崩溃。你可以在开头加一句if (len 0) { printf(YES\n); return 0; }做显式处理更清晰。第三个问题是大小写。如果题目只要求忽略大小写不要求忽略标点那过滤循环可以简化成只跳过空格。无论哪种要求isalnum和tolower这套组合总是最保险的。5. OJ提交阶段容易翻车的细节从PE到RE5.1 输出格式为什么能困住新手三道题的代码到这一步都能跑了但提交到DHUOJ后真正让人头疼的往往不是算法而是评测机的严格脾气。我第一次刷这三题时状态栏里出现最多的不是 WA而是 PE。后来我总结了一下PE 基本就三种来源行尾多空格、行间多空行、输出内容里混了中文标点或多余提示语。第25题是典型的行尾空格问题。如果你用printf(%d , i)前几个样例可能恰好没触发但如果用例的最后一个素数之后还有内容OJ就会抓到那个空格。前面给的做法已经用first变量解决了。第二种是调试时留下的输出没删干净。有人说自己代码在本地跑得好好的一提交就 WA经排查发现printf(here\n)之类的东西混在结果里。所有中间输出在提交前必须清掉。第三种是多余换行。有些题要求每个输出占一行最后的换行有没有其实都算对但如果你在printf(None)之后又习惯性地多打一个\n且题目要求的是同一行拼接就可能多出空行。看题面要求跟题面保持一致是最稳的。5.2 数组越界与未初始化的排查套路RE 最典型的触发原因是数组越界。第27题我已经举过例子。正规排查套路是这样的把题目里所有“长度不超过多少”的字样圈出来数组至少多开10到20个字节所有访问数组下标的循环逐一确认下标范围是否在[0, len)之内C语言局部变量不自动初始化如果你定义int a[100]并在循环里使用a[i]理论上数组内容是未知的。本地不小心跑出正确结果不代表评测机上也行。凡是需要用数组记录数据的要么显式初始化要么保证在写入之前不读取。这类“这次能过下次不能过”的问题根源几乎都是未定义行为。在OJ上它不是玄学是边界条件没处理干净。5.3 DHUOJ评测环境下的本地调试建议每个OJ的编译器版本和运行时行为稍有差别。就我刷DHUOJ的经验按 GNU C 标准编代码只要不用编译器扩展基本不会遇到环境差异。给你几条能落地的建议本地尽量用-Wall编译参数开启全部警告。哪怕只是“可能有未初始化变量”的提示都能帮你躲过一个大坑。想调试时用printf打印中间变量但提交前把调试行注释掉或者直接删掉。千万不要在代码里写system(pause)评测机不会帮你按回车结果就是卡在等待输入上导致超时。造用例时不要只抄题目样例还要自己加边界数据。三道题里25题要用[1,1]、[2,2]、[1,10000]这组数据验证26题要用上表那组27题要覆盖“全标点”“大小写混合”“字符串中间带空格”这三种场景。如果整段代码跑不出对的结果把思路讲给旁边的同学听或者把代码拆到最小复现一次只改一个变量。这种“二分排除法”排查思路在OJ上是通用技能。最后一件事。当时我刷完这三题回看自己最初的提交记录发现同样的错误在25题犯完到27题又犯了一遍。比如不处理边界、不控制格式、不检查下标。基础题的价值不是让你把题数凑到三位数而是把这几类底层问题一次性暴露出来。后面你写链表、写哈希表、写图遍历的时候真正支撑你走得远的其实还是这三题里反复磨过的东西遍历的顺序、边界的条件、数据的类型。建议你刷的时候也别急着刷完就跑把每一题多写一个版本尤其是第26题用整数法和字符串法各做一遍第27题用过滤后新建数组和原地双指针各写一遍对比一下你就会理解我刚才说的这些细节分别卡在哪里。
阅读完成 · 觉得有帮助？
