关于面试:25-匹马-5-条赛道最快需要几轮求出前-3-名

请点赞关注,你的反对对我意义重大。

🔥 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 常识体系。技术和职场问题,请关注公众号 [彭旭锐] 私信我发问。

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据