笨阶乘

难度: Medium

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。

例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。

另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。

示例 1：

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

示例 2：

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

提示：

1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1 （答案保证符合 32 位整数。）

Submission

运行时间: 28 ms

内存: 16.5 MB

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 = []
        r = 0
        ans = n*(n-1)//(n-2)+(n-3)
        for i in range(n-4,0,-1):
            if r == 0:
                stack.append(i)
            if r == 1:
                stack[0]*=i
            if r == 2:
                stack[0] //=i
            if r == 3:
                ans -= stack[0]-i
                stack.pop()
            r += 1
            if r == 4:
                r -=4
        if stack:
            ans -= stack[0]
        return ans

Explain

此题解利用栈来处理'笨阶乘'的运算规则。首先，对于n小于等于4的特殊情况，直接返回计算结果。对于n大于4的情况，题解首先计算前四个数的笨阶乘结果，并将其存入变量ans。接下来，从n-4开始向下递减，使用一个循环和一个栈来处理剩余的数。栈用于暂存当前的乘除结果，而变量r用来指示当前的操作（乘、除、加、减）。每遍历四个数后，根据r的值将栈顶元素加到ans中或从ans中减去，然后重置r。最后，如果栈中还有元素，则从ans中减去栈顶元素，最终返回ans。

时间复杂度: O(n)

空间复杂度: O(1)

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 = []
        r = 0
        ans = n*(n-1)//(n-2)+(n-3)  # 计算前四个数的笨阶乘结果
        for i in range(n-4, 0, -1):
            if r == 0:
                stack.append(i)  # 加入初始元素
            if r == 1:
                stack[0] *= i  # 进行乘法操作
            if r == 2:
                stack[0] //= i  # 进行除法操作
            if r == 3:
                ans -= stack[0] - i  # 进行减法操作，减去栈内元素与当前i的差
                stack.pop()  # 清除栈顶元素
            r += 1
            if r == 4:
                r -= 4  # 重置操作符计数器
        if stack:
            ans -= stack[0]  # 如果栈中还有元素，从ans中减去
        return ans

Explore

在处理n大于4的情况时，使用栈来存储中间计算结果是为了方便管理和计算涉及乘法和除法的操作。由于乘法和除法具有左结合性，且在算法中它们的优先级高于加法和减法，使用栈可以帮助我们暂存这些操作的中间结果，然后在遇到加法或减法时再进行处理。栈的后进先出特性使得我们可以有效地处理这种优先级和操作顺序的需求，确保在每个加法或减法操作之前，所有的乘法和除法操作都已经被正确处理。

对于n小于等于4的情况，结果是通过直接计算得出的。由于n的值较小，可以直接应用笨阶乘的定义进行计算来验证每个结果。例如，clumsy(1)只有1，clumsy(2)是2*1，clumsy(3)是3*2/1，clumsy(4)是4*3/2+1。这些结果都是通过直接应用笨阶乘的操作规则（乘、除、加、减）得出的。没有一个特定的通用公式来直接计算n小于或等于4的情况，而是通过具体的操作顺序和数值直接推导出的。

在循环中，变量r用作操作符的索引，控制当前应该执行的运算操作。初始时r设置为0，表示从乘法开始。每处理一个数字后，r会增加1，以此顺序控制操作：r为0时执行乘法，r为1时执行除法，r为2时执行加法，r为3时执行减法。每当r达到4时，说明一个完整的操作周期（乘、除、加、减）已完成，此时将r重置为0，开始下一个周期。这种方式确保了在整个计算过程中，操作符能够按照题目要求的固定顺序循环使用。