大头钉新鲜店面

面的是 machine learning engineer, 不是力扣原题,


给定一些列 boards, 每个包含一些 pins,
Board1: pin1, pin2, pin3
Board2: pin2, pin4, pin5
Two p

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

始，遍历它的连通分量，检查是否能够到达 **pin2**。
.--follow-up: 直接用 BFS, 相当于shortest path 问题.


刚面完, 还在等待结果. 求大米

不知道如何降低帖子积分, 直接回复这里:

给定一些列 boards, 每个包含一些 pins,
Board1: pin1, pin2, pin3
Board2: pin2, pin4, pin5
Two pins are considered related if they can be connected through one or more boards.
问题1： 给定两个pin， 判断他俩是否connected, 注意可以跨多个 board 连接。
Follow up: 算两个pin之间经过几个board才连起来。
这个问题可以看作一个图的连通性问题。每个 pin 是一个节点，每个 board 定义了一组完全连接的节点（即一个完全图）。我们需要判断两个 pin 是否在同一个连通分量中。 connected component.
邻接表 + 深度优先搜索 (DFS)
1. **构建邻接表**：
* 每个 **pin** 是一个节点，用字典存储每个 **pin** 的直接连接节点。
2. **DFS/BFS 遍历**：
* 从 **pin1** 开始，遍历它的连通分量，检查是否能够到达 **pin2**。
follow-up: 直接用 BFS, 相当于shortest path 问题.
刚面完, 还在等待结果. 求大米

没明白这个board和board之间是如何接触呢？是类似于华容道的样子横竖层次不齐？

匿名用户 发表于 2025-2-15 14:26
没明白这个board和board之间是如何接触呢？是类似于华容道的样子横竖层次不齐？

每个board 包含了 a list of pins, 比如 board1 中包含 pin2, 然后board2 中同样包含 pin2, 那么 可以把board1 和 board2 视为 connected via pin2. 可以把每个pin 想象为 graph 中 的 node, 每个 board 是 connected component.

匿名用户 发表于 2025-02-15 15:04:59
每个board 包含了 a list of pins, 比如 board1 中包含 pin2, 然后board2 中同样包含 pin2, 那么 可以把board

嗯嗯 明白 其实board就是edge