Не могу понять где ошибка, знаю, что неправильно нахожу поддрузей.

Вопрос по задаче

Сколько у человека потенциальных друзей?

Решен

Ошибка где-то тут, но не могу найти

while (deep > 1) {
            count = q.size();
            for (int j = 0; j < count; ++j) {
                int tmp = q.poll();
                for (int i = 0; i < humansRelationships.length; i++) {
                    if ((i < tmp) && (tmp < humansRelationships.length) && humansRelationships[tmp][i]) {
                        set.add(i);
                        if(!q.contains(i))
                            q.add(i);
                    } else if ((i > tmp) && humansRelationships[i][tmp]) {
                        set.add(i);
                        if(!q.contains(i))
                            q.add(i);

                    }
                }
            }
            deep--;
        }

Сегодня рассмотрим часть функционала социальных сетей. Откуда сеть знает, каких людей предлагать тебе в друзья, которых ты можешь знать? Эту задачу легко решить с помощью графов.

Твоя задача реализовать метод Set<Integer> getAllFriendsAndPotentialFriends(int index, int deep), который возвращает индексы людей, которые у тебя в друзьях уже есть и которых ты можешь знать. После этого отработает метод removeFriendsFromSet, и результат этого метода - это все потенциальные друзья человека с индексом index и глубиной поиска deep.
Для упрощения будем рассматривать связи всех людей как двумерный массив humanRelationships (смотри пример массива в методе generateRelationships). По главной диагонали все элементы true, так как это один и тот же человек. Пересечение строки и столбца указывает, добавлены ли люди друг у друга в друзья (если true - то люди есть друг у друга в друзьях). Если человек с индексом k добавлен в друзья к человеку с индексом p, это означает, что у человека с индексом p в друзьях есть человек с индексом k.

В метод передается два аргумента:
int index - это индекс человека в массиве (начиная с нуля);
int deep - глубина поиска друзей. Если Маша в друзьях у Наташи и у Маши в друзьях есть Оля, при глубине поиска = 1, для Наташи нужно добавить в результирующее множество Машу. Если глубина поиска = 2, для Наташи нужно добавить в результирующее множество Машу и как потенциального друга Олю. Если глубина поиска = 3, в это же множество нужно добавить еще и всех, с кем дружит Оля.
Смотри пример в методе main.
В множестве, которое возвращает метод getAllFriendsAndPotentialFriends не должно быть индекса index.

Требования:

В классе Solution должен существовать публичный метод Set<Integer> getAllFriendsAndPotentialFriends(int index, int deep).
В классе Solution должно быть объявлено приватное поле boolean[][] humanRelationships.
В множестве, которое возвращает метод getAllFriendsAndPotentialFriends не должно быть индекса index.
Метод getAllFriendsAndPotentialFriends должен быть реализован согласно условию.

package com.javarush.task.task36.task3611; import java.util.*; /* Сколько у человека потенциальных друзей? */ public class Solution { private boolean[][] humansRelationships; public static void main(String[] args) { Solution solution = new Solution(); solution.humansRelationships = generateRelationships(); Set<Integer> allFriendsAndPotentialFriends = solution.getAllFriendsAndPotentialFriends(4, 2); System.out.println(allFriendsAndPotentialFriends); //expected: [0, 1, 2, 3, 5, 7] Set<Integer> potentialFriends = solution.removeFriendsFromSet(allFriendsAndPotentialFriends, 4); System.out.println(potentialFriends); //expected: [2, 5, 7] } public Set<Integer> getAllFriendsAndPotentialFriends(int index, int deep) { Set<Integer> set = new TreeSet<>(); for (int i = 0; i < humansRelationships.length; i++) { if ((i < index) && (index < humansRelationships.length) && humansRelationships[index][i]) { set.add(i); } else if ((i > index) && humansRelationships[i][index]) { set.add(i); } } Queue<Integer> q = new PriorityQueue<>(); q.addAll(set); int count = 0; while (deep > 1) { count = q.size(); for (int j = 0; j < count; ++j) { int tmp = q.poll(); for (int i = 0; i < humansRelationships.length; i++) { if ((i < tmp) && (tmp < humansRelationships.length) && humansRelationships[tmp][i]) { set.add(i); if(!q.contains(i)) q.add(i); } else if ((i > tmp) && humansRelationships[i][tmp]) { set.add(i); if(!q.contains(i)) q.add(i); } } } deep--; } //удаляем число index из списка set.remove(Integer.valueOf(index)); return set; //напишите тут ваш код } //remove people from set, with which you have already had relationship public Set<Integer> removeFriendsFromSet(Set<Integer> set, int index) { for (int i = 0; i < humansRelationships.length; i++) { if ((i < index) && (index < humansRelationships.length) && humansRelationships[index][i]) { set.remove(i); } else if ((i > index) && humansRelationships[i][index]) { set.remove(i); } } return set; } //return test data private static boolean[][] generateRelationships() { return new boolean[][]{ {true}, //0 {true, true}, //1 {false, true, true}, //2 {false, false, false, true}, //3 {true, true, false, true, true}, //4 {true, false, true, false, false, true}, //5 {false, false, false, false, false, true, true}, //6 {false, false, false, true, false, false, false, true} //7 }; } }

Комментарии (1)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Максим

Уровень 40

17 ноября 2018, 05:26

решение

Нашел ошибку, я считаю, она достаточно очевидная, но у меня ушло достаточно много времени, чтобы ее увидеть. Ошибка в 32 строке:

Queue<Integer> q = new PriorityQueue<>();

Из-за того, что я создаю PriorityQueue<>(); она меняет порядок элементов при добавлении в нее новых элементов, а он крайне важен, иначе неправильный перебор "друзей" пойдет. Заменил ее на:

Queue<Integer> q = new ArrayDeque<>();

И все заработало как надо.