1. 一道小鱼的数字游戏为什么能让新手原地卡壳这道题我第一次刷的时候心里想的是这也算必刷。题目短、场景萌读起来不过三行小鱼看到一串数字以 0 结尾它要把这些数字倒着念出来。乍看就是输入一串数倒序输出而已。但等我真正动手写代码才发现里面藏着的坑一个接一个输入什么时候停停下来的那个 0 算不算数据如果数字个数事先不知道数组到底开多大输出最后一个数字后面要不要带空格这些细节不亲手踩过根本不会意识到。我后来把这道题放进自己的数组入门必刷清单是因为它用最小的问题模型把数组相关的四个基本功全考了一遍第一怎么处理不确定长度的输入第二怎么把读到的数据按顺序存进数组第三怎么用下标访问数组尤其是下标从 0 开始这个事实第四怎么控制输出的格式既不丢数据也不多输出。很多读者觉得算法题难在思路但《小鱼的数字游戏》恰恰是思路一句话实现十处坑的典型。它考验的不是你会不会背题解而是你对数组这种最基础数据结构是否真的养成了肌肉记忆。更关键的是这道题在众多算法题单里被放在必刷位置不是因为得用多么高深的技巧而是因为它能帮你打通输入-存储-遍历-输出这条最核心的链路。后面你刷二维数组、指针数组、动态数组、字符串数组本质上都是在这条链路上变花样。比如你看到树状数组的模板题会觉得复杂但追根到底仍然是把数据放进某种结构再按某种规则取出来。《小鱼的数字游戏》就是这个最初的原点。所以别看它简单我建议你把它当成一个标准件来刷至少用三种语言各写一遍再用递归和栈各写一遍。当你发现所有写法都能在五分钟内一次通过时你对数组的掌控感会完全不一样。以下我会从最朴素的固定数组解法一路讲到递归和栈把每步背后的理由和常见的翻车现场都摊开说。2. 先啃最朴素的解法固定长度数组加倒序输出2.1 完整代码与逐行拆解如果是在 C 语言环境下做这题大多数题解的第一版会长这样#include stdio.h int main() { int a[1000]; // 假设最多 1000 个数够用了 int n 0; // n 记录实际读了多少个数 int x; while (scanf(%d, x) 1 x ! 0) { a[n] x; n; } for (int i n - 1; i 0; i--) { printf(%d , a[i]); } return 0; }这段代码耐着性子拆开看其实每个字符都在跟数组打交道。先看int a[1000]。这是声明一块连续的内存空间下标从 0 到 999。题目没说最多输入多少个数只说以 0 结束所以现实中我们必须给数组定一个尺寸。这里的 1000 是我随手写的很多初学者看到这种拍脑袋的数字就害怕觉得不严谨。但很多 OJ 题目确实不会直接告诉你输入上限你只能根据题目描述和数据范围来估算。比如题目说小鱼看见一串数字没有给具体长度那 1000 通常够用——但够用不等于安全后面我会专门讲怎么避免在这个地方翻车。int n 0是计数器。每存一个数n 加一。它同时暗示了下一个空闲位置在哪第一次读到的数存在a[0]第二次存a[1]第 n 次存a[n-1]。最终 n 就是有效数字的个数也是倒序遍历的起点。进入循环后scanf(%d, x) 1表示成功读到一个整数 x ! 0表示读到 0 就停止。注意这个写法把读取成功和不是 0两个条件写在了一起顺序不能交换。如果先判断x ! 0但你还没读到 x或者读到文件末尾时x的内容是未定义的逻辑就会出问题。scanf返回 1 说明确实有输入这样后面的判断才有意义。循环体a[n] x; n;是标准的存数-后移操作。很多新手喜欢写成a[n] x;虽然能少写一行但初次接触时反而容易混淆。我建议一开始就老老实实分开写等彻底理解下标变化后再压缩。最后是循环输出for (int i n - 1; i 0; i--) { printf(%d , a[i]); }如果读入了 5 个数它们分别存在a[0]到a[4]那么倒序输出的起点就是n - 1 4终点是i 0。这里有三个容易写错的地方写成i n会访问a[5]越界了Windows 下程序可能直接崩Linux 下可能碰巧输出一个垃圾值写成i 0会漏掉a[0]也就是第一个读入的数写成i--还是i--后置自减倒序没问题但如果用死循环配合 break 就不太直观。所以这短短一行循环其实是在检验你对数组下标边界的敏感度。2.2 为什么数组下标要从 0 开始每次讲数组总有人问为什么不从 1 开始多好理解啊从 1 开始第一个元素是a[1]第 n 个元素是a[n]循环也好写。但实际上数组下标从 0 开始是 C 语言的设计基石因为这直接和内存地址挂钩。数组是连续内存的抽象。a[i]的本质是从首地址偏移 i 个元素大小的内存。如果首地址是 base每个元素占 size 个字节那么a[i]的地址就是base i * size。下标从 0 开始意味着第一个元素偏移量为 0正好落在首地址上不需要多余的计算如果下标从 1 开始访问a[1]就要做一次base (1-1)*size的换算虽然现代编译器能优化掉但语言设计之初追求简洁高效所以干脆让数组下标从 0 开始让第 i 个位置就是偏移 i 个位置。这一点在倒序时尤其明显。a[n-1]是最后一个元素a[0]是第一个元素。如果下标从 1 开始倒序就得从a[n]到a[1]别扭感一样存在。既然 C 的数组天生从 0 开头我们不如彻底接受它并把它刻进骨子里凡是用下标遍历都要时刻问自己起点和终点到底是谁。2.3 数组初始化的坑memset 和局部变量的默认值固定数组解法还有一个隐藏考点要不要初始化a代码里我用int a[1000];直接声明然后只写了n个位置后面倒序也只访问这n个位置。只要保证所有访问都发生在0到n-1之间数组里其他位置是什么值根本无关紧要。但很多初学者会被初始化数组这个概念绊住。有人习惯写int a[1000] {0};把整个数组清零觉得这样更干净。对于本题这完全没必要反而可能养成坏习惯——因为你没有访问未赋值的区域清零是在浪费计算资源。更大的坑在于如果使用局部变量却不初始化编译器有时候会给出警告或随机值。比如你可能这么写int a[1000]; int n; int x; while (...) { a[n] x; n; }这里n没有初始化它的初始值取决于栈上残留数据可能是个随机值。于是a[n]可能写到数组之外程序莫名其妙崩溃。我见过太多同学排查半天查不到原因最后发现只是忘记给n赋零。所以固定数组解法的第一原则不是清空数组而是让计数器从 0 开始。另外如果确实想把一个数组初始化成全 0可以用memset(a, 0, sizeof(a))但要注意memset是按字节填充的对int数组来说填 0 恰好有效填 其他数字比如 1却不会得到 1。如果哪天你想把数组全初始化为 -1就别用memset了老老实实用循环。这些细节都属于数组操作的基础功在必刷题里多锻炼后面自然就顺手。3. 多语言横向对比用 Java、Python、C 怎么写更舒服一道算法题用多种语言各写一遍价值在于帮你剥离语言特性和算法本质。数组的存储与倒序思想是不变的但每种语言提供的容器不同写出来的代码风格也不同。3.1 Java用 ArrayList 解决长度未知问题Java 的普通数组和 C 差不多int[] a new int[1000];也需要手动维护n计数器。但更舒服的做法是直接用ArrayListInteger它的长度可以动态增长完全不需要预设上限import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); ArrayListInteger list new ArrayList(); while (sc.hasNextInt()) { int x sc.nextInt(); if (x 0) { break; } list.add(x); } for (int i list.size() - 1; i 0; i--) { System.out.print(list.get(i) ); } sc.close(); } }ArrayList底层仍然是数组但它帮你管理了扩容逻辑。当你add到第 11 个元素时底层数组会翻倍拷贝然后把新元素放进去。这个细节在学习阶段很有价值你知道它方便但也应该知道它背后的复制成本。如果题目的数据量达到十万、百万频繁扩容是有开销的Java 的话你可以预估容量后直接new ArrayList(100000)给初始容量减少扩容次数。倒序输出时使用list.size() - 1当作起点和 C 语言的n - 1一个道理。唯一的差异是Java 的for循环写System.out.print(list.get(i) )末位会多一个空格。很多 OJ 对行末多余空格是宽容的但也有严格判题系统会判 Presentation Error。如果你的强迫症犯了可以用一个flag来控制第一个输出前不打印空格但那是另一个话题。3.2 Pythonlist 加切片或 reversed 一步到位Python 写这道题代码量能少到惊人nums [] while True: x int(input()) if x 0: break nums.append(x) print(*nums[::-1])nums.append和 Java 的add类似是动态数组list在尾部追加元素。nums[::-1]是切片倒序返回一个新列表*是把列表元素展开成多个参数传给print默认用空格分隔正好满足题目要求的输出格式。但这份优雅背后你一定要理解它到底做了什么。nums[::-1]会创建一个长度等于原列表的新列表然后逐个复制元素。对于这道题数据量不大无所谓。如果你在数据量巨大的场景下追求内存效率可以改用reversed(nums)它返回一个迭代器不会额外复制整个列表print(*reversed(nums))reversed是惰性求值从尾部向前遍历。不过把迭代器展开到print里时还是会一次性处理所有元素但至少没有中间副本。对初学者来说我更推荐先写显式的循环for i in range(len(nums) - 1, -1, -1): print(nums[i], end )这行代码更接近 C 语言的眼界也更容易和数组下标概念对上号。Python 的切片是很香但如果你依赖它而忘记了底层下标逻辑等你去做 C/C 的题目时会很不适应。我自己的习惯是竞赛时怎么快怎么来写题解时一定要写出那个显式循环把基础夯实。3.3 Cvector 与反向迭代器C 的vector既保留了数组的连续内存又具备动态扩容能力#include bits/stdc.h using namespace std; int main() { vectorint v; int x; while (cin x x ! 0) { v.push_back(x); } for (auto it v.rbegin(); it ! v.rend(); it) { cout *it ; } return 0; }cin x x ! 0的逻辑和 scanf 版本一致成功读入且不是 0。rbegin()指向最后一个元素rend()指向第一个元素之前的位置反向遍历时用it实际上是向开头移动。这其实就是倒序的迭代器语法糖。你也可以不用迭代器直接用下标for (int i (int)v.size() - 1; i 0; --i) { cout v[i] ; }要小心v.size()的返回类型是size_t无符号整数如果写成for (int i v.size() - 1; i 0; --i)当v.size()为 0 时v.size() - 1会变成一个巨大的无符号数然后被转换成int通常是 -1 或溢出导致循环不执行或死循环。稳妥做法是加一个(int)强制转换或者用v.empty()特判。这也是数组题里经典的无符号整型大坑我能想到是因为我踩过。3.4 不同语言在逆序上的思路其实一样对比下来你会发现无论 C、Java、Python、C核心都是四步初始化一个能存储数据的容器、读入、判断终止条件、倒序访问。语言容器换了几种但下标从后向前走的思想从未变过。这也解释了为什么数组题总是被拿来当第一关。你通过这道题掌握的不是某一种 API而是一种抽象能力把一组有序数据放进一段连续空间然后按任意顺序访问它。这种能力不绑定语言在各种业务场景里都会用到比如 VBA 里处理一列数、JavaScript 里操作 JSON 数组、MATLAB 里取出矩阵的多列本质上都是选一种容器按索引访问。所以如果你能把《小鱼的数字游戏》用两三种语言刷熟后面的路会顺很多。4. 不建数组也能逆序递归与栈的底层逻辑上面所有解法都建了数组或类似数组的容器。但《小鱼的数字游戏》还有两种更反直觉的解法它们不显式使用数组也能达到同样的效果。理解这两种解法能加深你对程序调用栈和数据结构栈的理解。4.1 递归解法函数调用栈替你存数据递归版 C 代码极其简洁#include stdio.h void solve() { int x; if (scanf(%d, x) ! 1) { return; } if (x 0) { return; } solve(); // 先递归读后面的数 printf(%d , x); // 回溯时输出当前数 } int main() { solve(); return 0; }这个函数做的事情是读一个数 x如果它既不是输入结束也不是 0就先不输出而是去递归调用solve()读下一个数等递归调用全部返回后再输出 x。为什么这样就能倒序因为函数调用本身是后进先出的。第一次调用solve()读到的 1会等待第二次调用返回后才输出第二次调用读到的 2会等待第三次调用返回后才输出……最后一次读到 0 时直接返回不输出。于是最内层的调用先返回先输出最后读到的那个非零数然后一层一层回溯输出之前的数。最终输出的顺序就是输入顺序的逆序。递归解法妙就妙在它把数组藏进了系统调用栈。每个函数的局部变量 x 都存在栈帧里调用栈天然支持后进先出所以不需要显式数组。代价是什么呢如果输入的数字非常多递归层数会很多系统栈可能不够用导致栈溢出。对于这道题 1000 个数问题不大但如果是十万个数递归就可能爆栈。这也让你直观理解为什么有些算法题会限制递归深度为什么很多生产环境里递归转循环是一个基本优化手段。4.2 手动模拟栈用数组实现 LIFO 行为用数组模拟栈代码会这样#include stdio.h int main() { int stack[1000]; int top 0; int x; while (scanf(%d, x) 1 x ! 0) { stack[top] x; } while (top 0) { printf(%d , stack[--top]); } return 0; }这里的stack本质上还是一个数组但用法完全向栈靠拢top指向栈顶的下一个空位push就是stack[top] xpop就是--top后取出stack[top]。第二个while循环每次--top输出的顺序天然是倒序。你会发现显式栈和递归是同一枚硬币的两面。递归靠系统维护的调用栈显式栈靠我们自己维护的数组。当你写stack[top]时就是在模仿递归中的返回地址和局部变量。很多算法题比如树的遍历、括号匹配、表达式求值都可以用这两种方式互相转换。把《小鱼的数字游戏》当作栈的入门实验你会更容易理解调用栈不是一个抽象概念而是实实在在的内存行为。4.3 三种解法的时空复杂度对比我做题时喜欢列一张小表帮助自己判断用什么解法最合适解法额外空间时间复杂度风险点固定数组O(N)N 是实际数字个数但需预设上限O(N)数组上限不够、计数器未初始化动态容器Java ArrayList / C vector / Python listO(N)可能略大于 N容量冗余O(N)扩容带来的摊销成本递归O(N)调用栈空间O(N)N 过大时栈溢出显式栈数组模拟O(N)O(N)和数组一样有上限注意递归解法的空间复杂度是 O(N)这往往被新手忽略。他们以为递归不用数组就省内存其实系统栈占的空间不比数组小甚至往往更大。所以递归更适合让你理解运行时栈的概念不适合用来压缩空间。这四种解法我都建议亲手敲一遍。敲完之后你会明白算法题的最优解不一定是最花哨的而是要和题目数据范围、语言特性、运行环境匹配。像《小鱼的数字游戏》这种小数据题用哪种都行但你必须清楚每种解法底层的空间开销因为日后刷到大数据量的数组题这些资源意识会救你一命。5. 我做这道题踩过的坑和总结出的刷题姿势题目简单不代表没有坑。我把这几年教新手时最常见的错误整理了一份你如果还没踩过很可能会在某个深夜被它们折磨。5.1 坑一把结束标志 0 也当成有效数字输出最常见的翻车写法是while (scanf(%d, x) 1) { a[n] x; } // 然后直接把 a[0] 到 a[n-1] 倒序输出这样会把结束标志 0 存进数组输出时也会输出 0。题目要求小鱼看到一串数字0 表示结束0 本身不是游戏内容所以必须排除。你需要在循环体里判断或者直接在循环条件里把x ! 0写上。这个错误往往不会被编译器察觉运行结果也看起来正常只是多了一个 0 在答案末尾导致判题 WA。5.2 坑二数组开太小直接越界我见过有人写int a[5];然后读入 100 个数字。程序可能当时没崩因为越界写到了相邻内存覆盖了其他变量或者幸运地写进了未使用的内存。但这种没崩是最危险的因为提交到 OJ 后可能因为内存校验而 Runtime Error而且复现起来很蛋疼。更隐蔽的是有些同学知道要开大数组但不知道大的上限于是写了int a[1000000];放在 main 函数里。这在某些 OJ 上会导致栈内存不够而崩溃因为局部大数组占的是栈空间栈通常只有几 MB。解决方案有两个一是把数组声明为全局变量静态存储区二是用动态内存分配malloc或new。如果你在用固定数组刷题建议一开始就把数组放在全局区域避开栈大小限制。5.3 坑三把scanf返回值当成可选项while (scanf(%d, x) 1 x ! 0)里的 1不是装饰。有些 OJ 的输入是纯数字有些可能会夹杂换行、文件结束符。如果你只写while (scanf(%d, x))当输入结束时scanf返回EOF其值是 -1在逻辑判断里是真循环不会终止程序会不断读取失败陷入死循环。所以任何涉及不确定输入长度的题目都要习惯性地检查scanf的返回值。这是 C 语言的握手协议确实啰嗦但很安全。5.4 刷题姿势先写伪代码再翻译成语言我给自己定了一条规矩除非是送分题否则绝不在拿到题后立刻写代码。至少先花一分钟把思路用自然语言描述出来。这道题的伪代码可以写成初始化一个存储整数的结构比如数组 计数器 n 0 循环读入整数 x 如果读入失败退出循环 如果 x 等于 0退出循环 把 x 存入结构n 加 1 从 n-1 到 0 逐个输出结构中的数写完伪代码你就可以往任意语言里填语法。C 的int a[1000]Java 的ArrayListPython 的listC 的vector都是存储整数的结构。你会发现语言差异只存在于容器声明和API 调用逻辑骨架是完全共通的。最后分享一个实际经验我刷这题时喜欢把输出最后一个数字后不输出多余空格也一起实现。做法是用一个布尔变量控制for (int i n - 1; i 0; i--) { if (i n - 1) printf( ); printf(%d, a[i]); }这样输出格式是5 4 3 2 1而不是5 4 3 2 1。虽然题目多半不会判错但严格模式下这种干净输出会给你省去很多不必要的 WA。把每一道简单题的输出都做到位到了复杂题格式严谨就成了一种本能你就不用再操心这些旁枝末节了。