不服气，川大数学博士吐槽华为招聘

宫水三叶的刷题日记

发布于 2024-02-06 17:03:27

2470

发布于 2024-02-06 17:03:27

文章被收录于专栏：宫水三叶的刷题日记

数学博士吐槽华为招聘

今天刷到一篇帖子：

文中来自川大的数学博士吐槽了华为对数学博士的招聘。

作者强调自己是川大的本硕博（算子分析方向），有论文，也拿过国家一等奖。

但自己投的华为简历，却石沉大海，了无音讯。

还直言道：自己在数学系待了 10 年，没有任何一个数学博士能够满足华为招聘三条要求中的两条，如果数学博士干的是华为招聘上的事情，毕业都难。

这事儿，怎么说呢，从不同角度，会有不同的理解。

首先，在企业招聘中，学历往往是起点门槛要求，而非唯一要求。

因此肯定不是说满足数学博士要求，就必然入面试，这一点和「本科/硕士」一样。

其次，企业招聘中，往往是「应用类」人才占比要比「科研类」人才占比更高。

因此在学历（数学博士）要求上，往往还会有企业所期望的技能要求，例如文中说的「熟练使用计算机编程语言」，也算是常规操作。

至于原帖作者说的，因为「华为招聘中有很多不是数学博士专业领域知识要求」，就得出「华为觉得不到这个水平就不算是博士」的结论，多少有点偏激了。

...

回归主线。

来一道不是数学博士也能做出来的算法题。

这道题曾经还是华为的校招机试原题。

题目描述

平台：LeetCode

题号：172

给定一个整数

，返回

结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3

输出：0

解释：3! = 6 ，不含尾随 0

示例 2：

输入：n = 5

输出：1

解释：5! = 120 ，有一个尾随 0

提示：

0 <= n <= 10^4

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

数学

对于任意一个

而言，其尾随零的个数取决于展开式中

的个数，而

可由质因数

2 * 5

而来，因此

的尾随零个数为展开式中各项分解质因数后

的数量和

的数量中的较小值。

即问题转换为对

[1, n]

中的各项进行分解质因数，能够分解出来的

的个数和

的个数分别为多少。

为了更具一般性，我们分析对

[1, n]

中各数进行分解质因数，能够分解出质因数

的个数为多少。根据每个数能够分解出

的个数进行分情况讨论：

能够分解出至少一个

的个数为

的倍数，在

[1, n]

范围内此类数的个数为

c_1 = \left \lfloor \frac{n}{p} \right \rfloor

能够分解出至少两个

的个数为

p^2

的倍数，在

[1, n]

范围内此类数的个数为

c_2 = \left \lfloor \frac{n}{p^2} \right \rfloor

...
能够分解出至少

个

的个数为

p^k

的倍数，在

[1, n]

范围内此类数的个数为

c_k = \left \lfloor \frac{n}{p^k} \right \rfloor

「我们定义一个合法的

需要满足

p^k \leqslant n

，上述的每一类数均是前一类数的「子集」（一个数如果是

p^k

的倍数，必然是

p^{k-1}

的倍数），因此如果一个数是

p^k

的倍数，其出现在的集合数量为

，与其最终贡献的

的数量相等。」

回到本题，

中质因数

的数量为 :

\sum_{i = 1}^{k_1}\left \lfloor \frac{n}{2^i} \right \rfloor = \left \lfloor \frac{n}{2} \right \rfloor + \left \lfloor \frac{n}{2^2} \right \rfloor + ... + \left \lfloor \frac{n}{2^{k_1}} \right \rfloor

中质因数

的数量为 :

\sum_{i = 1}^{k_2}\left \lfloor \frac{n}{5^i} \right \rfloor = \left \lfloor \frac{n}{5} \right \rfloor + \left \lfloor \frac{n}{5^2} \right \rfloor + ... + \left \lfloor \frac{n}{5^{k_2}} \right \rfloor

由

2 < 5

，可知

k_2 \leqslant k_1

，同时

相同的每一项满足

\left \lfloor \frac{n}{5^i} \right \rfloor \leqslant \left \lfloor \frac{n}{2^i} \right \rfloor

，可知最终

\sum_{i = 1}^{k_2}\left \lfloor \frac{n}{5^i} \right \rfloor \leqslant \sum_{i = 1}^{k_1}\left \lfloor \frac{n}{2^i} \right \rfloor

，即质因数

的个数必然不会超过质因数

的个数。我们只需要统计质因数

的个数即可。

Java 代码：

class Solution {
    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
}

Python 代码：

class Solution:
    def trailingZeroes(self, n: int) -> int:
        return n // 5 + self.trailingZeroes(n // 5) if n else 0

时间复杂度：

O(\log{n})

空间复杂度：忽略递归带来的额外空间开销，复杂度为

O(1)

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-02-05，如有侵权请联系 cloudcommunity@tencent.com 删除

华为

本文分享自宫水三叶的刷题日记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度