题目描述
给你一个非负整数 N，表示一个 2N x 2N 的网格。你需要用从 0 到 22N - 1 的整数填充网格，使其成为一个 特殊 网格。一个网格当且仅当满足以下 所有 条件时，才能称之为 特殊 网格：
- 右上角象限中的所有数字都小于右下角象限中的所有数字。
- 右下角象限中的所有数字都小于左下角象限中的所有数字。
- 左下角象限中的所有数字都小于左上角象限中的所有数字。
- 每个象限也都是一个特殊网格。
返回一个 2N x 2N 的特殊网格。
注意：任何 1x1 的网格都是特殊网格。
示例 1：
输入： N = 0
输出： [[0]]
解释：
唯一可以放置的数字是 0，并且网格中只有一个位置。
示例 2：
输入： N = 1
输出： [[3,0],[2,1]]
解释：
每个象限的数字如下：
由于 0 < 1 < 2 < 3，该网格满足给定的约束条件。
示例 3：
输入： N = 2
输出： [[15,12,3,0],[14,13,2,1],[11,8,7,4],[10,9,6,5]]
解释：
每个象限的数字如下：
- 右上角：3, 0, 2, 1
- 右下角：7, 4, 6, 5
- 左下角：11, 8, 10, 9
- 左上角：15, 12, 14, 13
max(3, 0, 2, 1) < min(7, 4, 6, 5)max(7, 4, 6, 5) < min(11, 8, 10, 9)max(11, 8, 10, 9) < min(15, 12, 14, 13)
这满足前三个要求。此外，每个象限也是一个特殊网格。因此，这是一个特殊网格。
提示：
解法
方法一：递归分治
特殊网格要求每个象限内的数字满足：右上角 < 右下角 < 左下角 < 左上角，且每个象限也是特殊网格。我们可以用递归分治的方法构造：对于一个边长为 \(k\) 的子网格，按照「右上 → 右下 → 左下 → 左上」的顺序依次递归填充，保证较小数字先填入右上角象限，较大数字后填入左上角象限，从而满足约束条件。
我们从整个网格的右上角 \((0, m - 1)\) 开始，其中 \(m = 2^n\)，边长为 \(m\)。当 \(k = 1\) 时，直接将当前值填入并递增；否则将子网格分为四个象限，递归处理。
时间复杂度 \(O(4^n)\)，空间复杂度 \(O(4^n)\)。其中 \(n\) 是输入参数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution:
def specialGrid(self, n: int) -> List[List[int]]:
def dfs(x: int, y: int, k: int):
if k == 1:
nonlocal val
ans[x][y] = val
val += 1
return
dfs(x, y, k // 2)
dfs(x + k // 2, y, k // 2)
dfs(x + k // 2, y - k // 2, k // 2)
dfs(x, y - k // 2, k // 2)
m = 1 << n
ans = [[0] * m for _ in range(m)]
val = 0
dfs(0, m - 1, m)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
private int[][] ans;
private int val;
public int[][] specialGrid(int n) {
int m = 1 << n;
ans = new int[m][m];
dfs(0, m - 1, m);
return ans;
}
private void dfs(int x, int y, int k) {
if (k == 1) {
ans[x][y] = val++;
return;
}
int h = k / 2;
dfs(x, y, h);
dfs(x + h, y, h);
dfs(x + h, y - h, h);
dfs(x, y - h, h);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public:
vector<vector<int>> specialGrid(int n) {
int m = 1 << n;
vector<vector<int>> ans(m, vector<int>(m));
int val = 0;
auto dfs = [&](this auto&& dfs, int x, int y, int k) -> void {
if (k == 1) {
ans[x][y] = val++;
return;
}
int h = k / 2;
dfs(x, y, h);
dfs(x + h, y, h);
dfs(x + h, y - h, h);
dfs(x, y - h, h);
};
dfs(0, m - 1, m);
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | func specialGrid(n int) [][]int {
m := 1 << n
ans := make([][]int, m)
for i := range ans {
ans[i] = make([]int, m)
}
val := 0
var dfs func(int, int, int)
dfs = func(x, y, k int) {
if k == 1 {
ans[x][y] = val
val++
return
}
h := k / 2
dfs(x, y, h)
dfs(x+h, y, h)
dfs(x+h, y-h, h)
dfs(x, y-h, h)
}
dfs(0, m-1, m)
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | function specialGrid(n: number): number[][] {
const m = 1 << n;
const ans = Array.from({ length: m }, () => Array(m).fill(0));
let val = 0;
const dfs = (x: number, y: number, k: number): void => {
if (k === 1) {
ans[x][y] = val++;
return;
}
const h = k >> 1;
dfs(x, y, h);
dfs(x + h, y, h);
dfs(x + h, y - h, h);
dfs(x, y - h, h);
};
dfs(0, m - 1, m);
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | impl Solution {
pub fn special_grid(n: i32) -> Vec<Vec<i32>> {
fn dfs(x: usize, y: usize, k: usize, ans: &mut Vec<Vec<i32>>, val: &mut i32) {
if k == 1 {
ans[x][y] = *val;
*val += 1;
return;
}
let h = k / 2;
dfs(x, y, h, ans, val);
dfs(x + h, y, h, ans, val);
dfs(x + h, y - h, h, ans, val);
dfs(x, y - h, h, ans, val);
}
let m = 1usize << n;
let mut ans = vec![vec![0; m]; m];
let mut val = 0;
dfs(0, m - 1, m, &mut ans, &mut val);
ans
}
}
|