LeetCode 1006. 笨阶乘

Categories:

题目描述
思路分析
1. 解法一：栈模拟运算优先级（推荐）
相似题目

题目描述

✅ 1006. 笨阶乘

思路分析

解法一：栈模拟运算优先级（推荐）

核心思路：

按 “* / + -“ 循环应用到递减序列。

乘除需要和前一项结合，使用栈存储中间结果。

加法直接入栈，减法转为入栈负数，最后求和。

复杂度分析：

时间复杂度：O(n)，其中 n 表示 N 的大小。

空间复杂度：O(n)，栈存储中间结果。

import java.util.*;

class Solution {
    public int clumsy(int n) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(n);
        n--;
        int op = 0;

        while (n > 0) {
            if (op == 0) {
                stack.push(stack.pop() * n);
            } else if (op == 1) {
                stack.push(stack.pop() / n);
            } else if (op == 2) {
                stack.push(n);
            } else {
                stack.push(-n);
            }
            op = (op + 1) % 4;
            n--;
        }

        int sum = 0;
        while (!stack.isEmpty()) {
            sum += stack.pop();
        }
        return sum;
    }
}

func clumsy(n int) int {
    stack := []int{n}
    n--
    op := 0

    for n > 0 {
        if op == 0 {
            stack[len(stack)-1] = stack[len(stack)-1] * n
        } else if op == 1 {
            stack[len(stack)-1] = stack[len(stack)-1] / n
        } else if op == 2 {
            stack = append(stack, n)
        } else {
            stack = append(stack, -n)
        }
        op = (op + 1) % 4
        n--
    }

    sum := 0
    for _, v := range stack {
        sum += v
    }
    return sum
}

相似题目

题目	难度	考察点
150. 逆波兰表达式求值	中等	栈
227. 基本计算器 II	中等	运算符优先级
224. 基本计算器	困难	栈
770. 基本计算器 IV	困难	表达式
772. 基本计算器 III	困难	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/75301058