骨骼电面1题

jtzgz 发表于 2020/06/10 15:08:37
也可以这样想呢。 对的。 就是如何把neighbor结构，先parse成tree结构。

parse 成 tree 的话也只用 O（n）就可以了，然后在 tree 上 dp 就可以O（n）做出来了。

jtzgz 发表于 2020-6-10 15:07
感觉，cover了所有的edge，就等于vertex吧

cover所有edge等于cover所有vertex，但是cover所有vertex不等于cover所有edge。。。

这题可以用union find来解吗？假设一开始所有等都是亮的 count = N 然后以任意一个点来做bfs，每次和neighbour union 就N-- 直到所有房间都被访问过，是不是最后count就是要找的解？

bjtuandy66 发表于 2020-6-13 09:26
这题可以用union find来解吗？假设一开始所有等都是亮的 count = N 然后以任意一个点来做bfs，每次和neighb ...

不好意思 审题错误，:(

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

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

jtzgz 发表于 2020-6-9 09:56
不是的。从一个room开始，然后，点亮，记录下来。遇到了全亮，更新min。 熄灭。下一个room，点亮。如此。 ...

你这不是 greedy 吧 ...

jtzgz 发表于 2020-6-10 15:08
也可以这样想呢。 对的。 就是如何把neighbor结构，先parse成tree结构。

A-B-C-A  只有一条 path, 但这肯定不是 tree 吧

amgfan 发表于 2020-6-13 16:38
A-B-C-A  只有一条 path, 但这肯定不是 tree 吧

A到C这不是有两条path么,我觉得这个题就是tree

yourdoraemon 发表于 2020-6-14 02:30
A到C这不是有两条path么,我觉得这个题就是tree

一条啊哥,  一个环

amgfan 发表于 2020-6-14 02:34
一条啊哥,  一个环

好吧, 这个得看有没有环了, 没有环 就转成 leetcode 那道tree题了.

有环的话..就不知道怎么做了......