口袋宝石oa

9/5 找人内推， 9/6 拿到了oa， 今天下午做的oa， 然后3个case没有过，内存没达到要求，估计是挂了。现在把题目复盘一下，虽然忘记截图了= = 也是做个总结。
题目是max difference， 和leetcode 547 friends circle 特别像， 可以先做547再去做oa。
题目要求： 一个图有1~N一共N个结点，有一些结点是相互连通的，称为连通分量，需要输出每个连通分量的difference的最大值， 每个连通分量的difference定义为这个连通分量结点的最大值和最小值的差。
sample case 1 ：
{1，2，3，4，5}
只有一个连通分量，答案就是5-1 = 4

sample

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

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

是用普通的dfs解决比较好，我没有用union find。先设定三个global variable, diff, max, min. 每次dfs的时候把max和min都重新赋值一下就好了，剩下的就是每个dfs正常求解diff最大值就好。

因为现在写也没有test case了，所以不知道对不对，希望给后来人一些思路吧。
以上

小白来看看，谢谢楼主

动物园鸭 发表于 2017-9-9 13:04
小白来看看，谢谢楼主

惭愧惭愧

赞个学长！！！

BullMonk 发表于 2017-9-25 11:50
求问楼主拿的哪一套，challenge3还是challenge4？

我是3，字数字数