LeetCode 题解工作台
构造符合图结构的二维矩阵
给你一个二维整数数组 edges ，它表示一棵 n 个节点的 无向 图，其中 edges[i] = [u i , v i ] 表示节点 u i 和 v i 之间有一条边。 请你构造一个二维矩阵，满足以下条件： 矩阵中每个格子 一一对应 图中 0 到 n - 1 的所有节点。 矩阵中两个格子相邻（ 横…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
class Solution: def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个二维整数数组 edges ，它表示一棵 n 个节点的 无向 图，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 之间有一条边。
请你构造一个二维矩阵，满足以下条件：
- 矩阵中每个格子 一一对应 图中
0到n - 1的所有节点。 - 矩阵中两个格子相邻（横 的或者 竖 的）当且仅当 它们对应的节点在
edges中有边连接。
题目保证 edges 可以构造一个满足上述条件的二维矩阵。
请你返回一个符合上述要求的二维整数数组，如果存在多种答案，返回任意一个。
示例 1：
输入：n = 4, edges = [[0,1],[0,2],[1,3],[2,3]]
输出：[[3,1],[2,0]]
解释：
示例 2：
输入：n = 5, edges = [[0,1],[1,3],[2,3],[2,4]]
输出：[[4,2,3,1,0]]
解释：
示例 3：
输入：n = 9, edges = [[0,1],[0,4],[0,5],[1,7],[2,3],[2,4],[2,5],[3,6],[4,6],[4,7],[6,8],[7,8]]
输出：[[8,6,3],[7,4,2],[1,0,5]]
解释：
提示：
2 <= n <= 5 * 1041 <= edges.length <= 105edges[i] = [ui, vi]0 <= ui < vi < n- 图中的边互不相同。
- 输入保证
edges可以形成一个符合上述条件的二维矩阵。
解题思路
方法一
class Solution:
def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]:
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
deg = [-1] * 5
for x, ys in enumerate(g):
deg[len(ys)] = x
if deg[1] != -1:
row = [deg[1]]
elif deg[4] == -1:
x = deg[2]
for y in g[x]:
if len(g[y]) == 2:
row = [x, y]
break
else:
x = deg[2]
row = [x]
pre = x
x = g[x][0]
while len(g[x]) > 2:
row.append(x)
for y in g[x]:
if y != pre and len(g[y]) < 4:
pre = x
x = y
break
row.append(x)
ans = [row]
vis = [False] * n
for _ in range(n // len(row) - 1):
for x in row:
vis[x] = True
nxt = []
for x in row:
for y in g[x]:
if not vis[y]:
nxt.append(y)
break
ans.append(nxt)
row = nxt
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for clear understanding of graph traversal and grid placement.
- question_mark
Check if the candidate can efficiently use hash tables to manage node relationships.
- question_mark
Assess the ability to handle large graph sizes while maintaining correct grid structure.
常见陷阱
外企场景- error
Overcomplicating the row/column assignment without considering adjacency constraints.
- error
Failing to handle edge cases such as disconnected components or varying node degrees.
- error
Incorrectly managing the grid size, leading to inefficient use of space or incorrect node placement.
进阶变体
外企场景- arrow_right_alt
Changing the graph structure to a directed graph.
- arrow_right_alt
Increasing the number of nodes significantly.
- arrow_right_alt
Requiring more complex relationships between nodes in the grid.