1 stair climbing algorithm (Fibonacci sequence)

Suppose you’re climbing stairs. It takes n steps to get to the top.

You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Example 1: Input: 2 Output: 2 Description: There are two ways to climb to the top of the building.

  1. 1 order plus 1 order
  2. 2 order

Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building.

  1. 1 order plus 1 order plus 1 order
  2. 1 order plus 2 order
  3. 2 order plus 1 order

Example 3: Input: 4 Output: 5 Explanation: There are five ways to climb to the top of the building.

  1. 1 order plus 1 order plus 1 order plus 1 order
  2. 1 order plus 1 order plus 2 order
  3. 1 order plus 2 order plus 1 order
  4. 2 order plus 1 order plus 1 order
  5. Two degrees plus two degrees

Obviously, this is a Fibonacci sequence, i.e. a[n] = a[n-2] + a[n-1]. N is the sum of the first two values.

Closure implementation

If you don’t care about space complexity, you can cache each result so that you can skip a lot of computation next time. The specific code is as follows

/** * @param {number} n * @return {number} */ var climbStairs = function(n) { let result = { 0: 1, 1: 1 }; function getData(n){ if(! result[n]){ result[n] = getData(n-1) + getData(n-2); Return result[n]} return getData(n)}Copy the code

The time complexity is O(n), and the space complexity is also O(n). The advantage is that the results can be cached and perform better the next time, making no difference to the need to evaluate only once. Disadvantage is the comparison of memory. The code is as follows:

/** * @param {number} n * @return {number} */ var climbStairs = function(n) { let result = { 0: 1, 1: 1 }; function getData(n){ if(! result[n]){ result[n] = getData(n-1) + getData(n-2); } return result[n] } return getData(n) }Copy the code

Traverse the implementation

/** * @param {number} n * @return {number} */ var climbStairs = function(n){ if (n == 0) return 0; else if (n == 1) return 1; else{ let one = 0, two = 1, i = 0, ret; for(; i < n; i++){ ret = one + two; one = two; two = ret; } return ret; }};Copy the code

The idea is, you take the value of n, you compute the value 0-n starting at 0, and you save the value of n-1 and n-2 for the next calculation. Advantages: time complexity O(n), space complexity O(1), compared with the closure of the idea to save a lot of memory space

2 Hat Color

A, B, C and D are each wearing A hat. There are two black hats and two white hats. D and A, B, C are separated by an opaque wall. A can see the colors of B and C’s hats. B can see the color of C’s hat. As long as you can judge the color of your hat, you can say it immediately. The four of them were silent for a few minutes when one of them said he knew what color his hat was. Who is this man?

The problem solving

B.

Explanation: because there are only 2 black 2 white. So:

  • If a person sees two black hats, he can infer that he is white;
  • If he sees two white hats, he can infer that he is a black hat. \

Because only A can see two people’s hats on the field, and he did not speak, indicating that he saw A black and A white hat.

Because A didn’t speak, B and C knew they were black and white. \

And since B can see C’s hat color, B can know that her own color is the opposite of C’s.

3 Lao Wang sells shoes

Topic:

Lao Wang sells shoes, a pair of purchase price of 30 yuan, Lao Wang sells at a loss, only 20 yuan. A swindler came to buy it and gave Lao Wang a fake 50 yuan note. Lao Wang failed to recognize, and no change, the fake note to the next shop Lao Li changed 50 yuan change, back to find the swindler 30. The next door soon found the problem, take counterfeit money to change, Lao Wang had to change his real money 50 yuan to the next door. How much money did Lao Wang lose?

Answer: 60 yuan.

Explanation: this problem is easy to confuse people, I thought of a way to clear, is to put Lao Wang received and take out the money separate column, finally received and pay the balance, is the correct answer. \

Then the things Lao Wang received were:

  • One counterfeit note (value 0)
  • Here’s Lao Li’s change of 50 yuan

Lao Wang’s contributions include:

  • A pair of shoes. Value of 30 yuan.
  • 30 dollars in change for the crook.
  • A refund of 50 yuan to Lao Li.

So in the end, Lao Wang lost 30 + 30 + 50-50 = 60 yuan.

4 the horse racing

Title: 25 horses, 5 tracks. What is the minimum number of runs required to select the top three fastest runners?

Answer: Seven times.

Explanation: 25 horses are divided into 5 groups, which we call groups A, B, C, D and E. Each of the five groups had a match first. That makes five group winners.

Then the first 5 groups again and again, so to find out the first, we put the first place in the group called group A, the second place in the group called group B, the third place in the group called group C.

And then we need to figure out which one of these guys is faster: A2, A3, B1, B2, C1. So we can find the three fastest horses.

The reason for this comparison is that the top three could be in one of four ways:

  • The top three are all in one group.
  • The top three are in three different groups.
  • The top three, the top two, the third.
  • The top three winners are in one group and the other two are in one group.

Compare A2, A3, B1, B2 and C1 to take all the above into account.

Spin-off question: If we want to find the top five, what is the minimum number of times we have to compete?

5 flip a coin

Title: There are 23 coins on the table,10 of which are heads. Blindfolded (you can’t tell heads from tails), how do you divide into two groups so that there are equal numbers of heads in both groups?

Answer: Divide the coins into two groups, one group of 10 and the other group of 13. Then turn the group of 10 over.

Explanation: Since we were randomly divided into two groups, so in the group of 10 (let’s call it group A), we assume that X coins come up. So we have 10 minus X coins coming down.

The other group (we’ll call it group B), since only 10 of the 23 coins came up, that group had 10-X of them coming up and the rest of them coming down.

We flip group A over, so we switch heads: heads become 10-x, and heads become X.

So group A has 10 minus X heads, the same number of heads as group B.

6 cups

Title: There are three cups with a capacity of 10 litres, 7 litres and 3 litres. Fill 10 liters with water. Q: How can you divide 10 liters of water into two 5 liters without using other measurements?

The answer:

  • Fill a 3-liter cup with water, then transfer the water from the 3-liter cup to the 7-liter cup.
  • Repeat the above steps three times. By the third time, the 7-liter cup was full, leaving 2 liters of water left in the 3-liter cup.
  • At this point pour the 7 liter glass of water back into the 10 liter glass.
  • Pour the remaining 2 litres of water from the 3 litres cup into the 7 litres cup.
  • Finally, fill the 3-liter glass with water, then pour the 3-liter glass into the 7-liter glass.
  • At this point, there are 5 liters of water in each of the 10 liters and 7 liters cups.