最近我遇到一个问题,我不得不对它进行编码,但未能有效地进行编码。所以我会尽量用最好的方式来解释这个问题,就像。。
有不同的人属于不同的社区。例如,1属于C1,2属于C2,3属于C3。我们可以执行两个操作:查询和连接。Query返回属于个人社区的总人数。Join用于将两个人的社区合并为一个社区。
我们将人员数量和要执行的操作数量作为输入,我们需要将结果生成到标准输出中。
Example Case: (Q -> Query and J -> Join)
3 // No. of People
6 // No. of Operations
Q 1 // Prints 1
J 1,2 // Joins communities of 1 and 2
Q 1 // Prints 2
J 2,3 // Joins communities of 1 and 2
Q 3 // Prints 3
Q 1 // Prints 3
所以本质上,它就像人最初是属于个体的泡沫,在加入时,我们加入两个人的泡沫,形成一个包含两个人的更大的泡沫。
解决这个问题有不同的方法。使用Java的ArrayList方法,非常简单。我试着用数组来解决它。
我的方法是,最初为每个人形成一个数组,当我们加入两个社区时,将相应的数组与所述的人一起添加:
Arr1 : 1 // Array for Person 1 ; Size 1
Arr2 : 2 // Array for Person 2 ; Size 1
J 1,2 results in,
Arr1 : 1,2 // Size 2
Arr2 : 2,1 // Size 2
但有人告诉我,这不是一个有效的办法,一个有效的办法是利用链表。我无法用链表来解决这个问题。所以我希望你们能提供一些关于这个方法的信息,我应该如何使用链表来跟踪连接操作?
很抱歉发了这么长的信,提前谢谢:)
注:我不确定标题是否合适,如果不合适,请建议合适的标题。
最佳答案
我不知道为什么有人觉得在这个例子中链表比数组更好,但是加入社区就像将一个社区的所有成员添加到另一个社区一样简单,并将指向现在空的社区的所有指针更改为指向包含所有成员的节点。查询应该足够简单,不用说。