news 2026/1/26 8:06:54

华为OD机试双机位C卷 - 采样过滤 (C++ Python JAVA JS GO)

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
华为OD机试双机位C卷 - 采样过滤 (C++ Python JAVA JS GO)

采样过滤

2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 200分题型

华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解

题目描述

在做物理实验时，为了计算物体移动的速率，通过相机等工具周期性的采样物体移动距离。由于工具故障，采样数据存在误差甚至错误的情况。需要通过一个算法过滤掉不正确的采样值。

不同工具的故障模式存在差异，算法的各类门限会根据工具类型做相应的调整。

请实现一个算法，计算出给定一组采样值中正常值的最长连续周期。

判断第 i 个周期的采样数据 S[i] 是否正确的规则如下（假定物体移动速率不超过10个单元，前一个采样周期 S[i-1] )：

  • S[i] <= 0，即为错误值
  • S[i] < S[i-1]，即为错误值
  • S[i] - S[i-1] >= 10，即为错误值
  • 其它情况为正常值

判断工具是否故障的规则如下：在M个周期内，采样数据为错误值的次数为T（次数可以不连续），则工具故障。

判断故障恢复的条件如下：产生故障后的P个周期内，采样数据一直为正常值，则故障恢复。

错误采样数据的处理方式:

  • 检测到故障后，丢弃从故障开始到故障恢复的采样数据。
  • 在检测到工具故障之前，错误的采样数据，则由最近一个正常值代替；如果前面没有正常的采样值，则丢弃此采样数据。

给定一段周期的采样数据列表S，计算正常值的最长连续周期。

输入描述

故障确认周期数和故障次数门限分别为M和T，故障恢复周期数为P。

第 i 个周期，检测点的状态为Si

输入为两行，格式如下：

M T P S1 S2 S3 ...

M、T和P的取值范围为[1, 100000]
Si取值范围为[0, 100000]，i 从0开始编号

输出描述

一行输出正常值的最长连续周期

用例1

输入

10 6 3 -1 1 2 3 100 10 13 9 10

输出

8

说明

S[0]，S[4]，S[7]，S[8]为错误值。S[0]之前没有正常的采样数据，丢弃S[0]。S[4]和S[7]不满足故障条件，此值分别由S[3]和S[6]代替，即S[4]为3，S[7]为13。替换后，S[8]小于S[7]，也是错误值。

题解

思路：模拟

这道题就是细节比较多，实际难度不是很高。简单逻辑如下:

  1. 可以使用一个双端队列deque存储发生错误采样位置序号，用来处理判定故障发生的情况。额外注意，判断故障前应先移除队首小于等于 i -m的序号，因为题目要求的判断故障限制在m大小的窗口。

  2. 接下来定义hasLastValid表示这个采样之前是否有正常采样值，lastValidValue记录最近正常采样值。currentLen = 0表示当前正常连续周期数,maxCurrentLen = 0记录最大正常连续周期数。

  3. 接下来就是循环遍历输入检测序列，首先判断当前序列current是否属于发生错误(这部分参照下面代码)：

    • 如果没有发生错误，执行currentLen += 1,hasLastValid = true,lastValidValue = current

    • 如果发生错误，将当前序号插入deque.然后分类处理

      • 如果当前dequeu.size() >= t,说明发生故障，进入故障恢复阶段。
      • 如果当前dequeu.size() < t,此时没有发生故障，分情况处理,以这个作为出发点在检测到工具故障之前，错误的采样数据，则由最近一个正常值代替；如果前面没有正常的采样值，则丢弃此采样数据。
        • hasLastValid == true情况下, 执行currentLen += 1, current = lastValid操作。
        • hasLastValid == false情况下, 不执行操作，因为不会影响currentLen
    1. 按照3的逻辑处理之后，记录下的maxLen就是结果。

c++

