笨阶乘
难度:
标签:
题目描述
代码结果
运行时间: 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的情况直接返回结果,这些结果是如何确定的?是否有一个通用的公式或逻辑来解释这些特殊值?
▷🦆
在循环中,变量r是如何控制不同运算操作(乘、除、加、减)的执行顺序的?
▷