题目描述
这是 LeetCode 上的 1006. 笨阶乘 ，难度为 中等。
Tag : 「数学」、「栈」
通常，正整数 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}231 <= answer <= 2^{31}231 - 1 （答案保证符合 32 位整数）
通用表达式解法
第一种解法是我们的老朋友解法了，使用「双栈」来解决通用表达式问题。
事实上，我提供这套解决方案不仅仅能解决只有 + - ( )（224. 基本计算器） 或者 + - * /(227. 基本计算器 II) 的表达式问题，还能能解决 + - * / ^ % ( ) 的完全表达式问题。
甚至支持自定义运算符，只要在运算优先级上进行维护即可。
对于「表达式计算」这一类问题，你都可以使用这套思路进行解决。我十分建议你加强理解这套处理逻辑。
对于「任何表达式」而言，我们都使用两个栈 nums 和 ops：
nums： 存放所有的数字ops：存放所有的数字以外的操作
然后从前往后做，对遍历到的字符做分情况讨论：
- 空格 : 跳过
(: 直接加入ops中，等待与之匹配的)): 使用现有的nums和ops进行计算，直到遇到左边最近的一个左括号为止，计算结果放到nums- 数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入
nums + - * / ^ %: 需要将操作放入ops中。
在放入之前先把栈内可以算的都算掉（只有「栈内运算符」比「当前运算符」优先级高/同等，才进行运算），使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums
我们可以通过 🌰 来理解 只有「栈内运算符」比「当前运算符」优先级高/同等，才进行运算 是什么意思：
因为我们是从前往后做的，假设我们当前已经扫描到 2 + 1 了（此时栈内的操作为 + ）。
- 如果后面出现的
+ 2或者- 1的话，满足「栈内运算符」比「当前运算符」优先级高/同等，可以将2 + 1算掉，把结果放到nums中； - 如果后面出现的是
* 2或者/ 1的话，不满足「栈内运算符」比「当前运算符」优先级高/同等，这时候不能计算2 + 1。
代码：
class Solution { public int clumsy(int n) { Deque<Integer> nums = new ArrayDeque<>(); Deque<Character> ops = new ArrayDeque<>(); // 维护运算符优先级 Map<Character, Integer> map = new HashMap<>(){{ put('*', 2); put('/', 2); put('+', 1); put('-', 1); }}; char[] cs = new char[]{'*', '/', '+', '-'}; for (int i = n, j = 0; i > 0; i--, j++) { char op = cs[j % 4]; nums.addLast(i); // 如果「当前运算符优先级」不高于「栈顶运算符优先级」，说明栈内的可以算 while (!ops.isEmpty() && map.get(ops.peekLast()) >= map.get(op)) { calc(nums, ops); } if (i != 1) ops.add(op); } // 如果栈内还有元素没有算完，继续算 while (!ops.isEmpty()) calc(nums, ops); return nums.peekLast(); } void calc(Deque<Integer> nums, Deque<Character> ops) { int b = nums.pollLast(), a = nums.pollLast(); int op = ops.pollLast(); int ans = 0; if (op == '+') ans = a + b; else if (op == '-') ans = a - b; else if (op == '*') ans = a * b; else if (op == '/') ans = a / b; nums.addLast(ans); } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(n)O(n)
数学解法（打表技巧分析）
这次在讲【证明】之前，顺便给大家讲讲找规律的题目该怎么做。
由于是按照特定顺序替换运算符，因此应该是有一些特性可以被我们利用的。
通常我们需要先实现一个可打表的算法（例如上述的解法一，这是为什么掌握「通用表达式」解法具有重要意义），将连续数字的答案打印输出，来找找规律：
Solution solution = new Solution(); for (int i = 1; i <= 10000; i++) { int res = solution.clumsy(i); System.out.println(i + " : " + res); } 复制代码
似乎 nn 与 答案比较接近，我们考虑将两者的差值输出：
Solution solution = new Solution(); for (int i = 1; i <= 10000; i++) { int res = solution.clumsy(i); System.out.println(i + " : " + res + " : " + (res - i)); } 复制代码
咦，好像发现了什么不得了的东西。似乎每四个数，差值都是 [1, 2, 2, -1]
再修改我们的打表逻辑，来验证一下（只输出与我们猜想不一样的数字）：
Solution solution = new Solution(); int[] diff = new int[]{1,2,2,-1}; for (int i = 1; i <= 10000; i++) { int res = solution.clumsy(i); int t = res - i; if (t != diff[i % 4]) { System.out.println(i + " : " + res); } } 复制代码
只有前四个数字被输出，其他数字都是符合我们的猜想规律的。
到这里我们已经知道代码怎么写可以 AC 了，十分简单。
代码：
class Solution { public int clumsy(int n) { int[] special = new int[]{1,2,6,7}; int[] diff = new int[]{1,2,2,-1}; if (n <= 4) return special[(n - 1) % 4]; return n + diff[n % 4]; } } 复制代码
- 时间复杂度：O(1)O(1)
- 空间复杂度：O(1)O(1)
证明
讲完我们的【实战技巧】之后，再讲讲如何证明。
上述的做法比较适合于笔试或者比赛，但是面试，通常还需要证明做法为什么是正确的。
我们不失一般性的分析某个 n，当然这个 n 必须是大于 4，不属于我们的特判值。
然后对 n 进行讨论（根据我们的打表猜想去证明规律是否可推广）：
n % 4 == 0: f(n) = n * (n - 1) / (n - 2) + ... + 5 - 4 * 3 / 2 + 1 = n + 1f(n)=n∗(n−1)/(n−2)+...+5−4∗3/2+1=n+1，即diff = 1n % 4 == 1: f(n) = n * (n - 1) / (n - 2) + ... + 6 - 5 * 4 / 3 + 2 - 1 = n + 2f(n)=n∗(n−1)/(n−2)+...+6−5∗4/3+2−1=n+2，即diff = 2n % 4 == 2: f(n) = n * (n - 1) / (n - 2) + ... + 7 - 6 * 5 / 4 + 3 - 2 * 1 = n + 2f(n)=n∗(n−1)/(n−2)+...+7−6∗5/4+3−2∗1=n+2，即diff = 2n % 4 == 3: f(n) = n * (n - 1) / (n - 2) + ... + 8 - 7 * 6 / 5 + 4 - 3 * 2 / 1 = n - 1f(n)=n∗(n−1)/(n−2)+...+8−7∗6/5+4−3∗2/1=n−1，即diff = -1
上述的表达式展开过程属于小学数学内容，省略号部分的项式的和为 0，因此你只需要关注我写出来的那部分。
至此，我们证明了我们的打表猜想具有「可推广」的特性。
甚至我们应该学到：证明可以是基于猜想去证明，而不必从零开始进行推导。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1006 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
