leetcode春季全国编程大赛答案

2022-05-18 21:26:38 浏览数 (1)

再来回顾下题目:

最近出题人的语文水准直线下降,看懂题目也成了考试的考点之一了。就让小编用人类的语言翻译一下这个题:

这之前,先让我们明白什么是数学里的期望值:

期望值大学时候老师讲过,就是实际的效果*概率 得到的就是了。比如:你去赌博,赢的话可以赢100块钱,但是几率只有1/3 。输的话输50块钱,但是几率有2/3。那么你是赌还是不赌呢?针对这个历史性问题,数学家给出了期望值的概念,如果最终期望为正,就可以赌,次数越多,你赚的就越稳。

你赢钱的期望值 = 100 * 1/3 = 33.333

你输钱的期望值 = -50 * 2/3 = -33.333

也就是说,你赌的次数越多,最终越接近不赔不赚。

那么再来回顾这道题:

首先我们要明白这个题到底有没有实际意义?一般没有实际意义的题目我是嗤之以鼻的。不过这道题,虽然花里胡哨,但是确实有一定实际意义和需求在。

说,有一个公司在招人。有俩个面试官,小a 和小b,他们俩个呢,不在一起办公。

然后某天hr推荐了7个简历过来,hr呢很负责,按照简历的能力值给排好顺序了。比如[1,2,3,3,3,6,6]

然后 俩位面试官呢 在自己的办公室,同时拿到了这7个简历,顺序什么的都一摸一样,他们自然而然的都从能力值最高的简历开始看起来。

也就是说 他们一开始 都会去选择 能力值6的 俩个简历。但是他们有可能拿重复了。比如这俩个能力值6的简历应聘者一个叫甲,一个叫乙。那么面试官小a可能第一次看的甲,然后小b可能第一次也看的甲。那么他们就看重复了。这就是公司上对于时间的一种浪费行为。然后小a看完了甲 又去看乙的简历,然后小b 看完了甲 同样去看乙的简历,这就必然又导致了一次重复。

那么这道题的现实意义就来了。计算出这个重复的期望值,也就是提前算一下公司会承担的浪费时间的成本。

刚刚我们举例里面,俩位面试官在能力值6的这俩份简历上 浪费了时间成本 为2,也就是第一次重复看了甲,第二次也重复看了乙。但是这种情况出现的概率是多少?应该是1/4

为啥是1/4呢?

因为一共四种情况:

1.小a先看甲,后看乙,小b先看甲,后看乙

2.小a先看甲,后看乙,小b先看乙,后看甲

3.小a先看乙,后看甲,小b先看甲,后看乙 4.小a先看乙,后看甲,小b先看乙,后看甲

综上所述:我们分析第一种情况的期望值为:重复2次 * 1/4 = 0.5

第二种情况的期望值为:重复0次 * 1/4 = 0

第三种情况的期望值为:重复0次 * 1/4 = 0

第四种情况的期望值为:重复2次 * 1/4 = 0.5

最后总结果为:0.5 0 0 0.5 = 1

这个结果就是我们对能力值6的俩份简历的最终期望值结果。

然后我们再去计算 能力值 [1,2,3,3,3,6,6] 中 3的最终期望值 然后是2,然后是1。

最后把这些加到一起,就是最终答案了

看到这,大家应该已经明白了这种计算浪费时间成本的期望值的方法了吧?

那么就试着理解下这个最终答案吧?

代码语言:javascript复制
class Solution(object):
    def expectNumber(self, scores):
        """
        :type scores: List[int]
        :rtype: int
        """
        scores.sort()
        scores = scores[::-1]
        res = []
        tmp_index = 1
        for i in range(len(scores)):
            try:
                if scores[i 1] == scores[i]:
                    tmp_index  =1
                    continue
                else:
                    res.append(tmp_index)
                    tmp_index = 1
            except:
                res.append(tmp_index)
        return len(res)

0 人点赞