Алгоритм Hackerrank Friend Circle Query - PullRequest
Новая
       13

Алгоритм Hackerrank Friend Circle Query

2 голосов
/ 09 марта 2019

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

...