LeetCode 1006. 笨阶乘

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

题目描述

✅ 1006. 笨阶乘

image-20260929070949843

image-20260929070949927

题意分析

将整数从 n 递减排列到 1，在它们之间依次放入乘、除、加、减运算符，四种运算循环出现，求最终表达式的值。

运算符出现顺序不等于可以把整个式子从左到右直接累计：乘除优先于加减，同级运算从左到右。原式的乘除段由正数组成，每次除法都取整数商，不能保留小数到最后再统一取整。

解法：栈模拟运算优先级

核心思路

[!blue]

按加减号把表达式分成若干带符号的项，每一项内部只含连续乘除。最终结果就是这些项的和；因此只要把当前乘除项算完整，就不需要再处理复杂的优先级。

用栈保存已经开始的各项，栈顶是当前还可能继续接乘除的项。遇到乘法或除法，直接修改栈顶；遇到加法，压入一个新的正数项；遇到减法，压入一个新的负数项。这样后续乘除只影响当前项，不会误作用于前面的整段总和。

减号放进数值的符号后，仍可直接对栈顶执行乘除。原式在减号后的乘除段先求正整数商再被减去，等价于对负项使用向零截断的整数除法；Java 和 Go 的除法正好满足这个关系，不能改成负数向下取整。

每读入一个操作数，栈里各项之和就是当前已读部分按优先级计算的值，只有栈顶还可能被后续乘除延长。操作数逐个递减，运算符编号按模 4 切换；处理到 1 后，把各项求和即可。

解题步骤

  1. 把 n 作为第一个项放入栈，运算符编号初始化为乘法。
  2. 从 n - 1 递减到 1，根据当前编号执行乘、除、加或减。
  3. 乘除直接覆盖栈顶，加法压入当前正数，减法压入当前数的相反数。
  4. 每处理一个操作数后，将编号更新为 (op + 1) % 4。
  5. 全部操作数处理完后，返回栈内各项之和；n = 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)$，保存带符号的项。

关键点总结

[!green]

  • 加减把表达式分项，乘除只延长当前项，这个划分直接体现优先级。
  • 保存负项就能保留减号的作用范围，无需在后续乘除时额外切换符号。
  • 整数除法在每次执行时就截断，浮点累计后再取整不等价。

易错点总结

[!yellow]

  • 用一个总和按出现顺序直接乘除加减，会让乘除作用于前面所有项，破坏优先级。
  • 乘除结果再次入栈而不替换旧栈顶，会把原项重复计入答案。
  • 减法也压入正数，却没有另行记录符号，会把本应减去的整段变成加法。
  • 对负栈顶改用向下取整，与原式先求正商再取负的含义不一致。
  • 循环没有处理到操作数 1，会漏掉表达式的最后一步。

相似题目

题目 难度 关联与区别
227. 基本计算器 II 中等 同样需要先算乘除再算加减，本题数字和运算符顺序固定，可以简化通用表达式解析。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/75301058
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！