训练数据清洗管线（AI022）- 算法机考高频题型 · 华为 AI 岗 / 字符串题解 | AlgoMooc

AI022. 训练数据清洗管线

中等

通过率 33% · 提交 12 · 通过 4

华为 AI 岗字符串哈希模拟

这道 OJ 的配套动画

训练数据清洗管线 · 对应本题的思路、过程和代码

本题改编自算法机考高频题型 · 考点：华为 AI 岗 / 字符串 · 难度：中等

训练数据集有 n 条记录,每条记录是一个不含空白字符的字符串。清洗管线由 q 个步骤组成,按输入顺序逐个执行;每个步骤把一种规则作用于当前整个数据集,完成后再进入下一个步骤。四种规则的含义固定如下: - dedup:去重。按当前字符串值,保留首次出现的记录,删除后续重复记录。 - dropna:删除值恰好为 NULL 或恰好为 - 的记录(区分大小写)。 - short:删除长度小于 3 的记录。 - lower:把每条记录中的大写英文字母改为小写,其他字符不变。执行完全部步骤后,输出剩余记录条数,并按顺序输出前 m 条(不足 m 条则全部输出)。

这类题属于算法机考高频题型中「华为 AI 岗 / 字符串」方向的高频题型，通常考察对「华为 AI 岗 / 字符串」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

第一行输入三个整数 n q m。接下来 n 行,每行输入一条记录。随后 q 行,每行输入一个规则名,取值为 dedup、dropna、short、lower 之一。

输出描述

第一行输出剩余记录条数 r。随后 min(r, m) 行,每行输出一条清洗后的记录,按数据集中的先后顺序。

数据范围

1 <= n <= 100000;0 <= q <= 10;1 <= m <= 100000;记录长度 1 到 30,字符为大小写英文字母、数字、下划线、连字符或点号。

示例

示例 1

输入示例

4 2 10
Cat
cat
NULL
Do
lower
dedup

输出示例

3
cat
null
do

说明：

lower 之后 NULL 变成 null,不再是缺失标记

示例 2

输入示例

4 2 10
NULL
-
abc
abc
dropna
dedup

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

训练营动画视频讲解

训练数据清洗管线

加载中

正在加载动画…

问小欧 · 图解算法年卡¥99 开通 →

题库上一题下一题

未登录也能直接「运行」调试;「提交」判题需微信登录,你写的代码会自动保留、登录后回到本题继续。

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

1
2

# 在此编写你的代码

写完代码点「提交」，将对全部测试用例判题。

⚠️ 这道题的坑 · 易错点与反直觉

这些是真正决定能不能 AC、但通用题解里常被略过的点。

规则合并进一次遍历会破坏顺序语义,NULL→null 逃过 dropna 就是例子
dedup 以执行时刻的值为准:lower 之后 Cat 和 cat 是同一个值
边遍历边删是各语言的经典事故,新建列表接存活记录

解题思路

按照输入顺序逐条执行规则，每条规则都作用于当前的完整数据集。dedup 用集合记录已经出现的字符串并保留首次出现；dropna 只删除恰好等于 NULL 或 - 的记录；short 删除长度小于 3 的记录；lower 只把大写英文字母转换为小写。每执行一条规则，都生成新的记录列表，再进入下一条规则。

正确性说明

主循环严格按照输入次序处理规则，因此每轮的输入正是上一轮的输出。四个分支分别实现题面定义的变换，其中去重按当前字符串值保留首次出现，保持了剩余记录的相对顺序。由规则数归纳可知，全部规则执行后得到的列表与题目要求一致。

复杂度分析

设执行第 i 条规则前记录的总字符数为 L_i，总时间为 O(ΣL_i)，上界可写为 O(qnℓ)，其中 ℓ 为记录最大长度。当前列表、下一轮列表和去重集合最多占 O(nℓ) 空间。

边界与常见错误

q=0 时应直接输出原数据；dropna 区分大小写且要求整串相等；short 的条件是长度严格小于 3。不能把多条规则合并为一次固定顺序的过滤，因为 lower 与 dedup、dropna 的先后次序可能改变结果。

参考代码

# 纯模拟:严格一轮一规则,每条规则线性扫、新建列表接存活记录
# 顺序敏感:lower 在 dropna 前会让 NULL 变 null 逃过删除
import sys


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0]); q = int(data[1]); m = int(data[2])
    records = [data[3 + i].decode() for i in range(n)]
    rules = [data[3 + n + i].decode() for i in range(q)]
    for rule in rules:
        if rule == "dedup":
            seen = set()
            kept = []
            for r in records:
                if r not in seen:
                    seen.add(r)
                    kept.append(r)
            records = kept
        elif rule == "dropna":
            records = [r for r in records if r != "NULL" and r != "-"]
        elif rule == "short":
            records = [r for r in records if len(r) >= 3]
        elif rule == "lower":
            records = [r.lower() for r in records]
    out = [str(len(records))]
    out.extend(records[:m])
    sys.stdout.write("\n".join(out) + "\n")


solve()