#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> #include<deque> using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vector<int> split(const string& str, const string& delimiter) { vector<int> result; size_t start = 0; size_t end = str.find(delimiter); while (end != string::npos) { result.push_back(stoi(str.substr(start, end - start))); start = end + delimiter.length(); end = str.find(delimiter, start); } // 添加最后一个部分 result.push_back(stoi(str.substr(start))); return result; } // 检验当前值是否合法 bool check(int cureent, bool hasLastValid, int lastValidValue) { if (cureent <= 0) return false; if (hasLastValid) { if (cureent < lastValidValue) return false; if (cureent - lastValidValue >= 10) return false; } return true; } int main() { // 窗口大小 窗口出现次数 恢复 int m, t, p; cin >> m >> t >> p; // 忽略换行符 cin.ignore(); string input; getline(cin, input); vector<int> seq = split(input, " "); int n = seq.size(); // 最近一个有效正常值 bool hasLastValid = false; int lastValidValue = 0; // 当前正常连续周期数 int currentLen = 0; // 最大正常连续周期数 int maxLen = 0; // 最近 M 个周期内的错误位置 deque<int> errorWindow; for (int i = 0; i < n; ) { int current = seq[i]; bool isNormal = check(current, hasLastValid, lastValidValue); // 移除超过m窗口的错误 while (!errorWindow.empty() && errorWindow.front() <= i - m) { errorWindow.pop_front(); } // 正常值 if (isNormal) { hasLastValid = true; lastValidValue = current; currentLen++; maxLen = max(currentLen, maxLen); // 异常值 } else { // 加入队列中 errorWindow.push_back(i); // 没有发生故障 if (errorWindow.size() < t) { // 并且前面有效值， 没有的话，应该直接丢弃，不会加长度不处理 if (hasLastValid) { seq[i] = lastValidValue; currentLen++; maxLen = max(currentLen, maxLen); } // 从这里发生故障 } else { // 按照这里逻辑直接进行故障恢复 int j = i + 1; bool recoveryHasLastValid = false; int recoveryLastValidValue = 0; // 连续正常区间个数 int pcount = 0; while (j < n && pcount < p) { int recoveryCurrent = seq[j]; bool recoveryIsNormal = check(recoveryCurrent, recoveryHasLastValid, recoveryLastValidValue); if (recoveryIsNormal) { pcount++; recoveryHasLastValid = true; recoveryLastValidValue = recoveryCurrent; // 连续被终止 } else { pcount = 0; recoveryHasLastValid = false; recoveryLastValidValue = 0; } j++; } // 全部丢弃 currentLen = 0; errorWindow.clear(); // 认定之前没有合法值 hasLastValid = false; lastValidValue = 0; i = j - 1; } } i++; } cout << maxLen << endl; return 0; }

JAVA

