Medium

题目描述

正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。

例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

我们通过将乘法操作替换为固定的运算符轮换，使用递减的整数制作笨阶乘：乘法 *、除法 /、加法 + 和减法 - 按此顺序循环。

例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。

但是，这些操作仍然使用通常的算术运算顺序。我们在任何加法或减法步骤之前进行所有乘法和除法步骤，乘法和除法步骤从左到右处理。

另外，我们使用的除法是向下取整除法，使得 10 * 9 / 8 = 90 / 8 = 11。

给定一个整数 n，返回 n 的笨阶乘。

示例 1：

输入: n = 4
输出: 7
解释: 7 = 4 * 3 / 2 + 1

示例 2：

输入: n = 10
输出: 12
解释: 12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

提示：

  • 1 <= n <= 10^4

解题思路

解题思路

这道题要求计算笨阶乘，运算符按照 *、/、+、- 的顺序循环使用。由于需要遵循运算优先级（乘除优先于加减），我们需要正确处理表达式的计算顺序。

方法一：栈模拟（推荐）

使用栈来处理运算优先级：

  1. 遇到乘法和除法时，直接与栈顶元素计算并更新栈顶
  2. 遇到加法时，直接将数字压入栈
  3. 遇到减法时，将数字的负值压入栈（因为减法相当于加负数）
  4. 最后将栈中所有元素相加得到结果

方法二：数学规律

通过观察可以发现，除了前几个特殊情况，从 n=5 开始，每4个数为一组的模式：

  • n * (n-1) / (n-2) + (n-3) - ...
  • 每组的值约等于 n+1

但考虑到边界情况较多，栈模拟方法更加直观和可靠。

实现要点

  1. 运算符循环：用 i % 4 来确定当前应该使用的运算符
  2. 除法向下取整：使用整数除法
  3. 栈处理：乘除法立即计算，加减法通过栈延迟处理

代码实现

class Solution {
public:
    int clumsy(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 6;
        if (n == 4) return 7;
        
        stack<int> st;
        st.push(n);
        n--;
        
        int op = 0; // 0: *, 1: /, 2: +, 3: -
        while (n > 0) {
            if (op == 0) { // *
                int top = st.top();
                st.pop();
                st.push(top * n);
            } else if (op == 1) { // /
                int top = st.top();
                st.pop();
                st.push(top / n);
            } else if (op == 2) { // +
                st.push(n);
            } else { // -
                st.push(-n);
            }
            op = (op + 1) % 4;
            n--;
        }
        
        int result = 0;
        while (!st.empty()) {
            result += st.top();
            st.pop();
        }
        return result;
    }
};

class Solution:
    def clumsy(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        if n == 3:
            return 6
        if n == 4:
            return 7
        
        stack = [n]
        n -= 1
        
        op = 0  # 0: *, 1: /, 2: +, 3: -
        while n > 0:
            if op == 0:  # *
                stack.append(stack.pop() * n)
            elif op == 1:  # /
                top = stack.pop()
                stack.append(int(top / n))  # 向下取整
            elif op == 2:  # +
                stack.append(n)
            else:  # -
                stack.append(-n)
            
            op = (op + 1) % 4
            n -= 1
        
        return sum(stack)

public class Solution {
    public int Clumsy(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 6;
        if (n == 4) return 7;
        
        Stack<int> stack = new Stack<int>();
        stack.Push(n);
        n--;
        
        int op = 0; // 0: *, 1: /, 2: +, 3: -
        while (n > 0) {
            if (op == 0) { // *
                int top = stack.Pop();
                stack.Push(top * n);
            } else if (op == 1) { // /
                int top = stack.Pop();
                stack.Push(top / n);
            } else if (op == 2) { // +
                stack.Push(n);
            } else { // -
                stack.Push(-n);
            }
            op = (op + 1) % 4;
            n--;
        }
        
        int result = 0;
        while (stack.Count > 0) {
            result += stack.Pop();
        }
        return result;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var clumsy = function(n) {
    if (n <= 2) return n;
    if (n == 3) return 6;
    if (n == 4) return 7;
    
    let result = Math.floor(n * (n - 1) / (n - 2)) + (n - 3);
    n -= 4;
    
    while (n >= 4) {
        result -= Math.floor(n * (n - 1) / (n - 2)) - (n - 3);
        n -= 4;
    }
    
    if (n == 3) {
        result -= 6;
    } else if (n == 2) {
        result -= 2;
    } else if (n == 1) {
        result -= 1;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
栈模拟O(n)O(n)
  • 时间复杂度: O(n)，需要遍历从 n 到 1 的所有数字
  • 空间复杂度: O(n)，栈最多存储 O(n) 个元素

相关题目