介紹

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

適合人群：

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

不適合人群：

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

非常不適合人群：

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

過往題目在這里！

不鄰接植花

題目看這里，lintcode第1042題，medium難度：
https://leetcode.com/problems/flower-planting-with-no-adjacent/

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

解析

這破題目真是缺了大德，我最討厭這種腦筋急轉(zhuǎn)彎。網(wǎng)上答案都說能給一個節(jié)點上色就盡量上色，但是為什么這樣實際上沒人說清楚，這個可太致命了。搞不清楚就變成p用沒有的背題，所以我們一起來看看。

貪婪算法看起來很美好，但是讓人不得不疑慮的一點在于，這樣會不會產(chǎn)生錯誤？比如當前節(jié)點A連接節(jié)點B，C，D。B和C已經(jīng)上色，分別是1和2。A正待上色，D未上色。這種情況下，如果D連接三個已經(jīng)上色的節(jié)點，而且D將來要上的顏色是4，那么A看起來有2和4兩個選擇，實際上只有2一個選擇。如果貪婪算法給A選了4就和D將來的顏色沖突。

我是被這個想法卡住了，但是ChatGPT一句無心的話提醒了我，以上的情況永遠不可能發(fā)生。因為里面是有悖論的。悖論在哪呢？提示：A節(jié)點也是連接D節(jié)點的，而且它在我們考慮問題的時候還沒有上色。

思考樂園

想想看上面場景里的悖論在哪？

音樂推薦

懶得做飯于是點了外賣，但是外賣也不好吃，下次不點這家了。總而言之，今天推薦的是零一_Uri的Catallena。

教材鏈接

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