从圈子里找一小群朋友？
从圈子里找一小群朋友？
提问于 2019-01-24 23:56:20
我正在处理以下问题：
在有人的房间里，如果两个人是直接或间接的朋友，我们会把他们定义为朋友。如果A是B的朋友，B是C的朋友，那么A也是C的朋友。一群朋友是一群人，其中任何两个人都是朋友。给出直接朋友的名单，找出最小的一群朋友。
示例:输入：
1<->6
2<->7
3<->8
4<->9
2<->6
3<->5组：
1-6-2-7
3-8-5
4-9最小群体中的人数是2，即4-9，所以我们应该返回2。
我想出了下面的代码，但我不明白如何现在使用这个holder映射来获得所需的输出。我在这里有点困惑。解决这个问题的最好办法是什么？
private static int findGroups(final List<List<Integer>> inputs) {
if (inputs == null || inputs.isEmpty()) {
return 0;
}
int count = Integer.MAX_VALUE;
Map<Integer, List<Integer>> holder = new HashMap<>();
for (List<Integer> input : inputs) {
// storing it in bidirectional way in the map
List<Integer> l =
holder.containsKey(input.get(0)) ? holder.get(input.get(0)) : new ArrayList<Integer>();
l.add(input.get(1));
holder.put(input.get(0), l);
List<Integer> l1 =
holder.containsKey(input.get(1)) ? holder.get(input.get(1)) : new ArrayList<Integer>();
l1.add(input.get(0));
holder.put(input.get(1), l1);
}
System.out.println(holder);
// use holder map to get the smaller group here?
return count;
}看起来我需要在这里使用递归来获得更小的组？
回答 1
Stack Overflow用户
发布于 2019-02-08 01:41:06
这是一些代码，我写这些是出于对你的问题的好奇。我对图不太了解，但它使用递归，正如您所要求的。
基本上，您需要通过输入，然后为每个人创建一个ArrayList<Integer>。在这一列中，是那个人的直接朋友。例如，对于1: {6}, for 2: {7, 6}, for 3: {8, 5}。然后，为了获得person 2的所有朋友，您可以通过将person 7和6的数组集合在一起(不包括副本)来创建复合ArrayList<Integer>数组。因此，使用递归的方式可以是，函数getAllFriends(Integer person)也必须为该人的直接朋友返回getAllFriends(Integer person2)。
所以，代码看起来可能像这样：
public class Test {
public static void main(String[] args) throws Exception {
String input = "1<->6\n" +
"2<->7\n" +
"3<->8\n" +
"4<->9\n" +
"2<->6\n" +
"3<->5";
HashMap<Integer, ArrayList<Integer>> friends = processInput(input); //getting data from the input string and storing it in a structured way
System.out.println(getAllFriends(1, friends, new ArrayList<Integer>(){{add(1);}})); //output: [1, 6, 2, 7]. Double brackets create an anonymous inner class, you add to the result the id of a person whose friends you're collecting
}
public static HashMap<Integer, ArrayList<Integer>> processInput(String input) throws Exception {
HashMap<Integer, ArrayList<Integer>> result = new HashMap<>();
BufferedReader bufReader = new BufferedReader(new StringReader(input));
String line=null;
while( (line=bufReader.readLine()) != null )
{
Integer personLeft = Integer.valueOf(line.substring(0, line.indexOf("<")));
Integer personRight =Integer.valueOf(line.substring(line.indexOf(">")+1, line.length()));
System.out.println(personLeft + ": " + personRight);
if (!result.containsKey(personLeft)) {
result.put(personLeft, new ArrayList<Integer>());
}
result.get(personLeft).add(personRight);
if (!result.containsKey(personRight)) {
result.put(personRight, new ArrayList<Integer>());
}
result.get(personRight).add(personLeft);
}
return result;
}
public static ArrayList<Integer> getAllFriends(Integer person, HashMap<Integer, ArrayList<Integer>> friends, ArrayList<Integer> result) {
for (Integer personFriend: friends.get(person)) {
if (!result.contains(personFriend)) {
result.add(personFriend); //add a person, if it wasn't added before
getAllFriends(personFriend, friends, result); //check out that person's friends
}
}
return result;
}
} 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54357151
复制相关文章
相似问题
腾讯云开发者
