合并社区并找到最大社区的大小
我正在努力解决HackerRank上的这个问题。我试着用一个自定义的链表-- NodeList来解决这个问题。它有三个字段- Node first，Node current，int size。“‘add”是一个重载方法。它可以添加一个值或另一个NodeList。我将NodeList的代码放在注释中，因为这并不重要。
字段:-
static HashMap<Integer, Integer> personToIndex = new HashMap<>();
static int largestCircleSize = 0;
static ArrayList<NodeList> groups = new ArrayList<>();这是我的业务逻辑方法。当只有一个人是朋友圈的一部分时，我会在朋友圈中添加另一个人。当握手的两个人都已经是其他圈子的一部分时，我就合并这些圈子。
static void updateFriendCircles(int friend1, int friend2) {
int friend1Index, friend2Index;
NodeList toUpdate;
friend1Index = personToIndex.getOrDefault(friend1, -1);
friend2Index = personToIndex.getOrDefault(friend2, -1);
if (friend1Index != -1) {
NodeList list = groups.get(friend1Index);
if (friend2Index != -1) {
NodeList list2 = groups.get(friend2Index);
if (list.first == groups.get(friend2Index).first)
return;
toUpdate = list.add(list2);
groups.set(friend2Index, list);
}
else {
toUpdate = list.add(friend2);
personToIndex.put(friend2, friend1Index);
}
}
else if (friend2Index != -1) {
toUpdate = groups.get(friend2Index).add(friend1);
personToIndex.put(friend1, friend2Index);
}
else {
int index = groups.size();
personToIndex.put(friend1, index);
personToIndex.put(friend2, index);
toUpdate = new NodeList(friend1).add(friend2);
groups.add(toUpdate);
}
if (toUpdate.size > largestCircleSize)
largestCircleSize = toUpdate.size;
}我也尝试过使用HashSet，但它也有同样的问题，所以我认为问题不在数据结构上。
回答 1
Stack Overflow用户
发布于 2019-12-16 00:32:27
由于不清楚解决方案到底出了什么问题(它不是由OP指定的)-一些测试用例的错误答案或超时，我将解释如何解决它。
我们可以使用disjoint set数据结构来表示朋友圈的集合。
基本思想是，在每个圆中，我们分配一个成员，用于表示给定的圆。我们可以称它为根。查找圆圈中的许多成员始终委托给存储其大小的根。
每个非根成员指向他的根成员，或者指向他可以通过其到达根的成员。将来，当前的root可能也会失去他在社区中的root状态，但随后它将指向新的root，因此始终可以通过链式调用到达它。
当2循环合并时，将从2先前的循环中选择一个新的根成员。可以在其中设置新的大小，因为以前的根已经包含了两个圆的大小。但是如何选择新的根呢？如果圆1的大小不小于圆2的大小，则将其选为新的根。
因此，对于这个问题，首先我们应该为circles和sizes定义占位符
Map<Integer, Integer> people;
Map<Integer, Integer> sizes;对于people中的非根成员，key是person ID，value是他关注的朋友(根或父级，可以让他找到根)。根成员在映射中不会有条目。
然后，我们需要一个方法，它可以让我们找到任何成员的根：
int findCommunityRoot(int x) {
if (people.containsKey(x)) {
return findCommunityRoot(people.get(x));
}
return x;
}最后，我们需要一个方法来为给定朋友的2构建一个社区：
int mergeCommunities(int x, int y) {
//find a root of x
x = findCommunityRoot(x);
//find a root of y
y = findCommunityRoot(y);
// one-man circle has a size of 1
if (!sizes.containsKey(x)) {
sizes.put(x, 1);
}
// one-man circle has a size of 1
if (!sizes.containsKey(y)) {
sizes.put(y, 1);
}
// friends in the same circle so just return its size
if (x == y) {
return sizes.get(x);
}
sizeX = sizes.get(x);
sizeY = sizes.get(y);
if (sizeX >= sizeY) {
people.put(y, x);
sizes.put(x, sizeY + sizeX);
return sizes.get(x);
} else {
people.put(x, y);
sizes.put(y, sizeY + sizeX);
return sizes.get(y);
}
}因此，我们有了在每次迭代中保存最大圆的大小所需的一切：
List<Integer> maxCircle(int[][] queries) {
List<Integer> maxCircles = new ArrayList<>();
int maxSize = 1;
for (int i = 0; i < queries.length; i++) {
int size = mergeCommunities(queries[i][0], queries[i][1]);
maxSize = Math.max(maxSize, size);
maxCircles.add(maxSize);
}
return maxCircles;
}https://stackoverflow.com/questions/55077964
复制相似问题
腾讯云开发者