import java.util.*; public class Main { // 检验当前值是否合法 static boolean check(int current, boolean hasLastValid, int lastValidValue) { if (current <= 0) return false; if (hasLastValid) { if (current < lastValidValue) return false; if (current - lastValidValue >= 10) return false; } return true; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 窗口大小 窗口出现次数 恢复 int m = sc.nextInt(); int t = sc.nextInt(); int p = sc.nextInt(); sc.nextLine(); // 忽略换行 // 读取采样序列 String line = sc.nextLine(); String[] parts = line.split(" "); int n = parts.length; int[] seq = new int[n]; for (int i = 0; i < n; i++) seq[i] = Integer.parseInt(parts[i]); // 最近一个有效正常值 boolean hasLastValid = false; int lastValidValue = 0; // 当前正常连续周期数 int currentLen = 0; // 最大正常连续周期数 int maxLen = 0; // 最近 M 个周期内的错误位置 Deque<Integer> errorWindow = new LinkedList<>(); for (int i = 0; i < n; ) { int current = seq[i]; boolean isNormal = check(current, hasLastValid, lastValidValue); // 移除超过m窗口的错误 while (!errorWindow.isEmpty() && errorWindow.peekFirst() <= i - m) { errorWindow.pollFirst(); } // 正常值 if (isNormal) { hasLastValid = true; lastValidValue = current; currentLen++; maxLen = Math.max(currentLen, maxLen); // 异常值 } else { // 加入队列中 errorWindow.addLast(i); // 没有发生故障 if (errorWindow.size() < t) { // 并且前面有效值， 没有的话，应该直接丢弃，不会加长度不处理 if (hasLastValid) { seq[i] = lastValidValue; currentLen++; maxLen = Math.max(currentLen, maxLen); } // 从这里发生故障 } else { // 按照这里逻辑直接进行故障恢复 int j = i + 1; boolean recoveryHasLastValid = false; int recoveryLastValidValue = 0; // 连续正常区间个数 int pcount = 0; while (j < n && pcount < p) { int recoveryCurrent = seq[j]; boolean recoveryIsNormal = check(recoveryCurrent, recoveryHasLastValid, recoveryLastValidValue); if (recoveryIsNormal) { pcount++; recoveryHasLastValid = true; recoveryLastValidValue = recoveryCurrent; // 连续被终止 } else { pcount = 0; recoveryHasLastValid = false; recoveryLastValidValue = 0; } j++; } // 全部丢弃 currentLen = 0; errorWindow.clear(); // 认定之前没有合法值 hasLastValid = false; lastValidValue = 0; i = j - 1; } } i++; } System.out.println(maxLen); } }

Python

importsysfromcollectionsimportdeque# 检验当前值是否合法defcheck(current,has_last_valid,last_valid_value):# 当前值 <= 0 为错误值ifcurrent<=0:returnFalseifhas_last_valid:# 如果有上一个正常值，当前值小于上一个也为错误ifcurrent<last_valid_value:returnFalse# 当前值超过上一个正常值 >=10，也为错误ifcurrent-last_valid_value>=10:returnFalsereturnTruedefmain():# 窗口大小 m，窗口出现次数 t，恢复周期 pm,t,p=map(int,sys.stdin.readline().split())# 读取采样序列seq=list(map(int,sys.stdin.readline().split()))n=len(seq)# 最近一个有效正常值has_last_valid=Falselast_valid_value=0# 当前正常连续周期数current_len=0# 最大正常连续周期数max_len=0# 最近 M 个周期内的错误位置error_window=deque()i=0whilei<n:current=seq[i]is_normal=check(current,has_last_valid,last_valid_value)# 移除超过 m 窗口的错误whileerror_windowanderror_window[0]<=i-m:error_window.popleft()# 正常值ifis_normal:has_last_valid=Truelast_valid_value=current current_len+=1max_len=max(max_len,current_len)else:# 异常值加入队列error_window.append(i)# 没有发生故障iflen(error_window)<t:# 前面有正常值，用最近正常值替换ifhas_last_valid:seq[i]=last_valid_value current_len+=1max_len=max(max_len,current_len)# 前面没有正常值，直接丢弃，不增加长度else:# 从这里发生故障，寻找恢复j=i+1recovery_has_last_valid=Falserecovery_last_valid_value=0pcount=0whilej<nandpcount<p:recovery_current=seq[j]recovery_is_normal=check(recovery_current,recovery_has_last_valid,recovery_last_valid_value)ifrecovery_is_normal:pcount+=1recovery_has_last_valid=Truerecovery_last_valid_value=recovery_currentelse:pcount=0recovery_has_last_valid=Falserecovery_last_valid_value=0j+=1# 故障期间丢弃current_len=0error_window.clear()has_last_valid=Falselast_valid_value=0i=j-1# 跳过故障恢复阶段i+=1print(max_len)if__name__=="__main__":main()

JavaScript

// Node 链表节点classNode{constructor(val){this.val=val;this.next=null;this.prev=null;}}// 双端链表 dequeclassDeque{constructor(){this.head=null;this.tail=null;this.size=0;}pushBack(val){letnode=newNode(val);if(!this.tail){this.head=this.tail=node;}else{this.tail.next=node;node.prev=this.tail;this.tail=node;}this.size++;}popFront(){if(!this.head)returnnull;letval=this.head.val;this.head=this.head.next;if(this.head)this.head.prev=null;elsethis.tail=null;this.size--;returnval;}front(){returnthis.head?this.head.val:null;}getSize(){returnthis.size;}}// ACM 模式constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinputLines=[];rl.on('line',(line)=>{inputLines.push(line);}).on('close',()=>{// 解析输入const[m,t,p]=inputLines[0].split(' ').map(Number);constseq=inputLines[1].split(' ').map(Number);constn=seq.length;// 检验当前值是否合法functioncheck(current,hasLastValid,lastValidValue){if(current<=0)returnfalse;if(hasLastValid){if(current<lastValidValue)returnfalse;if(current-lastValidValue>=10)returnfalse;}returntrue;}// 最近一个有效正常值lethasLastValid=false;letlastValidValue=0;// 当前正常连续周期数letcurrentLen=0;// 最大正常连续周期数letmaxLen=0;// 最近 M 个周期内的错误位置，用自定义 deque 保证前端删除 O(1)， 实际机考可能并没这么大数据量，可以先用数组模拟试试leterrorWindow=newDeque();leti=0;while(i<n){letcurrent=seq[i];letisNormal=check(current,hasLastValid,lastValidValue);// 移除超过 m 窗口的错误while(errorWindow.getSize()>0&&errorWindow.front()<=i-m){errorWindow.popFront();}// 正常值if(isNormal){hasLastValid=true;lastValidValue=current;currentLen++;maxLen=Math.max(maxLen,currentLen);}else{// 异常值加入队列中errorWindow.pushBack(i);// 没有发生故障if(errorWindow.getSize()<t){if(hasLastValid){seq[i]=lastValidValue;currentLen++;maxLen=Math.max(maxLen,currentLen);}}else{// 从这里发生故障，寻找恢复letj=i+1;letrecoveryHasLastValid=false;letrecoveryLastValidValue=0;letpcount=0;while(j<n&&pcount<p){letrecoveryCurrent=seq[j];letrecoveryIsNormal=check(recoveryCurrent,recoveryHasLastValid,recoveryLastValidValue);if(recoveryIsNormal){pcount++;recoveryHasLastValid=true;recoveryLastValidValue=recoveryCurrent;}else{pcount=0;recoveryHasLastValid=false;recoveryLastValidValue=0;}j++;}// 故障期间丢弃currentLen=0;errorWindow=newDeque();hasLastValid=false;lastValidValue=0;i=j-1;}}i++;}console.log(maxLen);});

Go

packagemainimport("bufio""container/list""fmt""os""strconv""strings")// 检验当前值是否合法funccheck(currentint,hasLastValidbool,lastValidValueint)bool{ifcurrent<=0{returnfalse}ifhasLastValid{ifcurrent<lastValidValue{returnfalse}ifcurrent-lastValidValue>=10{returnfalse}}returntrue}funcmain(){reader:=bufio.NewReader(os.Stdin)// 窗口大小 窗口出现次数 恢复line1,_:=reader.ReadString('\n')parts:=strings.Fields(line1)m,_:=strconv.Atoi(parts[0])t,_:=strconv.Atoi(parts[1])p,_:=strconv.Atoi(parts[2])line2,_:=reader.ReadString('\n')seqParts:=strings.Fields(line2)n:=len(seqParts)seq:=make([]int,n)fori:=0;i<n;i++{seq[i],_=strconv.Atoi(seqParts[i])}// 最近一个有效正常值hasLastValid:=falselastValidValue:=0currentLen:=0maxLen:=0// 最近 M 个周期内的错误位置，用 container/list 高效 O(1) 删除前端errorWindow:=list.New()i:=0fori<n{current:=seq[i]isNormal:=check(current,hasLastValid,lastValidValue)// 移除超过 m 窗口的错误forerrorWindow.Len()>0{front:=errorWindow.Front()iffront.Value.(int)<=i-m{errorWindow.Remove(front)}else{break}}// 正常值ifisNormal{hasLastValid=truelastValidValue=current currentLen++ifcurrentLen>maxLen{maxLen=currentLen}}else{// 异常值加入队列中errorWindow.PushBack(i)iferrorWindow.Len()<t{ifhasLastValid{seq[i]=lastValidValue currentLen++ifcurrentLen>maxLen{maxLen=currentLen}}}else{// 故障处理，寻找恢复j:=i+1recoveryHasLastValid:=falserecoveryLastValidValue:=0pcount:=0forj<n&&pcount<p{recoveryCurrent:=seq[j]recoveryIsNormal:=check(recoveryCurrent,recoveryHasLastValid,recoveryLastValidValue)ifrecoveryIsNormal{pcount++recoveryHasLastValid=truerecoveryLastValidValue=recoveryCurrent}else{pcount=0recoveryHasLastValid=falserecoveryLastValidValue=0}j++}// 故障期间丢弃currentLen=0errorWindow.Init()hasLastValid=falselastValidValue=0i=j-1}}i++}fmt.Println(maxLen)}
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/1/20 17:47:22

饮食饮水代谢检测系统 呼吸能量饮食饮水代谢检测系统 大鼠代谢系统 小鼠代谢系统

动物代谢监测系统具有多通量、实时统计、自动化、高准确性等优点&#xff0c;极大地提高了药物研发和基础生命科学研究的效率&#xff0c;并从根本上减少手工操作带来数据偏差及误差。在动物无拘束状态下&#xff0c;进行多通道测量,记录软件能实时统计大小鼠的饮食量、饮水量、…

作者头像 李华
网站建设 2026/1/25 18:30:51

智能论文改写工具推荐，8款AI平台助你轻松完成写作

目前市面上有多款AI论文辅助工具&#xff0c;通过对8个主流平台的综合评测发现&#xff0c;这些工具在论文降重、降低AI生成内容检测率以及辅助写作等方面各具特色&#xff0c;根据实际测试结果和用户评价显示&#xff0c;其性能表现主要取决于处理效率、内容准确度及操作便捷性…

作者头像 李华
网站建设 2026/1/23 17:24:17

基于SpringBoot+Spark+vue的在线广告推荐系统

前言 在线广告推荐系统的研究与开发从理论上讲&#xff0c;该系统涉及数据挖掘、机器学习、用户行为分析等多个前沿领域&#xff0c;为研究者提供了一个综合性的研究课题。通过不断优化推荐算法&#xff0c;可以推动相关理论的发展&#xff0c;特别是在大数据处理和实时推荐技术…

作者头像 李华
网站建设 2026/1/21 0:35:16

上位机是什么意思？图文并茂的新手教程

上位机是什么&#xff1f;一文搞懂工业控制中的“大脑”角色你有没有在工厂里见过这样的场景&#xff1a;一个操作员坐在电脑前&#xff0c;轻点几下鼠标&#xff0c;整条生产线就开始有序运转&#xff1b;屏幕上跳动着各种曲线、仪表盘和报警信息&#xff0c;仿佛一切尽在掌握…

作者头像 李华
网站建设 2026/1/19 21:38:56

你了解‌板卡控制的架构吗？‌板卡控制和PLC控制有什么区别

‌板卡控制在智能制造、能源管理、医疗研发等领域均有所使用&#xff0c;由此可见‌板卡控制的重要性。为增进大家对‌板卡控制的认识&#xff0c;本文将对‌板卡控制的架构与功能以及‌板卡控制与PLC控制的区别予以介绍。如果你对‌板卡控制具有兴趣&#xff0c;不妨继续往下阅…

作者头像 李华