leetcode
leetcode 901 ~ 950
笨阶乘

笨阶乘

难度:

标签:

题目描述

代码结果

运行时间: 28 ms, 内存: 16.5 MB


// Java Stream solution for the problem
// The solution requires using Java Streams to apply the sequence of operations: *, /, +, - in a loop.
// We use a List to hold the elements and then apply reduce to combine them.

import java.util.stream.IntStream;

public class ClumsyFactorialStream {
    public int clumsy(int N) {
        return IntStream.rangeClosed(1, N)
                .map(i -> N - i + 1)
                .boxed()
                .reduce(new int[]{0, 1}, (acc, n) -> {
                    int op = (N - n) % 4;
                    if (op == 0) {
                        acc[1] *= n; // Multiplication
                    } else if (op == 1) {
                        acc[1] /= n; // Floor Division
                    } else if (op == 2) {
                        acc[0] += acc[1]; // Addition
                        acc[1] = n; // Prepare for subtraction
                    } else {
                        acc[0] -= acc[1]; // Subtraction
                        acc[1] = n; // Prepare for next multiplication
                    }
                    return acc;
                }, (a, b) -> a)[0];
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在处理n大于4的情况时,为什么选择使用栈来存储中间计算结果?
在处理n大于4的情况时,使用栈来存储中间计算结果是为了方便管理和计算涉及乘法和除法的操作。由于乘法和除法具有左结合性,且在算法中它们的优先级高于加法和减法,使用栈可以帮助我们暂存这些操作的中间结果,然后在遇到加法或减法时再进行处理。栈的后进先出特性使得我们可以有效地处理这种优先级和操作顺序的需求,确保在每个加法或减法操作之前,所有的乘法和除法操作都已经被正确处理。
🦆
题解中提到对于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用作操作符的索引,控制当前应该执行的运算操作。初始时r设置为0,表示从乘法开始。每处理一个数字后,r会增加1,以此顺序控制操作:r为0时执行乘法,r为1时执行除法,r为2时执行加法,r为3时执行减法。每当r达到4时,说明一个完整的操作周期(乘、除、加、减)已完成,此时将r重置为0,开始下一个周期。这种方式确保了在整个计算过程中,操作符能够按照题目要求的固定顺序循环使用。

相关问题