熊厂

昨天，熊厂内部发了全员信，通知职级体系大调整。

为了适配 AI 时代的业务需求、打破人才发展壁垒、提升组织效率，将原有的 T（技术）、P（产品）、M（管理）等多序列并行，统一为 5~12 级简洁数字体系。

改变看起来不小，但其实也仅限如此。

不降级、不降薪、不改变现有汇报关系，仅职级标签变更，所有原同职级员工（如所有 T7），全部统一对应到同一新职级（9 级），不做差异化调整。

不得不说，熊厂现在越来越不像互联网公司，像个国企。

作为最早押注大模型的互联网公司，现在连第二梯队都排不上，最早布局自动驾驶，现在也没有声势了。

曾经电商业务也被打得不行的老队友阿里，现在也借着 AI，重新焕发第二春了，不知道熊厂的春天，何时到来。

...

聊到这里，来一道和「阿里巴巴」相关的算法题。

题目描述

平台：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

提示：

•   （答案保证符合 32 位整数）

通用表达式

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

「事实上，我提供这套解决方案不仅仅能解决只有 + - ( )（[224. 基本计算器](https://mp.weixin.qq.com/s/SOfHtzWhGR6fWxsyo9wmQw） 或者 + - * /(227. 基本计算器 II) 的表达式问题，还能能解决 + - * / ^ % ( ) 的完全表达式问题。」

甚至支持自定义运算符，只要在运算优先级上进行维护即可。

「对于「表达式计算」这一类问题，你都可以使用这套思路进行解决。我十分建议你加强理解这套处理逻辑。」

对于「任何表达式」而言，我们都使用两个栈 nums 和 ops：

• nums ： 存放所有的数字
• ops ：存放所有的数字以外的操作

然后从前往后做，对遍历到的字符做分情况讨论：

• 空格 : 跳过
• ( : 直接加入 ops 中，等待与之匹配的 )
• ) : 使用现有的 nums 和 ops 进行计算，直到遇到左边最近的一个左括号为止，计算结果放到 nums
• 数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums
• + - * / ^ % : 需要将操作放入 ops 中。 「在放入之前先把栈内可以算的都算掉（只有「栈内运算符」比「当前运算符」优先级高/同等，才进行运算）」，使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums

我们可以通过 🌰 来理解 「只有「栈内运算符」比「当前运算符」优先级高/同等，才进行运算」 是什么意思：

因为我们是从前往后做的，假设我们当前已经扫描到 2 + 1 了（此时栈内的操作为 + ）。

1. 如果后面出现的 + 2 或者 - 1 的话，满足「栈内运算符」比「当前运算符」优先级高/同等，可以将 2 + 1 算掉，把结果放到 nums 中；
2. 如果后面出现的是 * 2 或者 / 1 的话，不满足「栈内运算符」比「当前运算符」优先级高/同等，这时候不能计算 2 + 1。

更为详细的讲解可以看这篇题解 ：使用「双栈」解决「究极表达式计算」问题

Java 代码：

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);
    }
}

C++ 代码：

class Solution {
public:
    int clumsy(int n) {
        stack<int> nums;
        stack<char> ops;
        // 维护运算符优先级
        map<char, int> map = {{'*', 2}, {'/', 2}, {'+', 1}, {'-', 1}};
        char opsSeq[] = {'*', '/', '+', '-'};
        for (int i = n, j = 0; i > 0; i--, j++) {
            char op = opsSeq[j % 4];
            nums.push(i);
            // 如果「当前运算符优先级」不高于「栈顶运算符优先级」，说明栈内的可以算
            while (!ops.empty() && map[ops.top()] >= map[op]) {
                calc(nums, ops);
            }
            if (i != 1) ops.push(op);
        }
        // 如果栈内还有元素没有算完，继续算
        while (!ops.empty()) calc(nums, ops);
        return nums.top();
    }
    void calc(stack<int>& nums, stack<char>& ops) {
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        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.push(ans);
    }
};

• 时间复杂度：
• 空间复杂度：

最后

巨划算的 LeetCode 会员优惠通道目前仍可用 ~

使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。

我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。