LeetCode C++ 1688. Count of Matches in Tournament【Math】简单
发布日期:2021-07-01 02:58:22
浏览次数:2
分类:技术文章
本文共 1937 字,大约阅读时间需要 6 分钟。
You are given an integer n
, the number of teams in a tournament that has strange rules:
- If the current number of teams is even, each team gets paired with another team. A total of
n / 2
matches are played, andn / 2
teams advance to the next round. - If the current number of teams is odd, one team randomly advances in the tournament, and the rest gets paired. A total of
(n - 1) / 2
matches are played, and(n - 1) / 2 + 1
teams advance to the next round.
Return the number of matches played in the tournament until a winner is decided.
Example 1:
Input: n = 7Output: 6Explanation: Details of the tournament: - 1st Round: Teams = 7, Matches = 3, and 4 teams advance.- 2nd Round: Teams = 4, Matches = 2, and 2 teams advance.- 3rd Round: Teams = 2, Matches = 1, and 1 team is declared the winner.Total number of matches = 3 + 2 + 1 = 6.
Example 2:
Input: n = 14Output: 13Explanation: Details of the tournament:- 1st Round: Teams = 14, Matches = 7, and 7 teams advance.- 2nd Round: Teams = 7, Matches = 3, and 4 teams advance.- 3rd Round: Teams = 4, Matches = 2, and 2 teams advance.- 4th Round: Teams = 2, Matches = 1, and 1 team is declared the winner.Total number of matches = 7 + 3 + 2 + 1 = 13.
Constraints: 1 <= n <= 200
题意:一个整数 n
表示比赛中的队伍数。返回在比赛中进行的配对次数,直到决出获胜队伍为止。
解法1 遵循题意
class Solution { public: int numberOfMatches(int n) { int ans = 0; while (n > 1) { //n<=1时无需比赛 if (n & 1) { ans += (n - 1) / 2; n = (n - 1) / 2 + 1; } //奇数,加上(n-1)/2次配对次数,剩下(n-1)/2+1队伍 else { ans += n / 2; n /= 2; } //偶数,加上n/2次配对次数,剩下n/2支队伍 } return ans; }};
运行效率如下:
执行用时:0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗:6.2 MB, 在所有 C++ 提交中击败了100.00% 的用户
解法2 数学规律
每一轮中会进行多次配对,每次配对进行比赛,都会淘汰一支队伍。直到决出获胜队伍。因此最终只进行 n - 1
次配对:
class Solution { public: int numberOfMatches(int n) { return n - 1; }};
运行效率如下:
执行用时:0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗:6.2 MB, 在所有 C++ 提交中击败了100.00% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/111405870 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月27日 00时10分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Linux png转jpg (convert命令)
2019-04-30
vscode git
2019-04-30
CodeForces - 456C Boredom (dp)
2019-04-30
CodeForces - 1042B Vitamins (思维)
2019-04-30
ACM 2013 长沙区域赛 Collision (几何)
2019-04-30
ACM 2014 鞍山区域赛 E - Hatsune Miku (dp)
2019-04-30
反向传播&梯度下降 的直观理解程序(numpy)
2019-04-30
ACM 2017 北京区域赛 J-Pangu and Stones(区间dp)
2019-04-30
java常用类 String面试题
2019-04-30
四线触摸屏原理
2019-04-30
C/C++如何返回一个数组/指针
2019-04-30
腾讯AI语音识别API踩坑记录
2019-04-30
java.net.BindException: 无法指定被请求的地址
2019-05-01
svn服务器安装
2019-05-01
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01
未来已至,5G加持下的云游戏将走向何方?
2019-05-01
计算机网络 —— 网络层 1.
2019-05-01
Android 之 ContentProvider 与 ContentResolver
2019-05-01
【接口自动化】
2019-05-01