Yesterday, Leetcode held the algorithm competition team competition began. There are six questions, all of which are difficult, and there is no error feedback, which means that when you execute the script it doesn’t tell you what the expected output of the use case is, and you don’t even know if your output is right or wrong. If click submit, will make a series of cases to test, if it fails, you don’t know is which case cause you fail, don’t know you what is wrong is reported which lines of code (such as a special case in one line 15 subscript crossing/your use case timeout etc/your various output log will not give you show), The only way to know is if you fail the algorithm, there will be time to punish you. The difficulty is insane. Xiaobian also tried to make one of the questions, which took about 15 minutes. Here’s a look at the simplest one:

Come on, palm eye!



Note that the difficulty of this question is simple ~

So you can try and see if you can understand this problem. If you can see it then try to figure out how to use the code

To achieve it.

Recently the language level of the person who gives the question drops straight line, understand the topic also became one of the examination points of the exam. Let xiaobian use human language to translate this question:

Before we do that, let’s understand what expected value is in mathematics:

The expected value is the actual effect * the probability. For example, if you gamble, you can win $100, but the odds are only one in three. You lose $50, but there’s a 2/3 chance. So are you betting or not? So for this historical problem, mathematicians came up with the idea of expected value, that if you end up with a positive expectation, you can bet, and the more times you bet, the more secure you’ll be.

Your expected winnings = 100 * 1/3 = 33.333

The expected value of your loss = -50 * 2/3 = -33.333

In other words, the more you bet, the closer you get to breaking even.

So let’s go back to this one:

The first thing we need to know is does this actually make sense? I usually turn my nose up at topics that have no practical meaning. But this problem, although fancy, but does have a certain practical significance and demand in.

Said there was a company that was hiring. There are two interviewers, Little A and little B. They don’t work together.

Then one day HR recommended 7 resumes to come, hr is very responsible, according to the resume ability value to the order. Such as,2,3,3,3,6,6 [1]

And then two interviewers in their own offices were presented with these seven resumes at the same time, in exactly the same order, and they naturally started with the resumes with the highest competency.

In other words, they start with two resumes with an ability of 6. But they may have taken a repeat. For example, here are two resume candidates whose ability is 6: one is a, the other is B. Interviewer A might look at A for the first time, and interviewer B might look at A for the first time. So they look at repetition. This is a corporate waste of time. Then small A finished a to see the resume of b again, then small B finished a to see the resume of b likewise, this inevitably led to repeat again.

So this is where the real meaning of the problem comes in. Calculate the expected value of this repetition, which is to calculate in advance the cost of wasted time that the company will bear.

In the example we just gave, two interviewers wasted time on two resumes that were worth 6 and cost 2, i.e., they looked at a twice the first time and at B twice the second time. But what’s the probability of that happening? It should be a quarter

Why is it 1/4?

Because there are four cases:

1. Little A looks at A first and then b, and little B looks at A first and then B

Little A looks at A first and then b, and little B looks at B first and then A

Little A looks at B first, then A, then B 4. Little A looks at B first, then A, then B, then A

To sum up: Our expected value for analyzing the first case is: repeat 2 times * 1/4 = 0.5

The expected value of the second case is: repeat 0 times * 1/4 = 0

The expected value of the third case is: repeat 0 times * 1/4 = 0

The expected value of the fourth case is: repeat 2 times * 1/4 = 0.5

The final total result is: 0.5+0+0+0.5 = 1

This is what we expected of the two resumes with an ability of 6.

And then we compute the final expected value of 3 in the power value [1,2,3,3,3,6,6] and then 2, then 1.

And when you add these together, you get the final answer

Now, you get the idea of calculating the expected value of wasted time, right?

So try to understand the final answer?

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)
Copy the code