-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathSolution.java
More file actions
110 lines (78 loc) · 6.34 KB
/
Solution.java
File metadata and controls
110 lines (78 loc) · 6.34 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//Nathanael saith unto him, Whence knowest thou me? Jesus answered and said unto him, Before that Philip called thee, when thou wast under the fig tree, I saw thee. (John 1:48)
package com.javarush.task.task36.task3611;
import java.util.HashSet;
import java.util.Set;
/*
Сколько у человека потенциальных друзей?
*/
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> result = new HashSet<>();
if (deep == 0) return result;
for (int i = 0; i < humansRelationships.length; i++) {
if (i < index) {
if (humansRelationships[index][i]) {
result.add(i);
result.addAll(getAllFriendsAndPotentialFriends(i, deep - 1));
}
} else {
if (humansRelationships[i][index]) {
result.add(i);
result.addAll(getAllFriendsAndPotentialFriends(i, deep - 1));
}
}
}
result.remove(index);
return result;
}
//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
};
}
}
/*
Сколько у человека потенциальных друзей?
Сегодня рассмотрим часть функционала социальных сетей. Откуда сеть знает, каких людей предлагать тебе в друзья, которых ты можешь знать? Эту задачу легко решить с помощью графов.
Твоя задача реализовать метод Set<Integer> getAllFriendsAndPotentialFriends(int index, int deep), который возвращает индексы людей, которые у тебя в друзьях уже есть и которых ты можешь знать. После этого отработает метод removeFriendsFromSet, и результат этого метода - это все потенциальные друзья человека с индексом index и глубиной поиска deep.
Для упрощения будем рассматривать связи всех людей как двумерный массив humansRelationships (смотри пример массива в методе generateRelationships). По главной диагонали все элементы true, так как это один и тот же человек. Пересечение столбца и столбика указывает, добавлены ли люди друг у друга в друзья (если true - то люди есть друг у друга в друзьях). Если человек с индексом k добавлен в друзья к человеку с индексом p, это означает, что у человека с индексом p в друзьях есть человек с индексом k.
В метод передается два аргумента:
int index - это индекс человека в массиве (начиная с нуля);
int deep - глубина поиска друзей. Если Маша в друзьях у Наташи и у Маши в друзьях есть Оля, при глубине поиска = 1, для Наташи нужно добавить в результирующее множество Машу и как потенциального друга Олю. Если глубина поиска = 2, в это же множество нужно добавить еще и всех, с кем дружит Оля.
Смотри пример в методе main.
В множестве, которое возвращает метод getAllFriendsAndPotentialFriends не должно быть индекса index.
Требования:
1. В классе Solution должен существовать публичный метод Set getAllFriendsAndPotentialFriends(int index, int deep).
2. В классе Solution должно быть объявлено приватное поле boolean[][] humansRelationships.
3. В множестве, которое возвращает метод getAllFriendsAndPotentialFriends не должно быть индекса index.
4. Метод getAllFriendsAndPotentialFriends должен быть реализован согласно условию.
*/