问题
给出一些Connections,即Connections类,找到一些能够将所有城市都连接起来并且花费最小的边。
如果说可以将所有城市都连接起来,则返回这个连接方法;不然的话返回一个空列表。
注意事项
返回cost最小的连接方法,如果cost相同就按照city1进行排序,如果city1也相同那么就按照city2进行排序。
辅助类:
public class Connection {
public String city1;
public String city2;
public int cost;
public Connection(String city1, String city2, int cost) {
this.city1 = city1;
this.city2 = city2;
this.cost = cost;
}
}
样例
给出 connections = ["Acity","Bcity",1], ["Acity","Ccity",2], ["Bcity","Ccity",3]
返回 ["Acity","Bcity",1], ["Acity","Ccity",2]
思路
本题一看题目就知道是无向图的最小生成树问题,而解决这个问题有2个著名的算法,Prim算法和Kruskal算法,但是Prim算法在有相同权值的边时会失效,所以此题只能用Kruskal算法来解决。
Kruskal算法的主要思想是把边按照权值从小到大排序,然后依次取出最小边。
实现
public List<Connection> lowestCost(List<Connection> connections) {
// Write your code here
connections.sort(new Comparator<Connection>() {
@Override
public int compare(Connection o1, Connection o2) {
if (o1.cost != o2.cost) {
return o1.cost - o2.cost;
} else {
if (o1.city1.equals(o2.city1)) {
return o1.city2.compareTo(o2.city2);
} else {
return o1.city1.compareTo(o2.city1);
}
}
}
});
Set<String> points = new HashSet<>();
for (Connection connection : connections) {
points.add(connection.city1);
points.add(connection.city2);
}
List<Connection> result = new ArrayList<>();
List<Set<String>> pointSets = new ArrayList<>();
for (String point : points) {
Set<String> set = new HashSet<>();
set.add(point);
pointSets.add(set);
}
for (Connection connection : connections) {
String start = connection.city1;
String end = connection.city2;
int startIndex = -1;
int endIndex = -1;
int i = 0;
for (Set<String> point : pointSets) {
if (point.contains(start)) {
startIndex = i;
}
if (point.contains(end)) {
endIndex = i;
}
i++;
}
if (startIndex < 0 || endIndex < 0) {
return new ArrayList<>();
}
// 比较startIndex和endIndex大小的原因:如果先删除HasHMap较小index的元素,再删除较大Index元素时,会造成数组越界
// 所以hashSet执行多个remove操作的时候,一定要从后往前删
if (startIndex > endIndex) {
Set<String> startSet = pointSets.get(startIndex);
pointSets.remove(startIndex);
Set<String> endSet = pointSets.get(endIndex);
pointSets.remove(endIndex);
startSet.addAll(endSet);
pointSets.add(startSet);
result.add(connection);
} else if (startIndex < endIndex) {
Set<String> endSet = pointSets.get(endIndex);
pointSets.remove(endIndex);
Set<String> startSet = pointSets.get(startIndex);
pointSets.remove(startIndex);
startSet.addAll(endSet);
pointSets.add(startSet);
result.add(connection);
}
}
if (pointSets.size() > 1) {
return new ArrayList<>();
}
return result;
}
如果文章对你有帮助的话,不要忘了打赏小编哟
网友评论