当前位置：首页 > news >正文

华为OD机试 - 采样过滤（Java 2024 E卷 100分）

news 2025/6/29 13:00:59

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

在做物理实验时，为了计算物体移动的速度，通过相机和等工具周期性的采样物体移动距离。
由于工具故障，采样数据存在误差甚至丢失。
需要通过一个算法过滤掉不正确的采样值，且不同工具的故障恢复存在差异，算法的各关门限会根据工具类型做相应的调整。

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

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

S[i] <= 0，即为错误值
S[i] < S[i-1]，即为错误值
S[i] - S[i-1] >= 10，即为错误值。

其他情况为正常值。

判断工具是否故障的规则如下：

在 M 个周期内，采样数据为错误值的次数为 T(次数可以不连续)，则工具故障。

判断故障恢复的条件如下：

产生故障后的 P 个周期内，采样数据一直为正常值，则故障恢复。

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

检测到故障后，丢弃从故障开始到故障恢复的采样数据

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

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

二、输入描述

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

第i个周期，检测点的状态为S[i]。

输入为两行，格式如下：

M T P
s1 s2 s3 …

M, T, 和 P 的取值范围为[1, 100000]

S 取值范围为[0, 100000]，从0开始编号

三、输出描述

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

四、测试用例

1、输入

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

2、输出

3、说明

S[0]=-1 为错误，且没有前一个正常值，因此被丢弃。

S[1]=1 到 S[8]=10 中，只有 S[4]=100 和 S[7]=9, S[8]=10 是错误的，但总错误次数 3 < T=6，所以没有发生工具故障。

替换错误数据后，最长连续正常周期为 8。

五、解题思路

为了计算给定一组采样数据中正常值的最长连续周期，我们需要按照题目描述的规则对数据进行过滤，并实时跟踪最长的正常周期。

具体步骤如下：

判断采样数据是否正确：
- 对于每个采样点 S[i]，根据前一个采样点 S[i-1] 来判断其是否正确。
- 第一个采样点 S[0] 仅需满足 S[0] > 0。
维护一个滑动窗口：
- 使用一个固定大小为 M 的循环数组来跟踪最近 M 个周期内的错误次数。
- 当窗口中错误次数达到或超过 T 时，标记工具为故障状态。
处理工具故障：
- 一旦检测到工具故障，开始丢弃数据，直到连续 P 个周期的数据均为正常值，标记工具恢复正常。
- 在故障恢复期间，错误的采样数据被丢弃。
替换错误数据：
- 在工具未故障的情况下，如果检测到错误的采样数据且存在前一个正常值，则用前一个正常值替换错误数据。
- 如果不存在前一个正常值，则丢弃该采样数据。
跟踪最长连续正常周期：
- 在数据过滤的过程中，实时更新当前连续正常周期的长度，并记录最大值。
- 通过上述步骤，可以有效过滤掉错误数据，并计算出最长的连续正常周期。

六、Java算法源码

public class OdTest {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取M, T, Pint M = sc.nextInt();int T = sc.nextInt();int P = sc.nextInt();// 读取所有的采样数据// 由于不知道有多少采样数据，可以使用循环读取直到没有输入// 但根据题目，采样数据在第二行，因此可以先读取整行，再分割sc.nextLine(); // 读取剩余的换行符String[] sStr = sc.nextLine().trim().split("\\s+");int N = sStr.length;int[] S = new int[N];for(int i=0; i<N; i++) {S[i] = Integer.parseInt(sStr[i]);}// 初始化滑动窗口int[] window = new int[M];for(int i=0; i<M; i++) {window[i] = 0;}int window_error_count =0;int window_index =0;// 初始化其他变量Integer last_correct = null;int current_run =0;int max_run =0;boolean fault_state = false;int recovery_counter =0;for(int i=0; i<N; i++) {if(!fault_state) {boolean is_correct;if(i ==0) {is_correct = S[i] >0;}else {is_correct = (S[i] >0) && (S[i] >= S[i-1]) && ((S[i] - S[i-1]) <10);}int new_error_flag = is_correct ? 0 :1;// Update sliding windowwindow_error_count -= window[window_index];window[window_index] = new_error_flag;window_error_count += new_error_flag;window_index = (window_index +1) % M;// Check for faultif(window_error_count >= T) {fault_state = true;recovery_counter =0;current_run =0; // Reset current run as we discard data from now oncontinue; // Discard current data}if(is_correct) {last_correct = S[i];current_run +=1;if(current_run > max_run) {max_run = current_run;}}else {if(last_correct != null) {// 替换错误数据为最后一个正常值current_run +=1;if(current_run > max_run) {max_run = current_run;}}else {// 丢弃此数据current_run =0;}}}else {// Fault state: discard data and check for recoveryboolean is_correct;if(i ==0) {is_correct = S[i] >0;}else {is_correct = (S[i] >0) && (S[i] >= S[i-1]) && ((S[i] - S[i-1]) <10);}if(is_correct) {recovery_counter +=1;if(recovery_counter >= P) {fault_state = false;recovery_counter =0;// 重置滑动窗口for(int j=0; j<M; j++) {window[j] =0;}window_error_count =0;window_index =0;current_run =0;last_correct = null;}}else {recovery_counter =0;}}}System.out.println(max_run);}
}