笨阶乘C++解法详解(力扣1006)

问题解析LeetCode 1006 “笨阶乘”要求对正整数N按递减顺序依次使用乘*、除/、加、减-四个运算符循环计算即clumsy(N) N * (N-1) / (N-2) (N-3) - (N-4) * (N-5) / (N-6) ...需返回计算结果。核心在于处理运算符优先级乘除优先于加减和循环模式。解法对比方法核心思路时间复杂度空间复杂度适用场景栈模拟用栈存储中间结果按运算符优先级处理O(N)O(N)通用性强直观模拟运算过程数学归纳观察规律推导出分段计算公式O(1)O(1)效率最高直接计算方法一栈模拟法通过栈保存待计算的值遇到乘除立即计算加减则入栈减法转为加负数最后对栈中所有元素求和。#include stack #include vector using namespace std; class Solution { public: int clumsy(int N) { stackint stk; stk.push(N); N--; int index 0; // 用于循环运算符0:*, 1:/, 2:, 3:- while (N 0) { if (index % 4 0) { // 乘法 int top stk.top(); stk.pop(); stk.push(top * N); } else if (index % 4 1) { // 除法 int top stk.top(); stk.pop(); stk.push(top / N); } else if (index % 4 2) { // 加法 stk.push(N); } else { // 减法转为加负数 stk.push(-N); } index; N--; } // 对栈中所有元素求和 int sum 0; while (!stk.empty()) { sum stk.top(); stk.pop(); } return sum; } };时间复杂度O(N)遍历 N 次。空间复杂度O(N)栈最多存储约 N/2 个元素。方法二数学归纳法O(1)通过观察 N 较大时的计算规律可发现每 4 个数一组(N * (N-1) / (N-2) (N-3))的结果近似为N1剩余部分可推导出分段公式 N ≤ 2直接返回 N。N 3返回6即3 * 2 / 1。N 4返回7即4 * 3 / 2 1。N 4若N % 4 0结果为N 1。若N % 4 1或N % 4 2结果为N 2。若N % 4 3结果为N - 1。class Solution { public: int clumsy(int N) { if (N 2) return N; if (N 3) return 6; if (N 4) return 7; // 根据 N 对 4 取余的结果返回对应值 if (N % 4 0) return N 1; if (N % 4 1 || N % 4 2) return N 2; return N - 1; // N % 4 3 } };时间复杂度O(1)。空间复杂度O(1)。推荐使用数学归纳法其效率最高代码简洁。栈模拟法虽直观但效率较低适用于需要严格模拟运算过程的场景。参考来源1006. 笨阶乘 - leetcode刷题(C)力扣1006.笨阶乘LeetCode 1006. 笨阶乘1006. Clumsy Factorial刷❤️PAT❤️乙级_1006❤️C/C❤️详细注释反思总结❤️1006 换个格式输出整数 (15 分)