你第一次看到 LeetCode 1006 的标题Clumsy Factorial大概率会以为又是一道阶乘变体无非是把连乘改成别的运算顺序。我当时也是这么想的直到动手用 C 语言实现才发现这题考的根本不是阶乘而是一个“运算符按固定顺序循环、处处藏着整除陷阱”的混合四则运算求值问题。它非常适合检验两个基本功你是否真的理解运算符优先级以及你能否从模拟里提炼出数学规律。这篇文章我打算按自己的做题顺序来写先把题目彻底拆开讲清楚三个容易翻车的误区然后给出用栈模拟的完整 C 语言实现解释为什么模拟也要用栈接着推导 O(1) 的数学公式把n % 4四条结论讲明白最后补上 C 语言实现里的整除截断、溢出和边界测试这些细节。无论你是刚开始刷 LeetCode 的新手还是准备面试时想快速回忆套路的同学都能拿到能直接落地的代码和思路。1. 笨阶乘到底是什么题目拆解与最容易踩的认知误区1.1 题目到底在算什么正常阶乘是n * (n-1) * ... * 1而笨阶乘规定了一种固定的运算符循环*、/、、-四种符号不断循环即clumsy(n) n * (n-1) / (n-2) (n-3) - (n-4) * (n-5) / (n-6) (n-7) - ...你不是把所有数乘起来而是乘除加减这样一路循环下去直到数字用完。有两个约束非常关键乘法、除法依旧比加法、减法优先除法是整数除法结果直接截断取整。拿n 10手动算一遍clumsy(10) 10 * 9 / 8 7 - 6 * 5 / 4 3 - 2 * 1 90 / 8 7 - 30 / 4 3 - 2 11 7 - 7 3 - 2 12注意90 / 8在 C 语言里是11不是11.2530 / 4是7不是7.5。如果你带着浮点思维去做第一步就偏了。1.2 三个最容易翻车的认知误区第一个误区把它当成阶乘的变形试图用阶乘公式或递推去套。笨阶乘跟阶乘唯一的共同点是数字从 n 一路降到 1运算结构完全不一样。我最初想写int ans n; for (int i n-1; i 1; i--) { ... }这种循环但运算符不是固定的乘法直接套阶乘模板只会写出一个不伦不类的东西。第二个误区把整数除法当成浮点除法或者反过来把整数除法想得过于简单。比如11 / 2在普通数学里是5.5在 C 语言里是5。LeetCode 原题明确要求整数除法C 语言默认行为正好吻合但前提是你不能写出(double)n * (n-1) / (n-2)这种东西再转回 int。第三个误区忽略乘除优先级从左到右硬算。有的同学看到10 * 9 / 8 7知道先算乘除但看到后面- 6 * 5 / 4时容易把负号连着6 * 5一起先算。其实如果严格按“减号后面整体是乘除结果”来理解-6 * 5 / 4在 C 语言里和-(6 * 5 / 4)结果碰巧一致但这个“碰巧”掩盖了真正的难点遇到加减法时我们不能立刻把它和前面的结果合并因为后面可能还有乘除等着计算。这也是为什么模拟法需要一个栈。2. 先动手模拟C 语言栈模拟完整实现与原理2.1 为什么“直接从左往右算”不行如果表达式里只有乘除从左往右算完全没问题因为乘除本身满足左结合。但笨阶乘里混入了加减问题就来了10 * 9 / 8 7 - 6 * 5 / 4 ...当你扫描到 7时这个7可以直接作为一项留下来但当你扫描到- 6时后面立刻跟了* 5所以-6不能直接入最终答案必须等6 * 5算出结果、再除以4之后才能作为一项参与最终求和。这个过程天然适合用栈来模拟。遇到乘除把栈顶元素取出来和当前数运算再把结果放回栈顶遇到加减把当前数带着正负号直接压栈。等所有数字扫完栈里留下的都是“已经处理完乘除、可以相加”的项整体求和就是答案。2.2 数组栈模拟的完整实现C 语言写栈最舒服的方式就是数组模拟不需要malloc也不容易内存泄漏。题目给的范围是1 n 10000栈深度撑死也就是 n 个元素所以开一个10005的数组非常宽裕。int clumsy(int n) { int stack[10005]; int top 0; int op 0; // 0: *, 1: /, 2: , 3: - stack[top] n; for (int i n - 1; i 1; i--) { switch (op % 4) { case 0: // 乘法栈顶 * i stack[top - 1] * i; break; case 1: // 除法栈顶 / i stack[top - 1] / i; break; case 2: // 加法直接压入 i stack[top] i; break; case 3: // 减法直接压入 -i stack[top] -i; break; } op; } int ans 0; while (top 0) { ans stack[--top]; } return ans; }这段代码的核心是stack[top - 1] * i和stack[top - 1] / i。它相当于“弹出栈顶、做完运算、再压回去”只是用原地修改简化了。遇到加法和减法时不需要立即运算直接把带符号的数丢进栈里等到最后统一累加。用n 10跑一遍栈的变化压入 10 i9, op0: 栈顶 10*990 i8, op1: 栈顶 90/811 i7, op2: 压入 7 i6, op3: 压入 -6 i5, op0: 栈顶 -6*5-30 i4, op1: 栈顶 -30/4-7 i3, op2: 压入 3 i2, op3: 压入 -2 i1, op0: 栈顶 -2*1-2 栈内: [11, 7, -7, 3, -2] 求和 12结果和手算一致。这段代码对n 1也成立初始直接压入1循环不执行返回1。2.3 复杂度与为什么这段代码能过时间上每个数字只处理一次总体是 O(n)。空间上栈里元素最多 O(n)。n最大只有 10000这种复杂度在 LeetCode 上就是毫秒级完全够用。但只说“够用”其实有点浪费这道题。笨阶乘的价值在于你一旦跑出几个小数据很快会发现结果非常有规律。这时候就该进入下一步尝试用数学把 O(n) 压成 O(1)。3. 数学规律从四元组抵消到 O(1) 公式推导3.1 一个关键的整除恒等式先看一个核心引理对任意a 5有a * (a - 1) / (a - 2) a 1这里的/是 C 语言的整数除法。证明很简单a * (a - 1) (a - 2)(a 1) 2因为0 2 a - 2当a 5时所以整数除法的商恰好是a 1余数是2。这个恒等式是整道题的钥匙。它告诉我们连续的乘除项在整数除法下会被“压平”变成一个非常接近原数的线性值。3.2 逐轮抵消从第二轮开始的固定贡献把笨阶乘按每 4 个数分成一轮因为运算符循环周期正好是 4。第一轮是n * (n-1) / (n-2) (n-3)利用引理当n 5时第一轮等于(n 1) (n - 3) 2n - 2从第二轮开始每一轮第一个数字前面是负号。比如第二轮是- (n-4) * (n-5) / (n-6) (n-7)只要n - 4 5也就是n 9这一轮就等于- ((n-4) 1) (n-7) -(n-3) (n-7) -4第三轮、第四轮同样如此。只要轮次完整、轮首数字不小于 5从第二轮开始的每一完整轮贡献都是固定的-4。拿n 12验证一下clumsy(12) 12*11/10 9 - 8*7/6 5 - 4*3/2 1 13 9 - 9 5 - 6 1 13第一轮贡献13 9 22也即2n - 2 22。第二轮首项是 8贡献-8*7/6 5 -9 5 -4。第三轮首项是 4因为 4 小于 5引理不适用需要单算-4*3/2 1 -6 1 -5。总和22 - 4 - 5 13。这个例子清楚展示了“最后一轮特殊、中间轮固定抵消”的结构。再拿n 100验证第一轮贡献198从 96 到 8 共 23 个完整轮每轮-4合计-92最后一轮4*3/2那组贡献-5总结果198 - 92 - 5 101。而公式n % 4 0给的是n 1 101完美吻合。3.3 按 n%4 分情况得到 O(1) 代码既然每隔四项就抵消一轮最终结果只取决于 n 除 4 的余数。归纳下来就是四个公式n % 4 0结果是n 1n % 4 1结果是n 2n % 4 2结果是n 2n % 4 3结果是n - 1特别地n 1, 2, 3, 4这四个小值不再被“完整轮”覆盖必须单独处理。对应 C 代码非常短int clumsy(int n) { if (n 1) return 1; if (n 2) return 2; if (n 3) return 6; if (n 4) return 7; int r n % 4; if (r 0) return n 1; if (r 1) return n 2; if (r 2) return n 2; return n - 1; // r 3 }注意n 4绝对不能省。因为4 % 4 0不特判会返回5但真实值是4 * 3 / 2 1 7。类似的n 1不特判会走r 1分支返回3完全错误。4. 两种解法对比与 C 语言里的边界细节4.1 两种解法横向对比维度栈模拟数学公式时间复杂度O(n)O(1)空间复杂度O(n)O(1)代码量约 20 行约 10 行可读性直观贴近运算定义需要理解推导过程出错风险低但要小心栈顶更新高边界特判容易漏我个人的建议是两版都写但提交时优先用公式版。公式版代码短、运行快而且写完你可以用模拟版去对拍验证两个互相印证基本不可能错。4.2 整除截断负数场景到底要不要担心C 语言的整数除法是向零截断的。比如-7 / 2等于-3不是-4。笨阶乘的表达式里会出现负数参与乘除吗会。比如n 10时第二轮是-6 * 5 / 4栈里先出现-6乘完是-30再除 4 得到-7。那负数截断会不会影响最终结果我实际验证过对于笨阶乘的结构(-a * b) / c和-(a * b / c)结果一致。原因是a*b除以c的余数小于c取负后向零截断和“先截断再加负号”落在同一个整数上。所以即使你不小心把负号提到整个乘除项前面结果也不会变。不过这只是这道题的巧合换一道题别这么赌。4.3 溢出极限与整数类型的取舍题目给的n 10000最极端的中间值是10000 * 9999 99,990,000远小于int上限约21.47 亿所以用int完全安全。但如果你改练习平台、数据范围变大int就可能爆。我的习惯是这类题一律用long long栈和long long返回值多花不了几个字节但心里踏实。栈数组也值得提一句每次乘除都是在栈顶原地更新加减才会新压入一个数。所以栈里最多同时存在约n个元素10005对n 10000绰绰有余。5. 测试与复盘边界用例、对拍方式和这类题的通法5.1 边界用例别忘了 1 到 4刷题时最容易被“公式简洁”冲昏头脑、随手把边界忘掉。笨阶乘的边界就是n 1, 2, 3, 4n手算过程结果1没有后续运算122 * 1233 * 2 / 1644 * 3 / 2 1 6 17这几个值单独测一遍顺便也把n 5到n 10都跑一遍确认公式版没有在小数据上翻车。5.2 对拍验证两个实现互相当参照我刷题有个习惯遇到能推导出公式的题一定写一个暴力版或模拟版来做对拍。把两个实现放在一起从 1 跑到 10000用assert检查结果一致#include assert.h #include stdio.h int clumsy_stack(int n) { int stack[10005]; int top 0; int op 0; stack[top] n; for (int i n - 1; i 1; i--) { switch (op % 4) { case 0: stack[top - 1] * i; break; case 1: stack[top - 1] / i; break; case 2: stack[top] i; break; case 3: stack[top] -i; break; } op; } int ans 0; while (top 0) ans stack[--top]; return ans; } int clumsy_formula(int n) { if (n 1) return 1; if (n 2) return 2; if (n 3) return 6; if (n 4) return 7; int r n % 4; if (r 0) return n 1; if (r 1) return n 2; if (r 2) return n 2; return n - 1; } int main(void) { for (int n 1; n 10000; n) { assert(clumsy_stack(n) clumsy_formula(n)); } printf(all ok\n); return 0; }这套对拍代码在本地跑完再提交公式版基本可以做到一遍过。对拍最大的价值不是证明你的公式一定对而是让你在提交前把所有不自信消灭掉。5.3 这类题的通用破题顺序笨阶乘不是第一道“伪装成模拟的规律题”也不会是最后一道。遇到这种运算规则固定、循环出现的题目我的破题顺序是先手算 5 到 10 个样例看结果有没有明显的同余规律优先写一个不依赖规律的模拟版本保证自己能正确复现题目定义用模拟版本跑出更多数据猜测公式比如观察n % 4的分类用对拍验证猜测而不是直接拿公式提交最后再精简代码提交时可以选公式版。这个流程最关键的其实是第二步。很多人一上来就想找数学公式结果公式没推出来、连暴力实现也写不利索。先把模拟写对等于给了自己一个参考答案后面推公式时心里有底。我个人刷这道题最大的收获不是记住了n % 4的四种结果而是养成了“先怀疑有规律、再动手模拟”的习惯。LeetCode 的简单题里很多看起来要模拟的题目其实都藏着周期或同余规律找到规律后代码能短一半、快一个量级。下次再碰到类似题目不妨先花三分钟观察一下输出序列再决定怎么写。