Medium
题目描述
给定一个非负整数 n，表示一个 2^n × 2^n 的网格。你必须用 0 到 2^(2n) - 1 的整数填充网格，使其成为特殊网格。
一个网格是特殊的，当且仅当它满足以下所有条件：
- 右上象限中的所有数字都小于右下象限中的数字
- 右下象限中的所有数字都小于左下象限中的数字
- 左下象限中的所有数字都小于左上象限中的数字
- 每个象限本身也是一个特殊网格
返回特殊的 2^n × 2^n 网格。
注意：任何 1×1 网格都是特殊的。
示例 1：
输入：n = 0
输出：[[0]]
解释：只能放置数字 0，网格中只有一个可能的位置。
示例 2：
输入：n = 1
输出：[[3,0],[2,1]]
解释：每个象限中的数字是：
- 右上：0
- 右下：1
- 左下：2
- 左上：3
由于 0 < 1 < 2 < 3，满足给定约束。
示例 3：
输入：n = 2
输出：[[15,12,3,0],[14,13,2,1],[11,8,7,4],[10,9,6,5]]
约束条件：
- 0 ≤ n ≤ 10
解题思路
这是一个分治递归问题。关键观察是特殊网格具有自相似性：每个象限本身也必须是特殊网格。
核心思路：
- 基础情况：当 n = 0 时，只有一个 1×1 网格，填入 0
- 递归情况：对于 2^n × 2^n 网格，将其分为 4 个 2^(n-1) × 2^(n-1) 的象限
- 数字分配策略：将 0 到 2^(2n)-1 的数字按象限大小关系分配
- 右上象限：0 到 2^(2n-2)-1
- 右下象限：2^(2n-2) 到 2×2^(2n-2)-1
- 左下象限：2×2^(2n-2) 到 3×2^(2n-2)-1
- 左上象限：3×2^(2n-2) 到 2^(2n)-1
算法步骤：
- 递归生成每个象限的特殊子网格
- 为每个子网格的数字加上相应的偏移量
- 将四个象限组合成最终网格
这样确保了象限间的大小关系：右上 < 右下 < 左下 < 左上，同时每个象限内部也保持特殊性。
时间复杂度为 O(4^n)，因为需要填充 2^(2n) 个位置。
代码实现
class Solution {
public:
vector<vector<int>> specialGrid(int n) {
if (n == 0) {
return {{0}};
}
// 递归生成子网格
vector<vector<int>> subGrid = specialGrid(n - 1);
int subSize = subGrid.size();
int totalSize = subSize * 2;
vector<vector<int>> result(totalSize, vector<int>(totalSize));
// 计算每个象限的偏移量
int quadrantSize = subSize * subSize;
int offsets[4] = {0, quadrantSize, 2 * quadrantSize, 3 * quadrantSize};
// 填充四个象限：右上、右下、左下、左上
for (int i = 0; i < subSize; i++) {
for (int j = 0; j < subSize; j++) {
result[i][j + subSize] = subGrid[i][j] + offsets[0]; // 右上
result[i + subSize][j + subSize] = subGrid[i][j] + offsets[1]; // 右下
result[i + subSize][j] = subGrid[i][j] + offsets[2]; // 左下
result[i][j] = subGrid[i][j] + offsets[3]; // 左上
}
}
return result;
}
};
class Solution:
def specialGrid(self, n: int) -> List[List[int]]:
if n == 0:
return [[0]]
# 递归生成子网格
sub_grid = self.specialGrid(n - 1)
sub_size = len(sub_grid)
total_size = sub_size * 2
result = [[0] * total_size for _ in range(total_size)]
# 计算每个象限的偏移量
quadrant_size = sub_size * sub_size
offsets = [0, quadrant_size, 2 * quadrant_size, 3 * quadrant_size]
# 填充四个象限：右上、右下、左下、左上
for i in range(sub_size):
for j in range(sub_size):
result[i][j + sub_size] = sub_grid[i][j] + offsets[0] # 右上
result[i + sub_size][j + sub_size] = sub_grid[i][j] + offsets[1] # 右下
result[i + sub_size][j] = sub_grid[i][j] + offsets[2] # 左下
result[i][j] = sub_grid[i][j] + offsets[3] # 左上
return result
public class Solution {
public int[][] SpecialGrid(int n) {
if (n == 0) {
return new int[][] { new int[] { 0 } };
}
// 递归生成子网格
int[][] subGrid = SpecialGrid(n - 1);
int subSize = subGrid.Length;
int totalSize = subSize * 2;
int[][] result = new int[totalSize][];
for (int i = 0; i < totalSize; i++) {
result[i] = new int[totalSize];
}
// 计算每个象限的偏移量
int quadrantSize = subSize * subSize;
int[] offsets = {0, quadrantSize, 2 * quadrantSize, 3 * quadrantSize};
// 填充四个象限：右上、右下、左下、左上
for (int i = 0; i < subSize; i++) {
for (int j = 0; j < subSize; j++) {
result[i][j + subSize] = subGrid[i][j] + offsets[0]; // 右上
result[i + subSize][j + subSize] = subGrid[i][j] + offsets[1]; // 右下
result[i + subSize][j] = subGrid[i][j] + offsets[2]; // 左下
result[i][j] = subGrid[i][j] + offsets[3]; // 左上
}
}
return result;
}
}
var specialGrid = function(n) {
if (n === 0) return [[0]];
const size = 1 << n; // 2^n
const grid = Array(size * 2).fill().map(() => Array(size * 2).fill(0));
function fill(row, col, size, start) {
if (size === 1) {
grid[row][col] = start;
return;
}
const half = size / 2;
const quadSize = half * half;
// Top-right (smallest)
fill(row, col + half, half, start);
// Bottom-right
fill(row + half, col + half, half, start + quadSize);
// Bottom-left
fill(row + half, col, half, start + 2 * quadSize);
// Top-left (largest)
fill(row, col, half, start + 3 * quadSize);
}
fill(0, 0, size * 2, 0);
return grid;
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(4^n) | 需要填充 2^(2n) 个网格位置，每次递归处理 4 个象限 |
| 空间复杂度 | O(4^n) | 存储最终网格需要 2^(2n) 空间，递归深度为 n |