苹果icloud-mail电面

题目是

N个  鸽子  排成一排
N个  洞      排成一排
每一个  鸽子  分配一个  洞

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

构来缩短runtime，楼主并没有搞出来，估计是挂了

假设每条线起点是s，终点是e。如果s1e1和s2e2有交点，应该满足s1<s2&&e1>e2，或者是s1>s2&&e1<e2。按照s排好序，然后scan。当前扫描到的s肯定比之前所有见过的s都大，就只需要求当前遇到的e比之前遇到的多少个e要小，就是多少个交点。这一步用balanced tree什么的应该可以。这样可以么

lpj0522 发表于 2018-8-7 08:10
假设每条线起点是s，终点是e。如果s1e1和s2e2有交点，应该满足s1e2，或者是s1&gt;s2&amp;&amp;e1

就感觉像李扣 伞要无

是一一对应的吗？同一个洞会不会有两个鸽子

pandami 发表于 2018-8-4 02:30
是一一对应的吗？同一个洞会不会有两个鸽子

是一一对应的

union find,完后数多少个parent不是自己的节点

就一道题么？

ld_xixi 发表于 2018-8-7 06:49
union find,完后数多少个parent不是自己的节点

比如说N=3，index为0   1   2，0->2，1->0，2->1，这样的对应关系下来，用union find得出的结果是3？但实际结果是2

ld_xixi 发表于 2018-8-7 06:50
就一道题么？

楼主做得慢，只有一道题

JOEY_YUAN 发表于 2018-8-7 07:03
比如说N=3，index为0   1   2，0->2，1->0，2->1，这样的对应关系下来，用union find得出的结果是3？但实 ...

这个题我觉得题意我没有太理解， 这个连线怎么连呢？ 是N * N的2D矩阵那样连么？

ld_xixi 发表于 2018-8-7 07:34
这个题我觉得题意我没有太理解， 这个连线怎么连呢？ 是N * N的2D矩阵那样连么？

是N×2的矩阵，可以想象第一行N个点，第二行N个点，第一行的点跟第二行的点之间连线