刷透数组基本操作：从P1427小鱼的数字游戏到双指针与边界陷阱

刷题这件事我一直有个观点简单题不是用来“刷过”的而是用来“刷透”的。小鱼的数字游戏就是这样一道题。它在洛谷的编号是P1427标签写着“入门”题面也很短——小鱼报出一串正整数最后一个数字是0表示结束要求你把这串数字倒着说出来。数据范围很小最多100个数每个数也没超出int的承受能力。但如果你以为这道题只是让你练手“倒着输出”那可能就低估它了。它真正想考察的是你在数组这种最基础的数据结构上对存入、计数、索引、边界这四件事有没有形成条件反射。这篇文章我会从题面拆解讲起把C、C、Python、Java四种写法各写一遍重点说清楚每种写法里容易踩的坑再延伸出三个变式方向最后整理一份数组题排错清单。无论你是刚学编程的大学生还是准备面试想快速恢复手感的人这篇都能让你在半小时内把“数组基本操作”这块基础彻底夯实。1. 题面拆解这道“必刷”数组题到底在考什么1.1 一句话讲清题目题目描述很直白输入若干个正整数以0结尾要求按输入顺序的逆序输出这些数0本身不输出。比如输入1 2 3 4 0输出就是4 3 2 1是不是感觉太简单了先别急着下结论。这道题在洛谷上被标记为“入门”但它的通过率并没有想象中那么高大批新手会在小细节上翻车。我见过有人把0也输出出来见过有人数组开小了直接越界也见过有人用递归写这个题结果在大数据下爆栈。所以这道题真正的价值不是“会不会做”而是“能不能一次写对”。1.2 四个隐藏考点这道题看似只有一个“倒序输出”的动作但落到代码层面其实拆成了四个必须理解到位的环节第一数组的声明与大小选择。题目没给输入上限怎么办开多大的数组才安全这是数组题的第一道门槛。很多初学者习惯“估一个数”比如开a[100]结果数据给了101个就崩了。正确的做法是先看题目的数据范围约定如果没有明确约定那就开一个足够大的数组比如a[1005]或a[10005]宁可多开不要少开。第二动态存入与计数。循环读入数字每读到一个非0的数就存进数组同时记录个数。这里有个关键点计数变量是在存入之前自增还是存入之后自增这个顺序决定了后面倒序输出的起点错一位就是“差之毫厘谬以千里”。第三索引与边界。数组的下标从0开始存入n个数后最后一个元素的下标是n-1。倒序输出的循环应该从n-1出发一直走到0。新手最容易在这里写出从n出发的循环结果把越界或者把终止符0输出出来。第四循环终止条件的写法。读入以0结束那你怎么写这个while循环是先读再判断还是先判断再读这决定了0会不会被误存入数组。这四个考点单独拎出来每一个都不难但放在一道题里组合起来就能筛掉一批“以为自己会了”的人。这就是数组题的典型风格不考偏题怪题就考你对基础概念的肌肉记忆。1.3 为什么说它“必刷”我在带新人刷题的时候反复强调过数组是所有数据结构的地基。链表是数组加指针的变形栈和队列可以用数组模拟树和图的存储也离不开数组。你后面要学的归并排序、树状数组、动态规划的状态转移表哪一个不是建立在数组上的所以数组题不是刷一遍就完的而是要刷到“闭着眼睛都能写对”的程度。小鱼的数字游戏就是这么一个完美的入门载体——题面简单考点明确没有花哨的包装一道题就能把你对数组的基本功摸个底。如果你已经是刷了几百题的“老手”也可以用这道题做自测不假思索地写出一个无bug的解法并且能立刻说出三种不同的实现方式再说出至少两个容易踩的坑。能做到说明你的数组基本功是扎实的做不到那正好借这篇文章把这块补上。2. 多语言实现与细节剖析2.1 C语言版用最原始的方式理解数组C语言是最适合理解数组本质的语言。数组名本质上是首元素的地址a[i]在底层会被翻译成*(ai)所以下标天然从0开始——因为它表示的是“偏移量”。先看代码#include stdio.h int a[105]; int main() { int x, cnt 0; while (scanf(%d, x) 1 x ! 0) { a[cnt] x; } for (int i cnt - 1; i 0; i--) { printf(%d , a[i]); } printf(\n); return 0; }这里有几个细节值得啰嗦一下。第一数组为什么开105因为题目说了最多100个数开105就有余量。万一题目没说上限你就得开大一个量级比如10005。另外一个容易忽略的点是数组开在函数外面还是里面。这段代码把a[105]开成了全局变量好处是数组会放在静态存储区而不是栈上对于大数组来说更安全不会因为栈溢出而崩溃。如果是比赛环境全局开数组是常规操作。第二while循环的条件写得讲究。scanf(%d, x)的返回值是成功读取的变量个数正常情况下是1。如果读到文件末尾或者读入失败返回的是EOF也就是-1。写成while(scanf(%d, x) 1 x ! 0)既能保证每次确实读到了一个整数又能正常处理输入结束的情况。有些新手喜欢写while(scanf(%d, x) ! 0)这个写法在读到EOF时条件也为真会导致死循环非常危险。第三a[cnt] x这行是这道题的精髓。它等价于a[cnt] x; cnt cnt 1;先存再自增。当循环结束时cnt正好等于存入了多少个数字。比如输入1 2 3 4 0循环结束后cnt等于4数组里存的是a[0]1、a[1]2、a[2]3、a[3]4。最后一个数0根本没有进入数组因为它在判断条件x ! 0这一步就被拦下了。第四倒序输出的循环从cnt-1开始。刚才说了cnt是4最后一个元素的下标是3也就是a[3]所以从cnt-1出发完全正确。很多新手会写成for(int i cnt; i 1; i--)输出就变成“0 4 3 2 1”把终止符0也带出来了。这就是典型的边界条件没想清楚。2.2 Python版简洁背后的两个坑Python的写法看起来更轻松但同样有细节坑。先看标准解法nums [] while True: try: x int(input()) except: break if x 0: break nums.append(x) print( .join(map(str, nums[::-1])))这里要重点说两个容易翻车的地方。第一个坑是输入行的处理。很多新手写成这样nums list(map(int, input().split()))然后就直接用。这个写法默认所有数字在同一行但如果题目给的输入是分行的比如1 2 3 0那input()只会读到第一行的“1”后面的2、3、0全被漏掉。所以正确做法是写一个while True循环逐行读取直到遇到0再跳出。这里我用try/except包了一层是为了兼容输入结束的情况如果在线评测系统会在读完数据后发送EOF没有这个保护int(input())会抛异常。第二个坑是倒序输出的写法。nums[::-1]是Python切片最经典的用法之一表示从后往前取整个列表。这个写法在热搜词“python数组切片”里也是高频出现的。它本质上生成了一个新列表不影响nums本身。如果你希望不产生新列表可以用reversed(nums)它返回一个迭代器配合join使用也完全没问题。这里还有个常见的错误做法有人会在循环里用range(len(nums) - 1, -1, -1)手动倒序虽然没错但Python天然提供了更优雅的方式没必要绕远路。再说print那一行。 .join(map(str, nums[::-1]))的作用是把列表里的每个数字转成字符串然后用空格拼接。为什么要转字符串因为join方法只接受字符串列表直接传数字会报TypeError。这种类型转换在刷题里很常见也是新手经常卡住的地方。2.3 C与Java版容器与裸数组怎么选C选手通常会选择vector。代码长这样#include iostream #include vector using namespace std; int main() { vectorint v; int x; while (cin x x ! 0) { v.push_back(x); } for (int i (int)v.size() - 1; i 0; i--) { cout v[i] ; } cout endl; return 0; }vector的好处是动态扩容不需要预先指定大小适合“不知道输入有多少个”的场景。但这里藏了一个C特有的坑v.size()返回的是size_t类型这是一个无符号整数。如果不做强制转换直接写for(int i v.size() - 1; i 0; i--)当v.size()为0时v.size() - 1会变成一个极大的正数无符号溢出循环就会莫名其妙地跑很久甚至越界。本题虽然保证了至少有一个数但你得养成写(int)v.size() - 1的习惯。Java选手则有两条路用ArrayList或者用原生数组。我推荐ArrayList因为同样可以动态增长import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); ArrayListInteger list new ArrayList(); while (true) { int x sc.nextInt(); if (x 0) break; list.add(x); } for (int i list.size() - 1; i 0; i--) { if (i ! list.size() - 1) System.out.print( ); System.out.print(list.get(i)); } } }Java这段代码里有个关于输出格式的处理我用if判断来避免尾部多余空格。在严格判题的OJ上输出末尾多一个空格通常被判为Presentation Error虽然和Accepted只差一线但形式上不如直接避免。原生数组版本则需要先读一遍统计数量或者开一个足够大的数组。前者麻烦后者浪费。在刷题场景下ArrayList是更合理的选择。不过面试场景另说——如果你能现场用原生数组给出一个不浪费空间的解法那会让面试官更认可你对数据结构的理解。2.4 核心差异对比四种语言的实现各有侧重我把它们的核心差异整理成一张表语言存储方式动态扩容倒序输出方式典型坑点C固定数组不支持for循环倒序数组开小、边界错位Cvector自动for循环倒序无符号整数减法Pythonlist自动切片[::-1]或reversed读多行时漏数据JavaArrayList自动for循环倒序输出末尾空格看到没有虽然写起来难度不同但核心逻辑完全一致先存后逆序取。语言只是工具数据结构的思想才是共通的。我建议你至少把C语言版和Python版各写一遍一个让你理解底层一个让你感受工程效率两者互相印证数组这块的地基就稳了。3. 一题三吃从“倒序输出”延伸出的三个进阶方向3.1 变式一不知道有多少个数字时栈就登场了这道题的输入是以0结尾的所以你能计算出最终长度。但如果换一个场景数据来自一个实时数据流你不知道它什么时候结束甚至需要边读边处理该怎么办这时候你会发现“倒序输出”本质上是一个“后进先出”的问题。你最后读到的数要最先输出这就是栈的特性。用数组加一个栈顶指针模拟栈的操作int stack[105]; int top 0; while (scanf(%d, x) 1 x ! 0) { stack[top] x; } while (top 0) { printf(%d , stack[--top]); }这段代码里的top就扮演了栈顶指针的角色。入栈是stack[top] x出栈是stack[--top]。你不需要一个真正意义上的栈结构数组加指针就足够了。这正好呼应了热词里的“动态数组”和“栈”思想——静态数组按需求动态管理自己的“长度”本质就是手动管理一个可变容器。如果再往后走你会发现这种“后进先出”的思路在计算机里到处都是函数调用的递归栈、浏览器后退、撤销操作全是这个模型。一道小鱼的数字游戏其实是栈的启蒙题。3.2 变式二要求原地逆序双指针就是标准答案回到小鱼的数字游戏如果题目改成给你一个数组要求原地将元素顺序反转也就是把[1, 2, 3, 4]变成[4, 3, 2, 1]你会怎么做最直接的想法是再开一个数组倒着拷贝过去。但这样做空间复杂度是O(n)在一些内存受限的场合并不理想。面试官更想听到的解法是双指针int left 0, right cnt - 1; while (left right) { int tmp a[left]; a[left] a[right]; a[right] tmp; left; right--; }左边一个指针往右走右边一个指针往左走两个指针相遇时停止。每交换一对元素数组的两端就被“翻折”一次整个过程只需要O(1)的额外空间。这其实就是热词里“暴力枚举算法”的一个反面典型暴力法可以解决问题但双指针能把你从O(n)空间解放到O(1)空间。区别不是“能不能做”而是“做得好不好”。以后你会遇到大量双指针问题比如判断回文、合并两个有序数组、三数之和核心都是这个“一左一右往中间逼近”的模型。小鱼的数字游戏作为引子正好可以让你先体验一下双指针的节奏。3.3 变式三输入格式变化时读入策略要跟着变有些题目不会老老实实地在单个数字之间加空格它可能给你一整行字符串比如“1,2,3,4,0”逗号分隔。那你的读入策略就要从“读整数”变成“读字符串再拆分”。Python处理这个非常顺手nums list(map(int, input().split(,)))如果分隔符是空白字符空格、制表符、换行split()不传参数时会自动按任意空白字符切分这比C语言里费劲地处理空白要省心多了。但这也带来一个新的坑如果你用了split(,)但输入里实际是空格你会得到一个包含整个字符串的列表再转int就会报错。这个问题在热词“数组分割并显示包含某一字符”里被反复问到——所以读入之前先确认分隔符永远不是多余的步骤。另一个常见的输入形态是第一行告诉你有多少个数字第二行才是具体数据。这种题目就不能再用“0结尾”的循环了而应该先读长度n再读n个数。这个模式的通用解法是n int(input()) nums list(map(int, input().split()))这也启示我们刷题时读入部分的人力成本往往占了一半而读入方式的差异归根结底取决于题目给的输入格式。养成先读题、再设计读入策略的习惯能帮你避免一大半的格式错误。4. 实战避坑数组题最常见的错误与排查方法4.1 坑一数组开小了越界访问防不胜防我在群里见过一个经典案例有位同学写了int a[10];然后输入了20个数字程序跑起来直接乱码甚至出现段错误。原因很简单——C和C的数组访问是不做边界检查的。你写a[15]程序不会告诉你“越界了”只会默默地读写那块不属于你的内存结果可能是数据被篡改可能是栈被破坏也可能直接崩溃。怎么避免三个习惯先看题目数据范围再开数组开完再放大一点余量。全局数组比局部数组更安全因为局部数组在栈上容量有限开大了容易栈溢出。一旦出现“本地运行正常、提交后崩溃”的情况优先怀疑数组越界。Java和Python都有边界检查越界时会抛出异常至少不会像C那样产生未定义行为。但这也意味着同样的逻辑错误你用Python可能瞬间看到IndexError用C却要查半天。4.2 坑二终止符0到底要不要处理回到小鱼的数字游戏。输入以0结束那这个0本身算不算数组的一部分题目要求很明确0是终止标志不参与输出。但代码写出来不同人就会出现不同结果// 错误做法一把0也存进去了 while (scanf(%d, x) 1) { a[cnt] x; if (x 0) break; }这段代码的特点是先存再判断于是0也被写入数组。倒序输出时0跑到了最前面答案错误。// 正确做法先判断再存 while (scanf(%d, x) 1 x ! 0) { a[cnt] x; }这个区别说明了一个重要的编程习惯在做“判断后是否要处理”的操作时先想清楚这个值该不该进入你的核心数据结构。这道题的0就是不该进去的那个。4.3 坑三输出格式和多余空格OJ的判题机制对输出格式有严格要求。小鱼的数字游戏要求每个数字后面跟一个空格吗我看过不同版本的题面有的要求输出数字间用空格分隔末尾不允许有多余空格。用printf(%d , a[i])这种写法最省事但会在末尾多一个空格。许多OJ会因为这个空格判Presentation Error虽然结果看起来一样但提交不通过就是不舒服。推荐的做法是用一个标志位或者像Java版代码里那样在输出前判断for (int i cnt - 1; i 0; i--) { if (i ! cnt - 1) printf( ); printf(%d, a[i]); } printf(\n);第一项前不输出空格从第二项开始每一项前补一个空格。这样生成的字符串就是一个完美格式的“数字 数字 数字”没有任何多余字符。这个“首项无空格”的技巧在几乎所有需要输出多个值的题目里都适用建议直接背下来。4.4 坑四读入性能在数据量大时会要命小鱼的数字游戏数据范围很小读入性能问题不明显。但如果数据量放大到十万、百万级别用cin或者Scanner就会明显变慢。C选手可以加一行ios::sync_with_stdio(false); cin.tie(0);这行代码取消了C标准流与C标准库的同步能显著提升cin的读入速度。Java选手则建议用BufferedReader代替Scanner。Python选手如果遇到大数据尽量避免在循环里反复调input()而是用sys.stdin.read()一次性读入再split。这类优化在刷题初期用不上但面试或竞赛时会遇到。提前知道就不至于在关键时刻因为个读入问题卡到超时。4.5 一次真实的“错一位”排错实录最后分享一次实际带学生的排错经历。有个同学提交了这么一段代码int i 0; while (cin a[i] a[i] ! 0) { i; } for (int j i; j 0; j--) { cout a[j] ; }看起来逻辑通顺存数、计数、倒序输出一气呵成。但对样例输入“1 2 3 0”输出结果是“0 3 2 1”第一项多了一个0尾项少了1。为什么因为while循环结束时a[i]已经被读入为0i的值是3表示已经存入了3个非零数。所以最后一个有效元素的下标是i-12也就是a[2]3。但这位同学写的是for(int j i; j 0; j--)j从3开始先输出了a[3]0然后输出a[2]3结果最后输出a[0]1。这就是典型的“边界错一位”问题。我把这个案例发到群里后有个同学说“这不就是数组题的经典陷阱嘛差一个下标答案全错。”确实如此。数组题里这类“差一”错误太常见了原因就是对“存入个数”和“最后一个下标”之间的关系不够敏感。存了n个数最后一个下标是n-1——这个公式请你刻在脑子里。我个人的习惯是写完循环后用最简单的用例在脑内跑一遍。比如输入“5 0”存入了1个数cnt1应该从a[0]开始输出5。如果代码写的是从cnt开始立刻就能发现错位。这种“小数据脑内模拟”比调试器还快是刷题阶段必须掌握的基本功。数组题的坑说来说去无非是边界、下标、终止条件这几个关键词。如果你以后刷的题多了回头看会发现不管题目包装得多么花哨底层对数组操作的要求早在小鱼的数字游戏里就已经全部出现过。能把这道题里的每一处细节都讲清楚、写正确你的数组基本功就已经超越绝大多数初学者了。