G家现场面

catyoyo

求问生成迷宫的题目的思路？

candysonya

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

catyoyo

sssssC 发表于 2019-9-12 05:59
我感觉可以把每个input区间的start和end放到一个priorityQueue 然后maintain一个Map或者啥用来记录当前所 ...

这个方法挺好的，跟天际线问题一样，event driven simulatioin。

catyoyo

jemi 发表于 2019-9-12 07:02
给一个树，每个节点对应一个值，表示雨点从它的父节点走到它的时间，然后求雨点先经过根节点，能够把整棵树 ...

对于树，由于到每个节点的路径是唯一的，只需bfs即可，找出最长路径。如果是图，那有多个路径可走，需要找到最短的路径，可用dijkstra做。

catyoyo

candysonya 发表于 2019-9-13 12:36
合法：对于每个索引j，B[j] < n - j

面试官给了“合法”的定义吗？还是需要自己和面试官讨论合法的定义。

candysonya

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

candysonya

catyoyo 发表于 2019-9-14 13:32
面试官给了“合法”的定义吗？还是需要自己和面试官讨论合法的定义。

面试官没有给合法的定义，只是说合法，然后我直接把它理解成能够找到一个对应的A就叫合法。或许讨论一下什么是合法更好。

catyoyo

candysonya 发表于 2019-9-14 13:35
这是个成熟的题、参考：

https://zhuanlan.zhihu.com/p/27381213

这题如果没有什么要求的话，可以想出很多不同的解吧。不知道这种题目要考察什么方面。

sssssC

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

KuanCNTF

sssssC 发表于 2019-9-14 13:57
我一开始也觉得set存label就好可是再仔细想想如果不用map存有可能出现前面有两个addLine都有label ‘a ...

有道理，那就要mutliset存