Medium
题目描述
存在一个无限大的二维网格，网格中的每个单元格都是未着色的。给定一个正整数 n，表示你必须在 n 分钟内执行以下操作：
- 在第一分钟，将任意一个单元格涂成蓝色。
- 此后每分钟，将所有与蓝色单元格相邻的未着色单元格涂成蓝色。
下图展示了第 1、2、3 分钟后网格的状态。
返回 n 分钟结束时有色格子的数量。
示例 1：
输入：n = 1
输出：1
解释：1 分钟后，只有 1 个蓝色单元格，所以返回 1。
示例 2：
输入：n = 2
输出：5
解释：2 分钟后，边界上有 4 个有色单元格，中心有 1 个，所以返回 5。
约束条件：
1 <= n <= 10^5
提示：
- 推导有色格子总数与经过时间（分钟）之间的数学关系。
解题思路
解题思路
这是一个数学问题，我们需要找到有色格子数量与时间 n 的关系。
观察扩散模式：
- 第1分钟：只有1个格子（中心）
- 第2分钟：中心格子的4个相邻格子也被涂色，总共5个
- 第3分钟：继续向外扩散一圈，总共13个
我们可以发现，每分钟形成的图案是一个菱形（钻石形状），在坐标系中可以用曼哈顿距离来描述。
关键洞察：
- 第 n 分钟时，所有与初始格子曼哈顿距离 ≤ n-1 的格子都会被涂色
- 曼哈顿距离为 d 的格子数量为 4d（d > 0），距离为 0 的只有 1 个
推导公式： 总格子数 = 1 + 4×1 + 4×2 + … + 4×(n-1) = 1 + 4×(1 + 2 + … + (n-1)) = 1 + 4×((n-1)×n/2) = 1 + 2n(n-1) = 2n² - 2n + 1
验证：
- n=1: 2×1² - 2×1 + 1 = 1 ✓
- n=2: 2×4 - 4 + 1 = 5 ✓
- n=3: 2×9 - 6 + 1 = 13 ✓
时间复杂度：O(1)，空间复杂度：O(1)
代码实现
class Solution {
public:
long long coloredCells(int n) {
return 2LL * n * n - 2LL * n + 1;
}
};
class Solution:
def coloredCells(self, n: int) -> int:
return 2 * n * n - 2 * n + 1
public class Solution {
public long ColoredCells(int n) {
return 2L * n * n - 2L * n + 1;
}
}
/**
* @param {number} n
* @return {number}
*/
var coloredCells = function(n) {
return 2 * n * n - 2 * n + 1;
};
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(1) |
| 空间复杂度 | O(1) |