LeetCode 题解工作台
填充特殊网格
给你一个非负整数 N ，表示一个 2 N x 2 N 的网格。你需要用从 0 到 2 2N - 1 的整数填充网格，使其成为一个 特殊 网格。一个网格当且仅当满足以下 所有 条件时，才能称之为 特殊 网格： 右上角象限中的所有数字都小于右下角象限中的所有数字。 右下角象限中的所有数字都小于左下角象限…
3
题型
0
代码语言
3
相关题
当前训练重点
中等 · 数组·结合·divide·conquer
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·divide·conquer 题型思路
题目描述
给你一个非负整数 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
由于 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)
这满足前三个要求。此外，每个象限也是一个特殊网格。因此，这是一个特殊网格。
提示：
0 <= N <= 10
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space depend on the recursion depth, which is O(n). Each level handles four quadrants of half size, resulting in O(4^n) operations for a full 2^n x 2^n grid. Space grows with recursion stack and storage for subgrids. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a divide-and-conquer approach instead of iterative filling.
- question_mark
Expect careful tracking of integer ranges for each quadrant.
- question_mark
Recursive correctness and merging order are key to a valid solution.
常见陷阱
外企场景- error
Failing to properly offset integer ranges leads to duplicate numbers.
- error
Incorrect quadrant merging breaks the special property.
- error
Attempting an iterative approach without recursion may cause confusion and mistakes.
进阶变体
外企场景- arrow_right_alt
Fill a 2^n x 2^n grid in spiral order while maintaining uniqueness.
- arrow_right_alt
Modify the grid so each quadrant sums to the same total.
- arrow_right_alt
Generate a special grid with different base patterns for n=0 instead of starting at 0.