目录

题目

思路

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。让他帮助你查询原因。

# java # golang # c语言 # 开发语言
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

53.1.智能投喂器-硬件定时-基于STM32嵌入式物联网单片机软硬件毕业生系统设计【硬件+APP+云平台】

avatar 亚马逊云科技技术品牌专区

CMU 11-785 深度学习导论笔记（一）

神经网络是人工智能中的一种方法，它教会计算机以受人类大脑启发的方式处理数据。近年来，它已成为各种模式识别、预测和分析问题的主要研究方向之一。神经网络在许多问题上确立了最先进的技术水平，并且常常大幅超越之前的基准。上一节我们介绍了神经网络的基本定义，本节中我们来看看神经网络带来的一些突破性应用。语音助手：例如 Siri、Alexa、Google Assistant。视觉与感知：例如人脸检测、人脸识别

avatar 亚马逊云科技技术品牌专区

分布式ID的UUID与自定义时钟

第二，由于ID整体随时间戳递增，数据在存储时具有天然的时间局部性，极大提升了数据库的写入性能与范围查询效率。这种“等待”机制，结合工作节点ID的空间划分，确保了跨节点、跨时间的ID全局唯一且严格递增。反之，如果面对的是海量数据、高并发写入的场景，如电商交易、实时监控、社交网络动态等，那么投入精力构建基于自定义时钟的分布式ID服务，将是保障系统长期稳定与高效运行的关键基础设施投资。在云原生与微服务架

avatar 亚马逊云科技技术品牌专区