华为OD机试真题 新系统 2026-05-10 JavaGoC语言 实现【寻找孤立水站】
目录
题目
思路
Code
题目
城市供水管道由若干个连接外部的源头水站，以及内部水站、水管组成。
全市共有 n 个水站，编号为 0 至 n-1。
供水网络由若干管道连接，管道分为两类：
1. 单向管道（Type 0）：水流只能从水站 u 流向水站 v；
2. 双向管道（Type 1）：水流可以在水站 u 和 v 之间双向流动。受战争影响，城市中的一部分供水管道破裂，导致部分水站无法获得供水，我们将这些无法从任一源头水站到达的水站称为孤立站。
假设源头站一定有水（并且源头站本身不算孤立站），请你根据输入的各个水站的联通情况，输出孤立站的列表，结果按编号从小到大排列。
输入
1. n：整型，水站数量，水站编号为 0 至 n-1，0 < n <= 10000；
2. sources：整型数组，数组元素为源头水站编号；
3. pipes：二维数组，数组元素为 [u, v, type]，表示水站连通关系，其中 u、v 为水站编号，type 为连通类型；
- [u, v, 0] 表示单向管道，水可由 u 流向 v，不可由 v 流向 u；
- [u, v, 1] 表示双向管道，水可由 u 流向 v，也可由 v 流向 u。输出
孤立站列表，类型为整型数组，数组元素为孤立站编号，结果从小到大排列。输入描述
输入为一行，格式为：
n,sources,pipes
其中：
1. n 是整数；
2. sources 是形如 [1,3] 的整型数组；
3. pipes 是形如 [[1,0,0],[1,2,0]] 的二维数组。输出描述
输出孤立站编号数组，按从小到大排列。
若不存在孤立站，则输出 []。样例1
输入
5,[1],[[1,0,0],[1,2,0]]输出
[3,4]说明
源头站为 1。
由 1 可以到达 0 和 2，因此 0、1、2 都不是孤立站。
水站 3 和 4 无法从任一源头站到达，所以输出 [3,4]。
思路
1.经典的BFS/DFS 图类型的题目。
2.把所有水站看成图上的点，把管道看成边。
3.单向管道就加一条有向边，双向管道就加两条相反方向的边。然后从所有 sources 同时出发做一次 BFS 或 DFS，把所有能被源头水站到达的点标记出来。
4.最后遍历 0 ~ n-1，所有没有被访问到的水站就是孤立站，按编号顺序收集输出即可。
5.题目里真正稍微麻烦一点的是输入解析，因为输入是一整行 n,sources,pipes，后两部分本身也带逗号，所以不能直接普通 split(",")，需要按“最外层逗号”切分。
Code
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static class Parser { String s; int idx; Parser(String s) { this.s = s; this.idx = 0; } // 跳过空格，避免输入中夹杂空白字符影响解析。 void skipSpaces() { while (idx < s.length() && Character.isWhitespace(s.charAt(idx))) { idx++; } } // 解析一个整数，支持非负数。 int parseInt() { skipSpaces(); int num = 0; while (idx < s.length() && Character.isDigit(s.charAt(idx))) { num = num * 10 + (s.charAt(idx) - '0'); idx++; } return num; } // 解析形如 [1,2,3] 的一维数组。 List<Integer> parseIntArray() { skipSpaces(); List<Integer> result = new ArrayList<>(); idx++; // 跳过 '[' skipSpaces(); if (idx < s.length() && s.charAt(idx) == ']') { idx++; return result; } while (true) { result.add(parseInt()); skipSpaces(); if (s.charAt(idx) == ',') { idx++; continue; } if (s.charAt(idx) == ']') { idx++; break; } } return result; } // 解析形如 [[u,v,t],[u,v,t]] 的二维数组。 List<int[]> parsePipeArray() { skipSpaces(); List<int[]> result = new ArrayList<>(); idx++; // 跳过 '[' skipSpaces(); if (idx < s.length() && s.charAt(idx) == ']') { idx++; return result; } while (true) { List<Integer> item = parseIntArray(); result.add(new int[]{item.get(0), item.get(1), item.get(2)}); skipSpaces(); if (idx < s.length() && s.charAt(idx) == ',') { idx++; continue; } if (idx < s.length() && s.charAt(idx) == ']') { idx++; break; } } return result; } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line = br.readLine(); // 没有输入时按空数组处理。 if (line == null || line.trim().isEmpty()) { System.out.print("[]"); return; } // 先拆出最外层的三个部分：n、sources、pipes。 List<String> parts = new ArrayList<>(); int start = 0; int depth = 0; for (int i = 0; i < line.length(); i++) { char ch = line.charAt(i); if (ch == '[') depth++; else if (ch == ']') depth--; else if (ch == ',' && depth == 0) { parts.add(line.substring(start, i).trim()); start = i + 1; } } parts.add(line.substring(start).trim()); int n = Integer.parseInt(parts.get(0)); Parser sourceParser = new Parser(parts.get(1)); Parser pipeParser = new Parser(parts.get(2)); List<Integer> sources = sourceParser.parseIntArray(); List<int[]> pipes = pipeParser.parsePipeArray(); // 建图：单向边加一条，双向边加两条。 List<List<Integer>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } for (int[] pipe : pipes) { int u = pipe[0], v = pipe[1], type = pipe[2]; graph.get(u).add(v); if (type == 1) { graph.get(v).add(u); } } // 从所有源头站同时做 BFS，标记可达站点。 boolean[] visited = new boolean[n]; Queue<Integer> queue = new LinkedList<>(); for (int source : sources) { if (!visited[source]) { visited[source] = true; queue.offer(source); } } while (!queue.isEmpty()) { int node = queue.poll(); for (int next : graph.get(node)) { if (!visited[next]) { visited[next] = true; queue.offer(next); } } } // 所有不可达站点就是孤立站。 StringBuilder sb = new StringBuilder(); sb.append("["); boolean first = true; for (int i = 0; i < n; i++) { if (!visited[i]) { if (!first) { sb.append(","); } sb.append(i); first = false; } } sb.append("]"); System.out.print(sb.toString()); } }Go
package main import ( "bufio" "fmt" "os" "strings" "unicode" ) type Parser struct { s string idx int } // 跳过空格，避免输入中夹杂空白字符时影响解析。 func (p *Parser) skipSpaces() { for p.idx < len(p.s) && unicode.IsSpace(rune(p.s[p.idx])) { p.idx++ } } // 解析一个整数。 func (p *Parser) parseInt() int { p.skipSpaces() num := 0 for p.idx < len(p.s) && p.s[p.idx] >= '0' && p.s[p.idx] <= '9' { num = num*10 + int(p.s[p.idx]-'0') p.idx++ } return num } // 解析形如 [1,3] 的一维数组。 func (p *Parser) parseIntArray() []int { p.skipSpaces() result := make([]int, 0) p.idx++ // 跳过 '[' p.skipSpaces() if p.idx < len(p.s) && p.s[p.idx] == ']' { p.idx++ return result } for { result = append(result, p.parseInt()) p.skipSpaces() if p.s[p.idx] == ',' { p.idx++ continue } if p.s[p.idx] == ']' { p.idx++ break } } return result } // 解析形如 [[u,v,t],[u,v,t]] 的二维数组。 func (p *Parser) parsePipeArray() [][]int { p.skipSpaces() result := make([][]int, 0) p.idx++ // 跳过 '[' p.skipSpaces() if p.idx < len(p.s) && p.s[p.idx] == ']' { p.idx++ return result } for { result = append(result, p.parseIntArray()) p.skipSpaces() if p.idx < len(p.s) && p.s[p.idx] == ',' { p.idx++ continue } if p.idx < len(p.s) && p.s[p.idx] == ']' { p.idx++ break } } return result } func main() { reader := bufio.NewReader(os.Stdin) line, _ := reader.ReadString('\n') line = strings.TrimSpace(line) // 没有输入时按空数组输出。 if line == "" { fmt.Print("[]") return } // 按最外层逗号切出 n、sources、pipes 三部分。 parts := make([]string, 0) start := 0 depth := 0 for i, ch := range line { if ch == '[' { depth++ } else if ch == ']' { depth-- } else if ch == ',' && depth == 0 { parts = append(parts, strings.TrimSpace(line[start:i])) start = i + 1 } } parts = append(parts, strings.TrimSpace(line[start:])) nParser := &Parser{s: parts[0]} n := nParser.parseInt() sourceParser := &Parser{s: parts[1]} pipeParser := &Parser{s: parts[2]} sources := sourceParser.parseIntArray() pipes := pipeParser.parsePipeArray() // 建图：单向边加一条，双向边加两条。 graph := make([][]int, n) for _, pipe := range pipes { u, v, typ := pipe[0], pipe[1], pipe[2] graph[u] = append(graph[u], v) if typ == 1 { graph[v] = append(graph[v], u) } } // 从所有源头站同时做 BFS。 visited := make([]bool, n) queue := make([]int, 0) for _, source := range sources { if !visited[source] { visited[source] = true queue = append(queue, source) } } for head := 0; head < len(queue); head++ { node := queue[head] for _, next := range graph[node] { if !visited[next] { visited[next] = true queue = append(queue, next) } } } // 输出所有未访问到的站点。 var sb strings.Builder sb.WriteString("[") first := true for i := 0; i < n; i++ { if !visited[i] { if !first { sb.WriteString(",") } sb.WriteString(fmt.Sprintf("%d", i)) first = false } } sb.WriteString("]") fmt.Print(sb.String()) }C
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <ctype.h> #define MAXN 10005 #define MAXM 40005 #define MAXLINE 200000 typedef struct { int to; int next; } Edge; char s[MAXLINE]; int idxPtr; Edge edges[MAXM]; int head[MAXN]; int edgeCnt = 0; /* 跳过空白字符，避免空格影响解析。 */ void skipSpaces() { while (s[idxPtr] && isspace((unsigned char)s[idxPtr])) { idxPtr++; } } /* 解析一个整数。 */ int parseInt() { skipSpaces(); int num = 0; while (s[idxPtr] && isdigit((unsigned char)s[idxPtr])) { num = num * 10 + (s[idxPtr] - '0'); idxPtr++; } return num; } /* 加一条有向边 u -> v。 */ void addEdge(int u, int v) { edges[edgeCnt].to = v; edges[edgeCnt].next = head[u]; head[u] = edgeCnt++; } /* 解析一维数组 [a,b,c]。 */ void parseIntArray(int *arr, int *size) { skipSpaces(); (*size) = 0; idxPtr++; /* 跳过 '[' */ skipSpaces(); if (s[idxPtr] == ']') { idxPtr++; return; } while (1) { arr[(*size)++] = parseInt(); skipSpaces(); if (s[idxPtr] == ',') { idxPtr++; continue; } if (s[idxPtr] == ']') { idxPtr++; break; } } } /* 解析 pipes 二维数组，并直接建图。 */ void parsePipeArray() { skipSpaces(); idxPtr++; /* 跳过 '[' */ skipSpaces(); if (s[idxPtr] == ']') { idxPtr++; return; } while (1) { int item[3], size = 0; parseIntArray(item, &size); int u = item[0], v = item[1], type = item[2]; addEdge(u, v); if (type == 1) { addEdge(v, u); } skipSpaces(); if (s[idxPtr] == ',') { idxPtr++; continue; } if (s[idxPtr] == ']') { idxPtr++; break; } } } int main() { if (!fgets(s, sizeof(s), stdin)) { printf("[]"); return 0; } /* 初始化邻接表。 */ for (int i = 0; i < MAXN; i++) { head[i] = -1; } idxPtr = 0; /* 解析最前面的 n。 */ int n = parseInt(); skipSpaces(); if (s[idxPtr] == ',') idxPtr++; /* 解析 sources。 */ int sources[MAXN], sourceCount = 0; parseIntArray(sources, &sourceCount); skipSpaces(); if (s[idxPtr] == ',') idxPtr++; /* 解析 pipes 并建图。 */ parsePipeArray(); /* 从所有源头站同时做 BFS。 */ int visited[MAXN] = {0}; int queue[MAXN]; int front = 0, rear = 0; for (int i = 0; i < sourceCount; i++) { int source = sources[i]; if (!visited[source]) { visited[source] = 1; queue[rear++] = source; } } while (front < rear) { int node = queue[front++]; for (int e = head[node]; e != -1; e = edges[e].next) { int next = edges[e].to; if (!visited[next]) { visited[next] = 1; queue[rear++] = next; } } } /* 输出所有不可达站点。 */ printf("["); int first = 1; for (int i = 0; i < n; i++) { if (!visited[i]) { if (!first) { printf(","); } printf("%d", i); first = 0; } } printf("]"); return 0; }【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集
【华为od机试真题Python】：Python真题题库
【华为od机试真题JavaScript】：JavaScript真题题库
【华为od机试真题Java&Go】：Java&Go真题题库
【华为od机试真题C++】：C++真题题库
【华为od机试真题C语言】：C语言真题题库
【华为od面试手撕代码题库】：面试手撕代码题库
【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】
华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。