介紹

總而言之是時候利用暑假鍛煉一下算法技術，一提算法面試就面露難色的情形總不能一直持續(xù)下去。本欄目面向有一定基礎的編程愛好者，每天（如果up不鴿）分享并解析一道LeetCode中高難度題目（通常是hard）。有興趣的小伙伴可以一起跟著做并且討論解法。目前的教材是花花醬的Leetcode Problem List【1】.

適合人群：

有一定算法基礎，但是還未能順利通過筆試/面試，總覺得算法題目想不明白的你。

不適合人群：

算法入門級選手（一上來就做難題可能并不合適，建議首先專注簡單/中等題目）

非常不適合人群：

算法競賽選手（這種小兒科的問題完全是在浪費您的時間）

過往題目在這里！

克隆圖

題目看這里，lintcode第六百四十五題，medium難度：
https://www.lintcode.com/problem/645/description/

強烈建議讀者自己先做（不過真的會有讀者嗎，笑），有任何問題歡迎在評論區(qū)討論，up看到了會及時回復。做完了歡迎在評論區(qū)打卡～

解析

腦筋急轉彎型題目的典型，初看就是找唯一一個入度為n-1，出度為0的節(jié)點。但是題目的要求是API調用次數(shù)盡可能少?；驹硎牵绻鸻不認識b，那么b不可能是名人，因為人人都認識名人。如果a認識b，那么a不可能是名人，因為名人很高冷，誰都不認識。就這樣最多O(n)，可以只剩下一個候選人。那么這個候選人有沒有可能不是名人呢？當然可能。試想如果所有人都不認識任何人，那么以上算法也剩下一個候選人而且不是名人。所以我們再用其他人測試一下這個候選人。

純純的搞笑題目，除了訓練一點邏輯之外沒有任何價值，最佳解法也完全靠背。不建議去考這種題目的公司，不知道是干啥的。

思考樂園

咩有

音樂推薦

今天回家的時候坐uber，這位司機操著一口半生不熟的英文，完全無法溝通。然后慢悠悠的車和我要趕的公交擦肩而過，換來額外等車半個小時的我。那么，來自阿梓從小就很可愛的一首最近比較煩送給有時候也很煩的你。

教材鏈接

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