华为OD机试采样过滤题详解：状态机思路与多语言实现-北京尧图网络

这两年华为OD机试的题目越来越卷但本质考的还是那几个老生常谈的东西逻辑拆解、边界处理、多语言实现能力。C卷的“采样过滤”这道题乍一看就是个数组遍历加状态标记但真上手写的时候不少人在“连续无效数据的起点判定”和“过滤开始时那一条数据到底算不算被丢弃”上翻车。我当初刷这道题的时候也折腾了不少时间这里把完整的思路、多语言实现和踩坑记录整理出来希望对正在备考的朋友有帮助。1. 题目到底在说什么采样过滤的业务场景还原先别急着看代码这个题读不懂题意写出来的代码基本都是错的。题目说的是传感器在持续采样每秒采一个样本点每个样本点包含时间戳和数值。正常来说数据是一条一条记录的但采样过程中会出现两种异常数值无效和数据突跳。数值无效比较好理解就是采集到的值小于0比如传感器信号中断、干扰过大这时候记录下来的数值就是无效的。数据突跳指的是相邻两次采样的数值差不是1比如时间戳对应的数值本该是84、85、86这样递进结果突然出现一个88或90说明中间丢了采样或者数据被污染了。针对这两类异常题目给出了一个过滤条件如果从某个位置开始连续出现了n个无效数据那么从该段无效数据结束后的下一条数据开始进入过滤状态丢弃后面连续的有效数据直到出现连续的u个有效数据才恢复采样。如果从头开始统计当有效数据累积达到m个时同样触发过滤状态丢弃后续数据直到连续u个有效数据出现再恢复。过滤状态下遇到无效数据、突跳数据、以及被丢弃的数据都不输出。只有当恢复正常采样后输出的数据才是有效的。这个场景放到真实系统里非常常见。比如工业现场的传感器采集信号抖动、网络丢包、边缘网关误报都会造成数据质量下降。过滤算法的作用就是把这些“脏数据”挡在门外保证进入上层分析系统的序列是干净的。所以这类题考的不是纯语法而是对“状态机”的理解。2. 核心逻辑拆解有效/无效判定与过滤状态切换我把题目转化成程序逻辑大致分三步。第一步判定每个数据点是否有效。数据点有效需要同时满足两个条件data[i] 0data[i] data[i-1] 1从第二个点开始判断也就是说数值不能是负数且必须和上一个有效数值保持递增1的关系。注意这里的“上一个”指的是时间上的上一条数据不是上一个有效数据。题目说的是“如果数值小于0视为无效如果数值大于等于0需要判断是否等于上一个数值1”这个上一个指的是原始序列中前一个采样值这个细节很多人会理解错。第二步在未过滤状态下判断是否触发过滤。触发过滤有两种情况满足其一即可从当前位置往前看存在一段连续n个无效数据且当前数据是这段连续无效数据结束后的第一条。也就是data[i-n]到data[i-1]全部无效且data[i]是有效的也可能无效无效则继续累积。从数组开头到当前数据累计有效数据个数达到m。这两种情况是或的关系谁先触发谁生效。注意第二种情况里的“有效数据”即使中间有无效数据被跳过只要累计数量到了就触发。第三步过滤状态下何时恢复采样。恢复的条件是连续出现u个有效数据。这u个有效数据本身是需要输出的因为题目说的是“之后才能恢复”也就是连续u个有效数据之后的那条数据才恢复正常采样。这里有个歧义我后面细说我的处理方式。整个逻辑可以用伪代码概括过滤状态 false 实际输出的数据数量 0 当前连续有效数量 0 当前连续无效数量 0 累计有效数量 0 遍历每个数据点 i: 判断 data[i] 是否有效如果过滤状态为 false: 如果 data[i] 无效: 连续无效数量连续有效数量 0 否则: 连续有效数量累计有效数量如果连续无效数量 n 或者累计有效数量 m: 进入过滤状态连续无效数量 0 累计有效数量 0 触发过滤的这条数据按要求处理见下文 continue 否则: 输出 data[i] 对应的信息继续下一个数据否则过滤状态下: 如果 data[i] 有效: 连续有效数量如果连续有效数量 u: 退出过滤状态输出 data[i] 对应的信息连续有效数量 0 否则: 连续有效数量 0有个关键点必须单独说触发过滤时那个位置的判断。我见过很多AC代码是“如果连续n个无效从这条数据开始就不输出了”实际上题目描述通常是“过滤掉该数据之后的连续采样数据”也就是说触发条件成立的当前数据本身不输出下一跳开始丢弃。还有一种理解是当前数据是无效段的一部分本来就不输出。这里需要看具体题面我建议把触发过滤的当前数据也当作不输出的第一跳因为它的状态要么是无效、要么是恰好凑够m个有效的那条这两种情况在题面语境里都应该进入过滤状态而不输出。第三个细节过滤开始时数据个数不足n或m时的处理。题目有一条规定如果采样数据个数小于过滤触发所需的最小值就不需要过滤全部输出。这个case也要处理。3. 五种语言的实现C / Python / Java / JS / Go我分别给出完整实现思路每个版本都按同一套状态机逻辑来写。代码不是唯一的但状态转移一定要对。3.1 C实现C版本我直接用vector存数据遍历的时候带索引计算便于判断连续无效段。核心逻辑封装到一个函数里输入是采样数列和m、n、u输出过滤后的结果。#include iostream #include vector using namespace std; bool isValid(const vectorint data, int i) { if (data[i] 0) return false; if (i 0 data[i] ! data[i-1] 1) return false; return true; } vectorpairint,int filterSamples(const vectorint data, int m, int n, int u) { vectorpairint,int res; int len data.size(); if (len n len m) { for (int i 0; i len; i) res.push_back({i, data[i]}); return res; } bool filtering false; int invalidStreak 0; int validCount 0; int filteredStart -1; for (int i 0; i len; i) { bool curValid isValid(data, i); if (!filtering) { if (!curValid) { invalidStreak; validCount 0; if (invalidStreak n) { filtering true; invalidStreak 0; validCount 0; } } else { // 有效数据但检查是否突跳(已经由isValid保证与前一值相差1) invalidStreak 0; validCount; // 如果累计有效达到m触发过滤 if (validCount m) { filtering true; validCount 0; continue; // 当前这条不输出 } else { res.push_back({i, data[i]}); } } } else { if (!curValid) { invalidStreak 0; // 过滤期间无效数据也清零连续有效继续过滤 // 注意这里无效数据本身也不输出 continue; } else { invalidStreak 0; validCount; if (validCount u) { filtering false; validCount 0; // 恢复时这条输出 res.push_back({i, data[i]}); } } } } return res; }需要注意C判断“连续无效”时我用的办法是累计invalidStreak当它第一次达到n时就触发过滤。因为你无法预先知道哪一段是非法的只能边扫边判断。这样逻辑最线性也好调试。3.2 Python实现Python版本我写得更紧凑一些用布尔变量维护状态判断函数直接用lambda也行但为了可读性还是单独定义。Python的索引操作和切片很方便但别用切片去截断数组一是耗内存二是索引容易乱。def is_valid(data, i): if data[i] 0: return False if i 0 and data[i] ! data[i-1] 1: return False return True def filter_samples(data, m, n, u): if len(data) n and len(data) m: return [(i, data[i]) for i in range(len(data))] filtering False invalid_streak 0 valid_count 0 result [] for i in range(len(data)): cur_valid is_valid(data, i) if not filtering: if not cur_valid: invalid_streak 1 valid_count 0 if invalid_streak n: filtering True invalid_streak 0 valid_count 0 else: invalid_streak 0 valid_count 1 if valid_count m: filtering True valid_count 0 continue else: result.append((i, data[i])) else: if not cur_valid: valid_count 0 continue else: valid_count 1 if valid_count u: filtering False valid_count 0 result.append((i, data[i])) return resultPython写这类题的优势是代码量少但你要特别小心continue的位置。我在触发过滤时加了continue这个continue跳过了后续的result.append说明触发过滤的那条数据不输出。题目如果要求“过滤开始位置的前一条正常输出”那这里的判别逻辑又不一样考场上一定要反复读题。3.3 Java实现Java版本用ArrayList存结果思路一样。Java的强类型有时候会让代码看起来啰嗦但逻辑表达更清晰。import java.util.ArrayList; import java.util.List; public class SampleFilter { public static boolean isValid(int[] data, int i) { if (data[i] 0) return false; if (i 0 data[i] ! data[i-1] 1) return false; return true; } public static Listint[] filterSamples(int[] data, int m, int n, int u) { Listint[] result new ArrayList(); int len data.length; if (len n len m) { for (int i 0; i len; i) result.add(new int[]{i, data[i]}); return result; } boolean filtering false; int invalidStreak 0; int validCount 0; for (int i 0; i len; i) { boolean curValid isValid(data, i); if (!filtering) { if (!curValid) { invalidStreak; validCount 0; if (invalidStreak n) { filtering true; invalidStreak 0; validCount 0; } } else { invalidStreak 0; validCount; if (validCount m) { filtering true; validCount 0; continue; } else { result.add(new int[]{i, data[i]}); } } } else { if (!curValid) { validCount 0; continue; } else { validCount; if (validCount u) { filtering false; validCount 0; result.add(new int[]{i, data[i]}); } } } } return result; } }Java版本的数组和列表转换比较麻烦刷题时我一般直接用ArrayList最后再转int[][]。如果你在OJ上提交记得把类名改成Main方法签名改成public static void main输入输出用Scanner。3.4 JavaScript实现JS版本我用数组模拟判断函数也是一样的。JS没有元组我用对象{index, value}存储输出项。注意JS的Number类型对整数运算没坑但比较时用严格等于。function isValid(data, i) { if (data[i] 0) return false; if (i 0 data[i] ! data[i-1] 1) return false; return true; } function filterSamples(data, m, n, u) { const result []; const len data.length; if (len n len m) { for (let i 0; i len; i) result.push({ index: i, value: data[i] }); return result; } let filtering false; let invalidStreak 0; let validCount 0; for (let i 0; i len; i) { const curValid isValid(data, i); if (!filtering) { if (!curValid) { invalidStreak; validCount 0; if (invalidStreak n) { filtering true; invalidStreak 0; validCount 0; } } else { invalidStreak 0; validCount; if (validCount m) { filtering true; validCount 0; continue; } else { result.push({ index: i, value: data[i] }); } } } else { if (!curValid) { validCount 0; continue; } else { validCount; if (validCount u) { filtering false; validCount 0; result.push({ index: i, value: data[i] }); } } } } return result; }JS在牛客网、华为OD的机考环境里跑Node.js注意输入用readline或者fs.readFileSync数据格式处理要小心。输出的时候把result map成字符串再join。3.5 Go实现Go是我后面补的版本写起来最像C但语法更简洁。Go没有while循环只有for循环变体遍历时用索引。package main import fmt func isValid(data []int, i int) bool { if data[i] 0 { return false } if i 0 data[i] ! data[i-1]1 { return false } return true } func filterSamples(data []int, m, n, u int) [][2]int { result : [][2]int{} length : len(data) if length n length m { for i : 0; i length; i { result append(result, [2]int{i, data[i]}) } return result } filtering : false invalidStreak : 0 validCount : 0 for i : 0; i length; i { curValid : isValid(data, i) if !filtering { if !curValid { invalidStreak validCount 0 if invalidStreak n { filtering true invalidStreak 0 validCount 0 } } else { invalidStreak 0 validCount if validCount m { filtering true validCount 0 continue } else { result append(result, [2]int{i, data[i]}) } } } else { if !curValid { validCount 0 continue } else { validCount if validCount u { filtering false validCount 0 result append(result, [2]int{i, data[i]}) } } } } return result } func main() { data : []int{1, 2, 3, -1, -1, -1, 4, 5, 6, 7, 8} res : filterSamples(data, 4, 3, 2) fmt.Println(res) }Go版本的[2]int在append时注意类型[][2]int等价于“二元组数组”输出格式你自己定义。整体逻辑跟C几乎一一对应花不了多少时间。4. 边界条件与隐藏大坑为什么你的代码总是差一点点这道题在华为OD机试里不算难但通过率不高主要就是边界细节多。我把常见的坑和容易误判的地方列一下基本都是真实考场上会踩的。4.1 连续无效的起点判定第一种触发条件是“连续n个无效数据”这里说的是净连续不含有效数据夹杂。我最开始写的时候惯性思维用了window滑窗后来发现自己搞复杂了。直接线性累积invalidStreak就行关键是触发之后怎么处理。当invalidStreak第一次达到n时说明当前遍历到的位置恰好是连续第n个无效此时从这一条开始进入过滤状态并且这条数据本身不输出。如果你用的是“先收集连续无效数据段再判断段尾后一条”的思路就要小心段尾后一条不存在的情况比如数据末尾刚好是n个无效连续那后面没数据可滤了收尾也要处理好。4.2 m个有效数据触发过滤的数据算不算输出前面我提到这个细节再展开说。累计有效数据达到m时那第m条有效数据本身到底输不输出我按不输出来写理由是这样题目说“当有效采样个数达到m时将从下一个有效采样开始过滤”这个“从下一个有效采样开始”明确把当前这条排除在过滤之外但当前这条是第m条逻辑上它已经完成了“达到m”的使命继续保留会破坏过滤的纯粹性。所以各大题解和我的测试统一为达到m的这条不输出从它后面的数据开始丢弃。如果你的题面描述刚好相反输出就要对应调整考场上要仔细看。4.3 过滤状态下连续有效u个之后恢复采样的那条算不算输出这个和4.2是镜像问题。我按“恢复采样的第一条数据输出”来写因为连续u个有效数据这段区间里的数据是被过滤掉的否则就不算过滤当u个有效数据凑满后恢复采样的标志是从下一条正常数据开始输出。但有些题解把连续u个有效数据的最后一条当作恢复后第一条输出两种理解对结果有影响。我的处理方式在代码里是validCount达到u时立即清除过滤状态并输出当前这条数据这里其实隐含了“当前这第u个有效数据是恢复后的第一条”。如果题目语意是“连续u个之后恢复”那这u个也不输出代码改成把result.append挪到下一轮循环里即可。4.4 数据个数小于n和m时的“免过滤”规则题目通常会有一句“如果采样个数小于n和m则无需过滤”这个我直接在最开始做了长度判断。但要注意这里的小于是“同时小于n和m”不是“或”。如果一个满足一个不满足还是要走完整逻辑。上个月我帮朋友看代码他就漏了这个导致特定case全错。4.5 有效数据的递进判断基准data[i] data[i-1] 1这个条件基准是原始数组中的前一个位置不是前一个有效输出。比如[1, 2, -1, 4]4的有效性判断是看它是否等于-1 1也就是是否等于0显然4不等于0所以4无效。这一点很容易被误解成“跳过无效值后做递进判断”千万别搞混。因为题目描述里强调的是采样数值的连续递增关系如果中途出现无效值递进关系就被打破了。4.6 过滤期间无效数据的处理过滤状态下如果遇到无效数据我代码里是validCount 0然后continue不输出。这里有个隐含逻辑无效数据不会帮助恢复采样也不会延长过滤时长它只是被打断的“连续有效”计数。有些新手会在过滤状态下无效数据触发新的“连续无效n”判断造成状态叠加完全没有必要。过滤状态已经把所有数据都拦截了不需要再判断是否进入新的过滤。4.7 相邻差值判断的边界第一个数据点没有前驱所以只看它是否小于0。如果第一个点就是负数直接无效并启动无效累积如果第一个点非负无条件算有效。这个细节在测试用例里经常用[0, 2, 3]这类数据来卡2不等于01所以从2开始就是突跳需要被丢弃。4.8 连续无效的区间跨越多个阶段比如数据是[1, -1, -2, -3, 5, 6]n3这里-1、-2、-3是连续无效5开始进入过滤6也被滤掉。但注意如果n2那-1、-2就触发过滤了-3也顺带被滤掉5、6也一样。不同n导致过滤起点不同结果差异很大。测试时建议把n变小验证边界是否正确触发。5. 测试用例设计与验证思路模拟华为OD的判题逻辑刷这类题最重要的不是背代码而是会构造测试用例自测。这里弄一组覆盖主要场景的测试数据你们拿到代码后可以直接跑。用例1正常数据无过滤触发数据[1, 2, 3, 4, 5]m6n3u2 结果数据个数小于m且小于n全部输出。用例2连续无效过滤数据[1, 2, -1, -2, -3, 5, 6, 7]m10n3u2 预期1、2正常输出-1、-2无效不输出到-3时连续无效满3触发过滤-3不输出5、6过滤中不输出7有效连续有效u2还需要一个所以7先不输出如果后面还有8则8恢复后输出用例3m触发过滤数据[1, 2, 3, 4, 5, 6, 7]m4n5u2 预期1、2、3正常输出4是第4个有效数据累满m触发过滤4不输出5、6过滤中5不输出6有效开始计数17有效计数2达到u恢复7输出这个case网上经常能搜到本质是考察m触发边界的。用例4多个过滤区间连续出现数据[1, -1, -2, 3, 4, -3, -4, 5, 6, 7]m10n2u2 预期1正常-1无效连续无效1不输出-2无效连续无效2触发过滤不输出3有效过滤状态计数1不输出4有效计数2恢复4输出-3无效未过滤状态下无效计数1-4无效计数2触发过滤5、6过滤中5计数16计数26恢复这里注意6满足连续有效2所以6输出7未过滤状态正常输出这个用例能测出连续两个过滤区间能否正确衔接。用例5开头就是无效段数据[-1, -2, -3, 1, 2, 3]m5n3u2 预期-1、-2无效-3触发过滤1、2过滤中2有效计数13有效计数2恢复3输出如果开始时过滤没有触发过要考虑数组头部连续无效段直接启动过滤的情况。代码里的逻辑是遍历到-3自动进入过滤不需要额外初始化我的实现已经处理。用例6m和n在同一位置同时满足数据[1, 2, -1, -2, 3, 4, 5]m3n2u1 预期1有效有效计数1输出2有效有效计数2输出-1无效无效1-2无效无效2触发过滤同时有效计数还是2未到3所以n先触发3过滤中有效计数1u1恢复3输出4正常状态有效计数1输出5正常状态有效计数2输出注意m和n同时满足时边界顺序很重要。我的代码是先判断无效触发再判断有效触发也就是n优先。如果题目要求m优先结果可能不同这也是题目描述里容易隐藏的一个点。6. 如何调试和优化从30分钟到10分钟的思路转变我刚开始写这道题用了滑窗辅助数组把每个位置之前的连续无效数和累计有效数都预处理出来写了大几十行各种 index 错位。后来发现这道题根本不需要预处理直接在线性遍历过程中维护两个计数器就行。关于滑窗的错误直觉很多人一看到“连续”两个字就想滑窗但这题没有窗口求和的需求只需要“是否达到阈值”。线性计数器够用维护成本低。滑窗反而要处理窗口出界和触发后的重置增加了不必要的复杂度。关于递归完全没必要。状态只依赖当前数据和上一数据是典型的迭代场景。用递归反而要自己管理栈帧和参数传递容易爆栈。代码优化的方向尽量减少分支嵌套。我现在的写法是“非过滤状态”和“过滤状态”两个主分支每个分支内部再细分有效无效逻辑已经比较扁了。把isValid单独抽出来不管是C、Python还是Java都能让主流程更清晰也方便单独测试每个数据点的有效性。m和n的判断统一用而不是因为触发条件理论上可以重复用防止特殊情况漏判。过滤状态下invalidStreak要不要维护答案是不要。过滤期间所有数据都不放行无效数据只是打断连续有效计数至于无效了几个、够不够n完全没有意义因为已经在过滤状态里了。很多超时的代码就是在这里做重复维护。还有一点输出格式。华为OD机试对输出格式要求非常严格时间戳和数值之间用分号还是空格、每条数据之间怎么隔开都要和题目完全一致。我在本地调试时写了个小的打印函数def print_result(res): if not res: print(empty) else: print(; .join(f{idx}:{val} for idx, val in res))真实考试里不要自己发明格式看清楚样例输出再写打印逻辑。7. 从这道题看华为OD机试的评分逻辑与答题策略华为OD机试不是只看最终答案正确率还会看代码可读性、变量命名、边界覆盖情况和运行时间。尤其是C卷越来越接近实际工作场景考察的不仅是编码能力更是逻辑完备性。我总结了一下几类人在这道题上的典型丢分点不读题直接上手写代码导致过滤触发时机错误这是最大的失分来源。边界条件没人肉测试像数据个数小于n和m的免过滤分支经常被漏掉。多语言实现时语法特性影响逻辑比如JS的隐式类型转换导致比较出错Java的数组越界问题没处理好。时间空间复杂度超标比如用递归或者反复截断数组在大数据量下超时。我给备考的人一个建议在硬刷题之前先画状态转移图。不需要多专业就画两个圆圈一个叫“正常采样”一个叫“过滤采样”然后标出什么条件下从正常到过滤、什么条件下从过滤回正常。能不能把这张图画对基本决定了你代码能不能一次写对。我画这个图大概用了两分钟后来看别人总结的“状态机”方法才发现自己无意中走对了路。状态转移其实很简单正常状态遇到无效数据累积够n - 过滤有效数据累积够m - 过滤过滤状态连续有效数据够u - 恢复正常除此之外一切数据都不输出。这张图就是整道题的灵魂。8. 总结之外的一点私货这类题目在工作里真的有用吗最后说点题外话。采样过滤这个模型和我在实际工作中见过的时序数据清洗逻辑几乎一摸一样。有个项目是接工业设备传感器数据设备会上报温度、压力、转速等指标经常出现负值或者数值跳变我们当时写的过滤规则就是类似的连续无效阈值和跳变判定。只不过真实系统里还会加上阈值上下限、限幅滤波、中值滤波这些组合策略但核心的“状态机过滤”思想没变。所以不要觉得这只是一道面试题它背后的“数据质量判断”“异常窗口处理”“恢复正常采样”这些设计放在数据管道、监控告警、物联网平台上都是基础技能。把一道机试题吃透作用不仅是过考试后期做项目也会更顺手。回到题目本身如果你在手写代码前能先确认那几个模糊细节——触发过滤的当前数据是否输出、u个有效数据后恢复时怎么算、数据个数小于阈值时怎么处理你的代码大概率一遍就能过。剩下的无非是把状态机用你熟悉的语言翻译一遍。我花在调试这道题上的时间大部分是浪费在对“连续无效段结束后的下一条数据”和二义性文字的理解上。等到把题目用自己的话复述清楚、画出状态图之后编码基本十分钟搞定。所以如果你现在卡在代码上先把题目放一边写清楚输入输出和状态变化再回来写代码效果会好很多。

华为OD机试采样过滤题详解：状态机思路与多语言实现

相关推荐

libevent编译成功运行却报错？一文搞懂Linux动态链接库加载机制

华为路由器交换机VLAN配置实例：从VLAN划分到ACL排错

MongoDB热点数据缓存击穿：从识别到两级缓存优化实战

更多资讯

ARM64 CentOS 7手工安装MySQL 5.7实战：从二进制包到systemd全流程

OpenHarmony上适配dcli_common：构建鸿蒙CLI工具链实践

插件加载失败排查指南：从IAR到Harness与MusicFree的实战解析

Win11 安装配置 Node.js 完全指南：从 LTS 到环境变量与 npm 提速

Supabase RLS实战：公开读、投稿写、待审核可见的权限策略

408计算机网络复习：三层协议栈考点梳理与CRC/CIDR手算通关

今日更新

插件加载失败深度解析：从did not activate到生命周期排查指南

SpringBoot+Vue+MyBatis企业级房屋租赁管理系统源码解析

企业核心数据灾备自动化：用 OpenClaw 备份到本地 + 云端 + 离线存储的 TaoToken 统一通道实践

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？