介绍

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

适合人群：

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

不适合人群：

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

非常不适合人群：

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

过往题目在这里！

不邻接植花

题目看这里，lintcode第1042题，medium难度：
https://leetcode.com/problems/flower-planting-with-no-adjacent/

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

解析

这破题目真是缺了大德，我最讨厌这种脑筋急转弯。网上答案都说能给一个节点上色就尽量上色，但是为什么这样实际上没人说清楚，这个可太致命了。搞不清楚就变成p用没有的背题，所以我们一起来看看。

贪婪算法看起来很美好，但是让人不得不疑虑的一点在于，这样会不会产生错误？比如当前节点A连接节点B，C，D。B和C已经上色，分别是1和2。A正待上色，D未上色。这种情况下，如果D连接三个已经上色的节点，而且D将来要上的颜色是4，那么A看起来有2和4两个选择，实际上只有2一个选择。如果贪婪算法给A选了4就和D将来的颜色冲突。

我是被这个想法卡住了，但是ChatGPT一句无心的话提醒了我，以上的情况永远不可能发生。因为里面是有悖论的。悖论在哪呢？提示：A节点也是连接D节点的，而且它在我们考虑问题的时候还没有上色。

思考乐园

想想看上面场景里的悖论在哪？

音乐推荐

懒得做饭于是点了外卖，但是外卖也不好吃，下次不点这家了。总而言之，今天推荐的是零一_Uri的Catallena。

教材链接

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