1回答

liuyubobobo

2018-03-30

已采纳

我不确定我对题目的理解是否完全正确。但是根据你的描述，只要根据已知的发红包关系构建一个图（无向图就可以），之后求一遍图里的所有联通分量。最后所有联通分量的节点个数为1的那些节点，就是和任何其他人都没有关系的人。

如果你看过我的《算法与数据结构》课程，或者了解并查集这个结构，这个问题也可以使用并查集解决。对于每条X发给Y红包的信息，将X所在的集合和Y所在的集合合并起来。最终，在并查集中，那些id[i]==i，也就是id[i]依旧指向自己的节点，就是和任何其他人都没有关系的人。

不过，一般面试不会考察并查集的使用，所以第二个方法应该不在面试官的预期范围里。并查集通常是竞赛中常用的数据结构，当然，在面试中如果能提到或者写出并查集的方法，肯定是加分的。（只要面试官别太菜，自己不了解什么是并查集，但是一般考算法的面试官应该不至于。）

---

对于算法问题的解决，通常大概可以分两个层次。

第一个层次，了解基本的算法（和数据结构）。比如，这个问，题需要使用强联通分量解决，但是你完全不懂怎么求图的强联通分量，甚至不知道什么是图的强联通分量，那肯定是无法正确解决问题的。同理，某个问题可能是在考察堆的使用，栈的使用，你最起码要知道什么是堆，什么是栈。如果在这个层面自己还有问题，那没的说，继续补基础。大致主流的算法和数据结构必须要了解。

第二个层次就是，你需要把（实际）问题转换成一个算法模型来解决。比如让你求图的强联通分量，你会；但是问题这样描述，你却想不到使用图的联通分量这个算法来解决这个问题。或者说你无法把这个问题转化成一个算法模型。大多数同学在这方面会偏弱一些。我个人认为，主要是见的问题比较少，对什么算法什么结构能大致解决怎样的问题还没有一个大概的认识。如果自己属于在这个层面需要提高，无他，多见面试题。在自己对基础算法（和数据结构）的编写已经没问题的基础上，甚至可以不写程序了，节省时间，就看题，想这个题目应该转换成使用什么算法解决。如果没思路，看答案。自己觉得有必要，并且有测试环境的话，可以写一写。

我完全理解很多同学希望对于每一个问题，能够有一个万能的“思考路径”，掌握了这个“思考路径”，顺着这个“思考路径”走下去，就能找到问题的解决方案。但可惜，实际上，这个万能的“思考路径”很有可能是不存在的。具体可以参见我在这个问答中的第8条：https://coding.imooc.com/learn/questiondetail/46130.html

加油！提前预祝Offer多多！：）

1

1

一轩明月

非常感谢：）

2018-03-30

共1条回复