问题链接:https://leetcode-cn.com/problems/grid-illumination
注:仅记录我自己的错误思路并分析其原因,不直接提供解题思路
开始
看到这道题的5分钟不到,很快啊,我就有了大致的思路。
由于通过矩阵模拟必定会超时,所以我想到了用映射的方法表示对角线亮灯的范围,只不过这个映射方式比较蠢。
怎么个蠢法呢?别人都是映射到x轴,我是映射到网格的边际上。简单画一下,大概是下面这种情况。

随手画的图
显然,映射点时还需要考虑两种不同的情况。相比直接映射到x轴上而言,做无用功。
误区
在有了上述的思路之后就开始做题了。但在让代码跑起来这件事上就不是很顺利,主要是写一半代码发现一部分写复杂了,优化的时候没有考虑到所有情况,不过这并不是本次的主要问题。而主要问题主要是以下两个:
- 最初映射点的思路需要分类讨论,果然在这个地方出了些差错,在检查两遍后,发现了可以直接映射到x轴的方法。说明这个方法还是不难想到的。
- 因为脑内将“对角线”抽象成了“映射点”,所以我将它们放进了同一个稀疏矩阵中存储,忽略了“主对角线”和“反对角线”的所表示意义的差异(即一个灯泡在主对角线上的映射点和待检测网格在反对角线的映射点相同,但该灯泡肯定不能通过对角线的方式照亮该区域)。
论断
对上述误区提出改进方向,编号一一对应
- 在有可行思路时,可进一步推敲,看是否可以简化某些步骤。也要敢于做肯定推断。(我在实现思路时就常常不是很肯定某些步骤是否一定正确,只会举例论证,而且例子也不够丰富)
- 在抽象一些规则时,需要考虑他们之间是否完全等价,最好是注释上该抽象到底代表着什么。