骨骼电面1题

旧未来 发表于 2020-6-9 13:45
对 所以我那里特别写了[1,x,y,z..]就是选择1你能获得的所有数字，包括自己
但是总感觉2^n这样的算法不是 ...

这就是我为什么发这个帖子啊。。。

这个问题有点像NP-hard

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

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

既然无环，能不能随意选一个点作为root，变成tree，然后从leaf + 1层开始，隔层点亮， 对于每个node，可以dp它的子树，几种状态 （child1是否点亮 * child2是否点亮 * ... -> cur是否点亮）下的min

感谢楼主分享，挺有意思的题目

yidisanfenmu 发表于 2020-6-9 19:09
找有几个连通分量，不就是最终答案了嘛？利用path信息 把隐式图建好。当然楼主 的答案 也不错.

清详细讲一讲？

457368837 发表于 2020-6-9 16:10
既然无环，能不能随意选一个点作为root，变成tree，然后从leaf + 1层开始，隔层点亮， 对于每个node，可以d ...

camera就是这样的题

yunsan9999 发表于 2020-6-9 20:01
感谢楼主分享，挺有意思的题目

幸亏我作出来了greedy。不然电面都要帆船

vinf 发表于 2020-6-9 15:48
这个题是一般图最小点覆盖的问题，是NPC问题，差不多就只考虑搜索的解法了。

定义是选出最少点覆盖所有边 ...

谢谢谢谢。虽然没看太明白。