各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 67 天。今天力扣上的每日一题是「1006. 笨阶乘」。

解题思路

3 月的每日一题中，我们已经做过了 150. 逆波兰表达式求值 这个题目。表达式求值的题目一通百通。今天的题目其实也是个数学表达式求值。

先解释一下题意：对于输入的 n，要求 n 的笨阶乘。也就是要求表达式 n * (n - 1) / (n - 2) + (n - 3) - (n - 4) * (n - 5)....1 的值，其中的符号是按照 [*, / , +, -] 这个数学依次循环添加进去的。

我们知道求解没有括号的表达式的时候，运算符是优先级的：先乘除，后加减。

我们平时见到的运算表达式是中缀表达式，即 "操作数① 运算符② 操作数③" 的顺序，运算符在两个操作数中间。
类似的还有后缀表达式**是 "操作数① 操作数③ 运算符②"** 的顺序，运算符在两个操作数之后。

对于表达式求值，大家已经很熟悉了，需要用「栈」这个数据结构。求解没有括号的中缀表达式的时候，可以用一句顺口溜来概括：遇到乘除立即算，遇到加减先入栈。

  • 「乘除立即算」的含义是把栈顶元素和当前元素进行 * 或者 / 的计算
    - 「加减先入栈」的含义是如果当前操作符是 + 则直接把当前数字进栈，如果当前操作符是 - 则把当前数字取反放入到栈中。

以 clumsy(10) = 10 9 / 8 + 7 - 6 5 / 4 + 3 - 2 * 1 为例，用动画解释一下这个过程：

该动画对应的 PPT 如下，可以逐步观看：

Python 躲坑

如果你使用 Python 刷题，需要注意下面的这个坑。其他语言可以不看这部分。

python 的整数除法是向下取整，而不是向零取整，对于负数的除法会有问题。

  • python2 的除法 “/“ 是整数除法， "-3 / 2 = -2" ；
  • python3 的地板除 “//“ 是整数除法， "-3 // 2 = -2" ；
  • python3 的除法 “/“ 是浮点除法， "-3 / 2 = -1.5" ；

而 C++/Java 中的整数除法是向零取整。

  • C++/Java 中 "-3 / 2 = -1" .

本题的题意（一般情况）都是要求向零取整的。

解决方法 1

对 Python 的整数除法问题，可以用 int(num1 / float(num2)) 来做，即先用浮点数除法，然后取整。

  • 无论如何，浮点数除法都会得到一个浮点数，比如 "-3 / 2.0 = 1.5" ；
    - 此时再取整，就会得到整数部分，即 float(-1.5) = -1 。

解决方法 2

使用库函数 operator.truediv(num1, num2) ，调用该函数等价于 num1 / float(num2)。

代码

代码如下，挺简洁的。

  1. class Solution(object):
  2.     def clumsy(self, N):
  3.         op = 0
  4.         stack = [N]
  5.         for i in range(N - 1, 0, -1):
  6.             if op == 0:
  7.                 stack.append(stack.pop() * i)
  8.             elif op == 1:
  9.                 stack.append(int(stack.pop() / float(i)))
  10.             elif op == 2:
  11.                 stack.append(i)
  12.             elif op == 3:
  13.                 stack.append(-i)
  14.             op = (op + 1) % 4
  15.         return sum(stack)
  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

刷题心得

  • 数学表达式求值，一般都用到「栈」；
    - 表达式求值的难点在于各个操作符的优先级；
    - 不要看到题目长、题目新，就害怕啊，其实不难的；

  • 本题不能直接使用 eval()，这相当于作弊。

参考资料：
力扣官方题解

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！