[leetcode/lintcode 题解] 算法面试真题详解:识别名人

简介: [leetcode/lintcode 题解] 算法面试真题详解:识别名人

描述
假设你和 n 个人在一个聚会中(标记为 0 到 n - 1),其中可能存在一个名人。名人的定义是所有其他 n - 1 人都认识他/她,但他/她不知道任何一个。
现在你想要找出这个名人是谁或者验证这个名人不存在。你唯一可以做的事情就是提出如下问题:“你好,A,你认识B吗?” 来获取A是否认识B。您需要通过询问尽可能少的问题(以渐近的意义)来找出名人是谁(或验证其不存在)。
你得到一个辅助函数 bool know(a,b),它会告诉你A是否知道B.实现一个函数 int findCelebrity(n),你的函数应该使 knows 的调用次数最少。
如果在这个聚会中有名人, 那么有且只有一个。如果有名人在聚会中则返回名人的标签,如果没有名人,返回 -1。

在线评测地址:领扣题库官网

样例1
输入:
2 // 接下来n*(n-1)行
0 knows 1
1 does not know 0
输出: 1
解释:
所有人都认识1,而且1不认识其他人。
样例2
输入:
3 // 接下来n*(n-1)行
0 does not know 1
0 does not know 2
1 knows 0
1 does not know 2
2 knows 0
2 knows 1
输出:0
解释:
所有人都认识0,而且0不认识其他人。
0不认识1,同时1认识0。
2认识所有人,但是1不认识2。

解题思路
首先loop一遍找到一个人i使得对于所有j(j>=i)都不认识i。 然后再loop一遍判断是否有人不认识i或者i认识某个人。

源代码
"""
The knows API is already defined for you.
@param a, person a
@param b, person b
@return a boolean, whether a knows b
you can call Celebrity.knows(a, b)
"""


class Solution:
    # @param {int} n a party with n people
    # @return {int} the celebrity's label or -1
    def findCelebrity(self, n):
        celeb = 0
        
        for i in range(1, n):
            if Celebrity.knows(celeb, i):
                celeb = i
        
        # Check if the final candicate is the celebrity
        for i in range(n):
            if celeb != i and Celebrity.knows(celeb, i):
                return -1
            if celeb != i and not Celebrity.knows(i, celeb):
                return -1
        
        return celeb

更多题解参考:九章官网solution

相关文章
|
存储 人工智能 算法
从零掌握贪心算法Java版:LeetCode 10题实战解析(上)
在算法世界里,有一种思想如同生活中的"见好就收"——每次做出当前看来最优的选择,寄希望于通过局部最优达成全局最优。这种思想就是贪心算法,它以其简洁高效的特点,成为解决最优问题的利器。今天我们就来系统学习贪心算法的核心思想,并通过10道LeetCode经典题目实战演练,带你掌握这种"步步为营"的解题思维。
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
316 0
|
算法
面试场景题:如何设计一个抢红包随机算法
本文详细解析了抢红包随机算法的设计与实现,涵盖三种解法:随机分配法、二倍均值法和线段切割法。随机分配法通过逐次随机分配金额确保总额不变,但易导致两极分化;二倍均值法优化了金额分布,使每次抢到的金额更均衡;线段切割法则将总金额视为线段,通过随机切割点生成子金额,手气最佳金额可能更高。代码示例清晰,结果对比直观,为面试中类似算法题提供了全面思路。
2449 16
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
564 4
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
448 2
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
2865 2
|
机器学习/深度学习 JavaScript 算法
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
640 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行

热门文章

最新文章