LeetCode 1006. 笨阶乘

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
数学 栈 模拟
目录

题目描述

✅ 1006. 笨阶乘

题意分析

把 n! 里连乘的那些乘号，换成 *、/、+、- 四个符号循环使用，操作数依次是 n, n-1, n-2, ... 一直递减到 1，求这个表达式的值。例如 n = 10 对应 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。

题目给了两条决定性的规则。第一，运算符是固定循环的，不需要词法分析、不需要读字符串，第 i 个运算符是什么完全由 i % 4 决定——这把「表达式求值」里最麻烦的解析部分整个省掉了。第二，除法是整数除法且只保留整数部分（向零截断），这意味着不能把连续的乘除合并成分数再约分，必须按出现顺序一步步算。

剩下的难点只有一个：优先级。* 和 / 要先于 + 和 - 结合，所以不能从左到右一路算下去。而 +、- 之间优先级相同、左结合，可以把减法看成加一个负数，从而把整个表达式化成若干个「项」的求和，项与项之间只剩加法。

约束是 1 ≤ n ≤ 10^4，规模很小；答案会在 int 范围内（最大项是 n * (n-1) / (n-2)，量级约 n，总和量级也在 n 附近），不必担心溢出，但中间的 n * (n-1) 在 n = 10^4 时接近 $10^8$，仍在 int 内。

边界是 n 很小的几种：n = 1 只有一个操作数，答案 1；n = 2 是 2 * 1 = 2；n = 3 是 3 * 2 / 1 = 6；n = 4 才第一次出现加号，4 * 3 / 2 + 1 = 7。好的实现应当让这些情形自然落进主循环，而不是靠一串特判。

解法：栈模拟运算优先级

核心思路

运算符按 *、/、+、- 循环出现，但普通四则运算的优先级仍然生效。可以把表达式按加减号切成若干带符号的项：乘除只会继续修改当前项，加减则开始一个新项。

用栈保存这些项。先把 n 作为第一项压栈，然后从 n - 1 递减到 1，并按四种运算循环处理：

  • 遇到 * 或 /，直接修改栈顶，因为它们属于当前项；
  • 遇到 +，把当前数作为新项压栈；
  • 遇到 -，把当前数的相反数压栈，将减法转化为加上负数。

不变量：处理完当前操作数后，栈中依次保存已读表达式按加减号分组后，各项已经完成的值；所有栈元素之和等于已读表达式的值。 乘除更新最后一项，加减追加一个带符号的新项，因此不变量始终成立。所有数处理完后，栈内求和就是完整表达式的结果。

Java 和 Go 的整数除法都向 0 截断，所以负项可以直接参与除法。例如 -30 / 4 = -7，与题目要求一致；不能先用浮点数计算、最后再统一取整。

解题步骤

  1. 创建栈并压入首个操作数 n。
  2. 用 op = 0, 1, 2, 3 分别表示 *、/、+、-。
  3. 从 x = n - 1 递减到 1：乘除覆盖栈顶，加法压入 x，减法压入 -x；每轮后令 op = (op + 1) % 4。
  4. 将栈中所有项相加并返回。

以 n = 7 为例：

表达式：7 * 6 / 5 + 4 - 3 * 2 / 1
栈变化：[7] -> [42] -> [8] -> [8, 4]
       -> [8, 4, -3] -> [8, 4, -6] -> [8, 4, -6]

最终结果为 8 + 4 - 6 = 6。边界 n = 1 时循环不执行，栈中只有 1，直接返回 1。

代码实现

class Solution {
    public int clumsy(int n) {
        int[] stack = new int[n];
        int top = 0;
        stack[top] = n;
        int op = 0;

        for (int x = n - 1; x >= 1; x--) {
            switch (op) {
                case 0:
                    stack[top] *= x;
                    break;
                case 1:
                    stack[top] /= x;
                    break;
                case 2:
                    stack[++top] = x;
                    break;
                default:
                    stack[++top] = -x;
            }
            op = (op + 1) % 4;
        }

        int answer = 0;
        for (int i = 0; i <= top; i++) {
            answer += stack[i];
        }
        return answer;
    }
}

func clumsy(n int) int {
	stack := make([]int, 1, n)
	stack[0] = n
	op := 0

	for x := n - 1; x >= 1; x-- {
		top := len(stack) - 1
		switch op {
		case 0:
			stack[top] *= x
		case 1:
			stack[top] /= x
		case 2:
			stack = append(stack, x)
		default:
			stack = append(stack, -x)
		}
		op = (op + 1) % 4
	}

	answer := 0
	for _, term := range stack {
		answer += term
	}
	return answer
}

复杂度分析

  • 时间复杂度： $O(n)$。每个操作数只处理一次，最后再线性求和。
  • 空间复杂度： $O(n)$。栈保存由加减号分隔出的项，最坏数量与 n 同阶。

关键点总结

  • 按加减号分项，乘除只修改当前项，可以直接落实运算符优先级。
  • 将减法表示成压入负数后，最终只需统一求和。
  • 栈中“已完成的带符号项”是不变量；它同时解释了乘除为何改栈顶、加减为何压新项。
  • 整数除法必须在每一步向 0 截断，Java 和 Go 的 / 正好符合题意。

易错点总结

  • 按出现顺序从左到右计算而忽略优先级： n = 7 会把 (8 + 4 - 3) * 2 / 1 算成 18，正确答案是 6。
  • 乘除结果压成新项而不是覆盖栈顶： n = 4 会重复保留原项，求和不再等于表达式值；正确结果应为 4 * 3 / 2 + 1 = 7。
  • 循环漏掉操作数 1： n = 5 的最后一步是 -1，若循环条件写成 x > 1 会得到 8，正确答案是 7。
  • 使用浮点除法并在最后统一取整： n = 10 会先保留 90 / 8 = 11.25 和 -30 / 4 = -7.5，最终截断得到 11；逐步整数除法的正确答案是 12。
  • 把运算符初值或轮转顺序写错： n = 4 的第一个运算必须是乘法，周期必须严格为 *、/、+、-。

相似题目

题目 难度 考察点
227. 基本计算器 II 中等 同样是「乘除就地结合、加减切项、最后求和」，但运算符要从字符串里解析，还要处理多位数字
224. 基本计算器 困难 引入括号与一元负号，需要用栈保存括号外的符号与部分和
772. 基本计算器 III 困难 括号与四则运算同时出现，是 224 与 227 的合并版，通常写成递归下降
150. 逆波兰表达式求值 中等 后缀表达式天生无优先级问题，栈里存的是操作数，遇运算符就弹两个
LCR 036. 逆波兰表达式求值 中等 与 150 同题，可用来检验对「向零截断」除法的处理是否一致
394. 字符串解码 中等 栈保存的是倍数与前缀而非数值，出栈时做展开，属于构造型的栈模拟
735. 小行星碰撞 中等 同为循环内按规则决定「入栈、改栈顶还是弹栈」，但结局分三种且当前元素可能被销毁