Блог

Я борюсь с этой проблемой на HackerRank. https://www.hackerrank.com/challenges/friend-circle-queries/problem Я попытался решить это с помощью пользовательского связанного списка — NodeList. В нем есть три поля — Node first, Node current, int size. «добавить» — это перегруженный метод. Это может добавить значение или другой список узлов. Я поместил код для 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, но у него тоже такая же проблема, поэтому я думаю, что проблема не в структуре данных.

Поскольку неясно, что именно не так с решением (это не указано в OP) — неправильные ответы или тайм-аут для некоторых тестовых случаев, я объясню, как это решить.

Мы можем использовать структуру данных непересекающегося набора для представления наборов кругов друзей.

Основная идея заключается в том, что в каждом круге мы назначаем член, который используется для представления данного круга. Мы можем назвать это root. Поиск количества участников в круге всегда делегируется корню, который хранит его размер.

Каждый некорневой участник указывает на своего корневого участника или на участника, через которого он может получить доступ к корню. В будущем текущий корень также может потерять свой статус root для сообщества, но тогда он будет указывать на новый корень, и поэтому к нему всегда можно добраться с помощью связанных вызовов.

Когда 2 круги сливаются, новый корневой участник выбирается среди 2 предыдущих. В него можно задать новый размер, поскольку предыдущие корни уже содержат размеры для обоих кругов. Но как выбирается новый root? Если размер circle 1 не меньше, чем у circle 2 , то он выбирается в качестве нового корня.

Итак, для решения этой проблемы сначала мы должны определить заполнители для circles и sizes :

 Map<Integer, Integer> people;
Map<Integer, Integer> sizes;
  

Для некорневых участников в people key — это идентификатор пользователя, а value — друг, на которого он подписан (root или родительский, который может привести его к root). У корневых участников не будет записи на карте.

Затем нам нужен метод, который приведет нас к корню для любого участника:

 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;
}