做了半天愣是0%，发帖记录（Java）节点类：class Node { int val; List neighbor = new ArrayList<>(); boolean visited;}思路：1. 先获取到所有边，存到节点数组中；2. 已知根节点为“1”，使用广度优先或者层式遍历方式遍历；3. 遍历时注意判断当前节点的neighbor是否已被访问（即为父节点），排除父节点后则可知子节点数量；代码实践：import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set;import java.util.stream.Collectors;class Node { int val; List neighbor = new ArrayList<>(); public Node(int val) { this.val = val; }}public class T2 { public static void main(String[] args) {// Scanner in = new Scanner(System.in);// int T = in.nextInt(); int T = 1; int[] ns = new int[]{7}; int[][] bs = new int[][]{ {1, 2}, {1, 3}, {3, 5}, {3, 7}, {2, 4}, {2, 6} }; for (int i = 0; i long res = 0;// int n = in.nextInt(); int n = ns[i]; Node[] nodeArr = new Node[n]; for (int j = 0; j int u = bs[j][0]; int v = bs[j][1]; if (nodeArr[u - 1] == null) { nodeArr[u - 1] = new Node(u - 1); } if (nodeArr[v - 1] == null) { nodeArr[v - 1] = new Node(v - 1); } nodeArr[u - 1].neighbor.add(nodeArr[v - 1]); nodeArr[v - 1].neighbor.add(nodeArr[u - 1]); } int[] count = new int[3]; count[nodeArr[0].neighbor.size()]++; Set visited = new HashSet<>(); visited.add(nodeArr[0].val); List curNodes = nodeArr[0].neighbor; List tmpNodes = new ArrayList<>(); while (curNodes.size() > 0) { for (Node node : curNodes) { visited.add(node.val); List nextNodes = node.neighbor.stream().filter(nodeTmp -> !visited.contains(nodeTmp.val)).collect(Collectors.toList()); int childNum = nextNodes.size(); count[childNum]++; tmpNodes.addAll(nextNodes); } curNodes = tmpNodes; tmpNodes = new ArrayList<>(); } for (int c: count) { res += getPairCount(c); } System.out.println(res); } } static long getPairCount(int n) { if (n return 0; } return (long) n * (n - 1) / 2; }}
查看3道真题和解析
投递美团等公司10个岗位