介绍

总而言之是时候利用暑假锻炼一下算法技术，一提算法面试就面露难色的情形总不能一直持续下去。本栏目面向有一定基础的编程爱好者，每天（如果up不鸽）分享并解析一道LeetCode中高难度题目（通常是hard）。有兴趣的小伙伴可以一起跟着做并且讨论解法。目前的教材是花花酱的Leetcode Problem List【1】.

适合人群：

有一定算法基础，但是还未能顺利通过笔试/面试，总觉得算法题目想不明白的你。

不适合人群：

算法入门级选手（一上来就做难题可能并不合适，建议首先专注简单/中等题目）

非常不适合人群：

算法竞赛选手（这种小儿科的问题完全是在浪费您的时间）

过往题目在这里！

克隆图

题目看这里，lintcode第六百四十五题，medium难度：
https://www.lintcode.com/problem/645/description/

强烈建议读者自己先做（不过真的会有读者吗，笑），有任何问题欢迎在评论区讨论，up看到了会及时回复。做完了欢迎在评论区打卡～

解析

脑筋急转弯型题目的典型，初看就是找唯一一个入度为n-1，出度为0的节点。但是题目的要求是API调用次数尽可能少。基本原理是，如果a不认识b，那么b不可能是名人，因为人人都认识名人。如果a认识b，那么a不可能是名人，因为名人很高冷，谁都不认识。就这样最多O(n)，可以只剩下一个候选人。那么这个候选人有没有可能不是名人呢？当然可能。试想如果所有人都不认识任何人，那么以上算法也剩下一个候选人而且不是名人。所以我们再用其他人测试一下这个候选人。

纯纯的搞笑题目，除了训练一点逻辑之外没有任何价值，最佳解法也完全靠背。不建议去考这种题目的公司，不知道是干啥的。

思考乐园

咩有

音乐推荐

今天回家的时候坐uber，这位司机操着一口半生不熟的英文，完全无法沟通。然后慢悠悠的车和我要赶的公交擦肩而过，换来额外等车半个小时的我。那么，来自阿梓从小就很可爱的一首最近比较烦送给有时候也很烦的你。

教材链接

【1】https://zxi.mytechroad.com/blog/leetcode-problem-categories/