遍历包含两个值的元素列表并仅汇总连接的值（Java）

Question

我需要帮助解决以下问题。当我有一个包含两个值的元素列表时，它表示桥的起点和终点。这些值代表“桥梁”。因此，例如 [0,1] 表示连接 island0 和 island1 的桥。

我如何遍历从 0 开始的列表，只总结连接的值而忽略其他值？

示例 1 - 每个岛都是间接连接的

[0,1]

[1,2]

[2,3]

[3,4]

解应该是：0+1+2+3+4 = 10

示例 2

[0,1]

[1,2]

[3,4] !!! NOT CONNECTED

解应该是：0+1+2 = 3

Answer 1

试试下面的。更改Bridge对象以满足您的要求public class Bridge {&nbsp; &nbsp; int start;&nbsp; &nbsp; int end;&nbsp; &nbsp; public Bridge(int start, int end) {&nbsp; &nbsp; &nbsp; &nbsp; this.start = start;&nbsp; &nbsp; &nbsp; &nbsp; this.end = end;&nbsp; &nbsp; }&nbsp; &nbsp; public int getStart() {&nbsp; &nbsp; &nbsp; &nbsp; return start;&nbsp; &nbsp; }&nbsp; &nbsp; public int getEnd() {&nbsp; &nbsp; &nbsp; &nbsp; return end;&nbsp; &nbsp; }}计算总和import java.io.IOException;import java.util.ArrayList;import java.util.List;public class BridgeSum {&nbsp; &nbsp; public static void main(String... args) throws IOException {&nbsp; &nbsp; &nbsp; &nbsp; Bridge B1 = new Bridge(0, 1);&nbsp; &nbsp; &nbsp; &nbsp; Bridge B2 = new Bridge(1, 2);&nbsp; &nbsp; &nbsp; &nbsp; Bridge B3 = new Bridge(2, 4);&nbsp; &nbsp; &nbsp; &nbsp; Bridge B4 = new Bridge(4, 8);&nbsp; &nbsp; &nbsp; &nbsp; Bridge B5 = new Bridge(8, 9);&nbsp; &nbsp; &nbsp; &nbsp; List<Bridge> list = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; list.add(B5);&nbsp; &nbsp; &nbsp; &nbsp; list.add(B2);&nbsp; &nbsp; &nbsp; &nbsp; list.add(B3);&nbsp; &nbsp; &nbsp; &nbsp; list.add(B1);&nbsp; &nbsp; &nbsp; &nbsp; list.add(B4);&nbsp; &nbsp; &nbsp; &nbsp; list.sort((a, b) -> a.getStart() > b.getStart() ? 0 : -1);&nbsp; &nbsp; &nbsp; &nbsp; int sum = 0;&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < list.size(); i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum = sum + list.get(i).getStart() + list.get(i).getEnd();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (list.get(i).getStart() == list.get(i - 1).getEnd()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum = sum + list.get(i).getEnd();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(sum);&nbsp; &nbsp; }}

Answer 2

有了一些限制，它可能很容易，没有它可能会变得更复杂。有了约束，我的意思是第一座桥梁应该是真相的来源。想想这些案例：[0,1][1,2][3,4][4,5]（内部连接相同长度的两部分）[0,1][1,2][3,4][4,5]（第一个桥是排除的）如果桥 1+2 已连接且 3+4 已连接但未将两个部分连接在一起，会发生什么情况？我是说这个...[0,1][2,3][3,4][4,5]假设第一座桥是直通的来源，你可以试试这个：public class IslandConnector {&nbsp; &nbsp; private final List<Bridge> includedBridges = new ArrayList<>();&nbsp; &nbsp; private List<Bridge> excludedBridges;&nbsp; &nbsp; public IslandConnector(List<Bridge> bridges) {&nbsp; &nbsp; &nbsp; &nbsp; this.excludedBridges = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; for(Bridge bridge : bridges) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(includedBridges.isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; includedBridges.add(bridge);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(!tryIncludeBridge(bridge)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; excludedBridges.add(bridge);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; private boolean tryIncludeBridge(Bridge bridge) {&nbsp; &nbsp; &nbsp; &nbsp; for(Bridge includedBridge: includedBridges) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(bridge.hasSameS(includedBridge)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; includeBridge(bridge);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; }&nbsp; &nbsp; private void includeBridge(Bridge bridge) {&nbsp; &nbsp; &nbsp; &nbsp; includedBridges.add(bridge);&nbsp; &nbsp; &nbsp; &nbsp; for(Bridge excludedBridge: excludedBridges) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(bridge.hasSameS(excludedBridge)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; excludedBridges.remove(excludedBridge);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; includeBridge(excludedBridge);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; public List<Bridge> getIncludedBridges() {&nbsp; &nbsp; &nbsp; &nbsp; return includedBridges;&nbsp; &nbsp; }&nbsp; &nbsp; public static void main(String... args) {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(new IslandConnector(Arrays.asList(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new Bridge(0, 1),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new Bridge(1, 2),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new Bridge(2, 3),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new Bridge(3, 4)&nbsp; &nbsp; &nbsp; &nbsp; )).getIncludedBridges());&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(new IslandConnector(Arrays.asList(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new Bridge(0, 1),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new Bridge(1, 2),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new Bridge(3, 4)&nbsp; &nbsp; &nbsp; &nbsp; )).getIncludedBridges());&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(new IslandConnector(Arrays.asList(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new Bridge(0, 1),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new Bridge(2, 3),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new Bridge(3, 4)&nbsp; &nbsp; &nbsp; &nbsp; )).getIncludedBridges());&nbsp; &nbsp; }}印刷[[0,1], [1,2], [2,3], [3,4]][[0,1], [1,2]][[0,1]]

Answer 3

具有以下课程：public class Graph<V> {&nbsp; &nbsp; private static class Edge<VV> {&nbsp; &nbsp; &nbsp; &nbsp; private final VV from;&nbsp; &nbsp; &nbsp; &nbsp; private final VV to;&nbsp; &nbsp; &nbsp; &nbsp; private Edge(VV from, VV to) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.from = from;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.to = to;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; private final Set<V> vertices = new HashSet<>();&nbsp; &nbsp; private final Collection<Edge<V>> edges = new ArrayList<>();&nbsp; &nbsp; public void addEdge(V from, V to) {&nbsp; &nbsp; &nbsp; &nbsp; vertices.add(from);&nbsp; &nbsp; &nbsp; &nbsp; vertices.add(to);&nbsp; &nbsp; &nbsp; &nbsp; edges.add(new Edge(from, to));&nbsp; &nbsp; }&nbsp; &nbsp; public Set<V> closure(V start) {&nbsp; &nbsp; &nbsp; &nbsp; Set<V> result = new HashSet<>();&nbsp; &nbsp; &nbsp; &nbsp; closure(start, result);&nbsp; &nbsp; &nbsp; &nbsp; return result;&nbsp; &nbsp; }&nbsp; &nbsp; private void closure(V start, Set<V> seen) {&nbsp; &nbsp; &nbsp; &nbsp; if (vertices.contains(start) && !seen.contains(start)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; seen.add(start);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (Edge<V> e: edges) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (start.equals(e.from)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; closure(e.to, seen);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}你可以这样做：&nbsp; &nbsp; Graph<Integer> graph = new Graph<>();&nbsp; &nbsp; graph.addEdge(0,1);&nbsp; &nbsp; graph.addEdge(1,2);&nbsp; &nbsp; graph.addEdge(3,4);&nbsp; &nbsp; int sum = 0;&nbsp; &nbsp; for (int v: graph.closure(0)) {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Vertex: " + v);&nbsp; &nbsp; &nbsp; &nbsp; sum += v;&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println("Sum: " + sum);使用以下输出：Vertex: 0Vertex: 1Vertex: 2Sum: 3

Answer 4

用 HashMap 试试这个解决方案public class BridgeSolution {&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; Map<Integer, Integer> bridgeMap = new HashMap<>();&nbsp; &nbsp; &nbsp; &nbsp; List<Integer[]> bridges = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; bridges.add(new Integer[]{0, 1});&nbsp; &nbsp; &nbsp; &nbsp; bridges.add(new Integer[]{1, 2});&nbsp; &nbsp; &nbsp; &nbsp; bridges.add(new Integer[]{2, 3});&nbsp; &nbsp; &nbsp; &nbsp; bridges.add(new Integer[]{3, 4});&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < bridges.size(); i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bridgeMap.put(bridges.get(i)[0], bridges.get(i)[1]);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; Integer start = bridges.get(0)[0];&nbsp; &nbsp; &nbsp; &nbsp; Integer value = null;&nbsp; &nbsp; &nbsp; &nbsp; Integer sum = start;&nbsp; &nbsp; &nbsp; &nbsp; while ((value = bridgeMap.get(start)) != null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum += value;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start = value;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(sum);&nbsp; &nbsp; }}