标签: 数学
难度: Medium
有一个无穷大的二维网格图，一开始所有格子都未染色。给你一个正整数 n ，表示你需要执行以下步骤 n 分钟：
下图分别是 1、2、3 分钟后的网格图。
请你返回 n 分钟之后 被染色的格子 数目。
示例 1：
输入：n = 1 输出：1 解释：1 分钟后，只有 1 个蓝色的格子，所以返回 1 。
示例 2：
输入：n = 2 输出：5 解释：2 分钟后，有 4 个在边缘的蓝色格子和 1 个在中间的蓝色格子，所以返回 5 。
提示：
1 <= n <= 105运行时间: 28 ms
内存: 16.1 MB
class Solution:
def coloredCells(self, n: int) -> int:
if n==1:
return 1
else:
return 2*n**2-(2*n-1)
题解中采用的方法是计算经过 n 分钟后被染色的格子数目。思路是基于每分钟格子染色的增长模式。第 1 分钟染色 1 个格子。从第 2 分钟开始，每分钟新增的染色格子数构成了一个增长的正方形边界。具体来说，第 n 分钟，新增染色的格子围绕先前染色的格子形成一个宽度为 2 的环。因此，第 n 分钟的总染色格子数可以通过计算直到第 n 分钟所有新增加的环的格子数之和来得到。这个数目等于中心的 1 个格子加上 n-1 个每层新增的环的格子数。每个环的格子数是前一分钟格子数的周长，即 (2*(n-1) + 2*(n-1)) = 4*(n-1)，加上 4 个角落的格子。通过简化计算，最终得到的公式为 2*n^2-(2*n-1)。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def coloredCells(self, n: int) -> int:
# 当 n 为 1 时, 只有中心的一个格子被染色
if n == 1:
return 1
# 当 n > 1 时, 按照每分钟新增染色的格子数计算总数
else:
return 2 * n ** 2 - (2 * n - 1) # 计算公式，考虑到每一分钟新增的环的格子数
这个公式通过观察每分钟新增染色格子的形状和数量来推导。在第 1 分钟，只有中心的一个格子被染色，总数为 1。从第 2 分钟开始，染色的格子围绕之前所有已染色的格子形成一个宽度为 2 的环状结构。每个环的新增格子数量可以通过计算该环的外围边界格子数得到，即计算环周长。对于第 n 分钟，新增的环的外围边界包括四边各有 n-1 个格子，加上四个角落，总共有 4*(n-1)+4=4n 个格子。因此，从第 2 分钟到第 n 分钟，每分钟新增 4n-4 个格子。累加起来，总染色格子数为 1（第1分钟）加上从第 2 分钟到第 n 分钟的所有新增格子数，即 1 + ∑₂ₙ (4n-4)，这个求和可以通过数学公式计算为 4*(n-1)*n/2 - 4*(n-1) 简化为 2*n^2 - (2*n-1)。
从第二分钟开始，每个新染色的格子都是直接相邻于之前已经染色的格子。这些新增的染色格子会围绕着已染色的区域形成一层外围，这一层恰好是宽度为2的环状结构，因为每个新增的格子可以从四个方向（上、下、左、右）与之前的染色格子相邻。第一层环覆盖了所有直接与中心格子相邻的格子，第二层环则是围绕第一层环再向外扩展一圈。因此，每分钟新增的染色格子实质上是在扩展这个环状结构的宽度，每次增加的宽度为2。
在题解中，`4*(n-1)`代表的是在第 n 分钟时，新增染色格子的数量中，除去四个角落的格子外，环状结构的主体部分的格子数量。具体来说，每一层环由四段组成（上、下、左、右），每段的长度为 n-1，因为每段需要覆盖上一分钟染色区域边缘外的一层。因此，4*(n-1) 表示的是这四段的总长度，即除角落外，新增的环的周长。