This is the ninth day of my participation in the First Challenge 2022
preface
Some people love each other, some people drive at night to watch the sea, some people can not solve the first question of Leetcode, so it can be seen that the question of Leetcode still has weight. Today we’re going to meet them
Subject to introduce
You are given an integer n for the number of teams in the game. The competition follows a unique format:
If the current number of teams is even, each team will be paired with another team. A total of N / 2 matches are played and n / 2 teams are generated to advance to the next round. If the current number of teams is odd, a random round will be played and one team will advance, and the remaining teams will be paired. A total of (n-1) / 2 matches are played and (n-1) / 2 + 1 teams are produced to advance to the next round. Returns the number of pairings made during the tournament until the winning team is determined. Example 1:
Input: n = 7 Output: 6 Explanation: Match Details: - Round 1: Number of teams = 7, Number of matches = 3, 4 teams advance. - Round 2: Number of teams = 4, number of matches = 2, 2 teams advance. - Round 3: Number of teams = 2, number of matches = 1, 1 winning team will be determined. Total number of pairs = 3 + 2 + 1 = 6Copy the code
Example 2:
Input: n = 14 Output: 13 Explanation: Match Details: - Round 1: Number of teams = 14, number of matches = 7, 7 teams advance. - Round 2: Number of teams = 7, number of matches = 3, 4 teams advance. - Round 3: Number of teams = 4, number of matches = 2, 2 teams advance. - Round 4: Number of teams = 2, number of matches = 1, 1 winning team will be determined. Total number of pairs = 7 + 3 + 2 + 1 = 13Copy the code
Tip:
1 <= n <= 200
Copy the code
mathematics
Train of thought
- According to the title, there are two teams taking part in the competition
- In every match one team will advance and one team will lose
- In the end, only one team will win
- Suppose you have
Four teams
So the number of games isFirst couple and second team
Play a game, the winning team andThe third team
Play the game, the winning team of the second match andThe third team
To compete for the championship, sofour
The teams compete altogether3 games
- So,
n
One team, you need to playn-1
field
Method a
var numberOfMatches = function (n) {
let res = 0
while (n > 1) {
res++
n--
}
return res
};
Copy the code
Method 2
var numberOfMatches = function (n) {
return n - 1
};
Copy the code
simulation
instructions
- Simulate a real situation
- Because we are not sure the number of cycles all use
The while loop
- Each cycle (
The game
),- If the teams are
An even number
, then proceedn/2
Time matching - If the team is
An odd number
“, then one of the teams will be empty, and then the number of matches will need to be(n-1)/2
Time matching - And the number of teams left is
(n-1)/2
Add to that the empty teams, and the true remaining teams are(n-1)/2+1
- If the teams are
solution
var numberOfMatches = function (n) { let res = 0 while (n > 1) { if (n % 2 === 0) { n /= 2 res += n } else { res += (n - 1) / 2 n = (n - 1) / 2 + 1 } } return res };Copy the code
Write in the last
- I hope you find it rewarding