共计 1399 个字符，预计需要花费 4 分钟才能阅读完成。
请点赞关注，你的反对对我意义重大。
🔥 Hi，我是小彭。本文已收录到 GitHub · AndroidFamily 中。这里有 Android 进阶成长常识体系，有气味相投的敌人，关注公众号 [彭旭锐] 带你建设外围竞争力。
前言
- 在计算机面试中，逻辑类题目是规模以上互联网公司的必考题。因为题目花样百出，筹备难度较大，题海战术可能不是举荐的做法。
- 在这个系列里，我将精选十道十分经典的逻辑题，心愿能帮忙你找到解题思路 / 技巧。如果能帮上忙，请务必点赞加关注，这真的对我十分重要。
系列文章
- 《逻辑 |“我晓得你不晓得”！》
- 《逻辑 | 德·梅齐利亚克砝码！》
- 《逻辑 | 天黑请闭眼！）》
- 《逻辑 | 赛马！》
1. 题目形容
给定 25 匹马与 5 条赛道，一个赛道只能包容一匹马，每轮较量只能失去 5 匹马之间的快慢水平，而不是速度，求决胜 1，2，3 名至多多少轮。
2. 解题要害
2.1 分治思维
欲求得 25 匹马中的前三名，能够先求得较小规模问题中的前三名，再合并小规模问题的解得出最终解。
2.2 代表元法
在并查集（一种数据结构）中，会应用根节点来代表一个汇合，这种办法叫做代表元法。咱们能够借鉴这种“代表元”的思维，让一组马中跑的最快的一匹来代表整组马。举个例子，给定一组赛马 $A_1,A_2,A_3,A_4,A_5$，$A_1$ 为这组马中冠军马，若有 $B_1>A_1$，则天然有 $B_1>A$（即：如果 $B_1$ 比 $A$ 组中跑的最快的一匹马还快，天然能够得出 $B_1$ 比 $A$ 组所有马都快的论断）。
提醒： 若不理解并查集，请务必浏览我之前写过的一篇文章：《数据结构 | 并查集 & 联结 – 查找算法》
3. 解决问题
了解了分治和代表元后，当初能够说问题的解法了，一共分为 2 个回合来解决：
3.1 第一回合
首先，咱们将 25 匹赛马分为 5 组，让每组马进行组内较量，失去组内排名，假如后果为 $A_1>A_2>A_3>A_4>A_5$（此时进行了 5 轮较量）。因为组内排名第四与第五名不可能竞争全场前三名，所以排除每一组的第四与第五名。
$A 组：\{A_1,A_2,A_3,A_4,A_5\}$
$B 组：\{B_1,B_2,B_3,B_4,B_5\}$
$C 组：\{C_1,C_2,C_3,C_4,C_5\}$
$D 组：\{D_1,D_2,D_3,D_4,D_5\}$
$E 组：\{E_1,E_2,E_3,E_4,E_5\}$
第一回合
3.2 第二回合
其次，每一组跑得最快的一匹马作为代表元参加一轮“代表赛”，假如比赛结果是：$[A_1>B_1>C_1>D_1>E_1]$，由此能够排除失去竞争资格的赛马：
- $A_1$ 是代表赛中最快的，所以 $A_1$ 肯定是全场第一名；
- $B_1$ 是代表赛中的第二名，最快状况下 $B_1$ 同时也是全场的第二名，则 $B_3$ 后面还有 $B_2$，所以 $B_3$ 失去竞争前三名的资格；
- $C_1$ 是代表赛中的第三名，最快状况下 $C_1$ 同时也是全场的第三名，则 ${C_2、C_3}$ 失去前三名的竞争资格；
- $D_1$ 和 $D_1$ 是代表赛的四五名，阐明 D 组和 E 组都失去了前三名的竞争资格；
第二回合
3.3 第三回合
此时，残余的未知程序的赛马正好有 5 匹，加赛一轮就能够得出第二名和第三名的归属。三个回合总共进行了 7 轮较量，故答案就是 7。
$\{A_2,A_3\}$
$\{B_1,B_2\}$
$\{C_1\}$
论毕。
我是小彭，带你构建 Android 常识体系。技术和职场问题，请关注公众号 [彭旭锐] 私信我发问。
