LC 1006. 笨阶乘

题目描述

这是 LeetCode 上的 1006. 笨阶乘 ，难度为中等。

通常，正整数 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 位整数）

通用表达式解法

第一种解法是我们的老朋友解法了，使用「双栈」来解决通用表达式问题。

事实上，我提供这套解决方案不仅仅能解决只有 + - ( )（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)$

数学解法（打表技巧分析）

这次在讲【证明】之前，顺便给大家讲讲找规律的题目该怎么做。

由于是按照特定顺序替换运算符，因此应该是有一些特性可以被我们利用的。

通常我们需要先实现一个可打表的算法（例如上述的解法一，这是为什么掌握「通用表达式」解法具有重要意义），将连续数字的答案打印输出，来找找规律：

Solution solution = new Solution();
for (int i = 1; i <= 10000; i++) {
    int res = solution.clumsy(i);
    System.out.println(i + " : " + res);
}

似乎 $n$ 与答案比较接近，我们考虑将两者的差值输出：

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)$

证明

讲完我们的【实战技巧】之后，再讲讲如何证明。

上述的做法比较适合于笔试或者比赛，但是面试，通常还需要证明做法为什么是正确的。

我们不失一般性的分析某个 n，当然这个 n 必须是大于 4，不属于我们的特判值。

然后对 n 进行讨论（根据我们的打表猜想去证明规律是否可推广）：

n % 4 == 0 : $f(n) = n (n - 1) / (n - 2) + … + 5 - 4 3 / 2 + 1 = n + 1$，即 diff = 1
n % 4 == 1 : $f(n) = n (n - 1) / (n - 2) + … + 6 - 5 4 / 3 + 2 - 1 = n + 2$，即 diff = 2
n % 4 == 2 : $f(n) = n (n - 1) / (n - 2) + … + 7 - 6 5 / 4 + 3 - 2 * 1 = n + 2$，即 diff = 2
n % 4 == 3 : $f(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 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

数学栈

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 416. 分割等和子集上一篇

LC 90. 子集 II 下一篇