网站制作设计发展前景_企业管理考研院校推荐_搜狗收录提交入口网址_广州关于进一步优化疫情防控措施

华为OD机试真题中的“查找接口成功率最优时间段”是一个典型的算法问题。以下是对该问题的详细解析：

一、题目描述

服务之间交换的接口成功率是服务调用的关键质量特性。某个时间段内的接口失败率使用一个数组表示，数组中每个元素都是单位时间内失败率数值，数组中的数值为0~100的整数。给定一个数值（minAverageLost）表示某个时间段内平均失败率容忍值，即平均失败率小于等于minAverageLost。要求找出数组中最长的时间段，该时间段内的平均失败率小于等于给定的容忍值minAverageLost，如果未找到则直接返回NULL。

二、输入与输出

• 输入：

  • 第一行为minAverageLost，表示平均失败率容忍值。
  • 第二行为数组，表示每个单位时间内的失败率，数组元素通过空格分隔。
  • minAverageLost及数组中元素取值范围为0~100的整数，数组元素的个数不会超过100个。

• 输出：

  • 找出平均值小于等于minAverageLost的最长时间段，输出数组下标对，格式为{beginIndex}-{endIndex}（下标从0开始）。
  • 如果同时存在多个最长时间段，则输出多个下标对，且下标对之间使用空格拼接。多个下标对按下标从小到大排序。

用例：

输入：

1
0 1 2 3 4

输出

0-2

说明：前3个元素的平均值为1，因为数组第一个至第三个数组下标，即0-2

输入

2
0 0 100 2 2 99 0 2 

输出

0-1 3-4 6-7

说明：minAveragerLost=2,数组[0,0,100,2,2,99,0,2] 通过计算小于等于2的最长时段为数组下标为0-1即[0,0],数组下标为3-4即[2,2]数组下标为6-7即[0,2],这三部分都满足平均值小于2的要求，因此输出0-1 3-4 6-7

三、解题思路

1. 读取输入：

   • 使用 Scanner 类读取输入，首先读取一个整数作为 minAverageLost。
   • 然后读取一行字符串，将其按空格分割并转换为整数数组 arr。

2. 初始化变量：

   • 创建一个 ArrayList 来存储满足条件的时间段（下标对）。
   • 使用两个嵌套的循环来遍历数组的所有可能子区间。

3. 遍历所有可能的子区间：

   • 外层循环从数组的第一个元素开始，作为子区间的起始点。
   • 内层循环从当前起始点开始，遍历到数组的末尾，作为子区间的结束点。
   • 在内层循环中，计算当前子区间的失败率之和，并根据子区间的长度计算容忍的失败率之和。
   • 如果当前子区间的失败率之和小于等于容忍值，则将该子区间的起始和结束下标作为一对存储到 ArrayList 中。

4. 排序和筛选最长时间段：

   • 对存储满足条件的时间段的 ArrayList 进行排序。排序规则是先按时间段长度降序排序，如果长度相同，则按起始下标升序排序。
   • 遍历排序后的 ArrayList，找到最长的时间段长度。
   • 再次遍历 ArrayList，筛选出与最长时间段长度相同的时间段，并构建输出字符串。

5. 输出结果：

   • 如果 ArrayList 为空，则输出 NULL。
   • 否则，将筛选出的时间段下标对转换为字符串并输出。

四、示例代码

以下是一个Java实现的示例代码：

import java.util.ArrayList;
import java.util.Scanner;public class InterfaceSuccessRate {public static void main(String[] args) {// 创建扫描器对象以读取输入Scanner scanner = new Scanner(System.in);// 读取输入int minAverageLost = scanner.nextInt();scanner.nextLine(); // 读取换行符String[] inputArray = scanner.nextLine().split(" ");int[] arr = new int[inputArray.length];for (int i = 0; i < inputArray.length; i++) {arr[i] = Integer.parseInt(inputArray[i]);}// 记录满足条件的子区间ArrayList<int[]> validIntervals = new ArrayList<>();// 遍历所有可能的子区间// 遍历数组，以每个元素作为可能的子数组的起始点for (int start = 0; start < arr.length; start++) {int sum = 0;// 从当前起始点开始，遍历到数组的末尾，尝试找到所有可能的子数组for (int end = start; end < arr.length; end++) {// 累加当前子数组的和sum += arr[end];// 计算当前子数组的长度int length = end - start + 1;// 如果当前子数组的平均值小于等于给定的最小平均值，则将该子数组记录为有效区间if (sum <= minAverageLost * length) {validIntervals.add(new int[]{start, end});}}}// 按长度降序排序，长度相同按起始位置升序排序// 对有效的区间列表按照区间长度进行降序排序，如果区间长度相同，则按照区间起始位置升序排序validIntervals.sort((o1, o2) -> {// 计算第一个区间的长度int length1 = o1[1] - o1[0] + 1;// 计算第二个区间的长度int length2 = o2[1] - o2[0] + 1;// 比较两个区间的长度，如果不相同，则按照长度降序排序if (length1 != length2) {return length2 - length1; // 降序} else {// 如果两个区间的长度相同，则按照区间起始位置升序排序return o1[0] - o2[0]; // 升序}});// 输出结果if (validIntervals.isEmpty()) {System.out.println("NULL");} else {// 计算并获取最长有效间隔的长度int maxLength = validIntervals.get(0)[1] - validIntervals.get(0)[0] + 1;// 初始化StringBuilder用于构建结果字符串StringBuilder result = new StringBuilder();// 遍历所有有效间隔，寻找与最长间隔长度相同的间隔for (int[] interval : validIntervals) {// 当前间隔的长度等于最长间隔长度时，将该间隔添加到结果字符串中if (interval[1] - interval[0] + 1 == maxLength) {result.append(interval[0]).append("-").append(interval[1]).append(" ");}}System.out.println(result.toString().trim());}}
}

五、注意事项

1. 边界条件：

   • 处理数组为空或只有一个元素的情况，确保代码能够正确运行并输出 NULL。
   • 在计算子区间时，注意避免数组越界。

2. 时间复杂度：

   • 该算法的时间复杂度为 O(n^2)，其中 n 为数组的长度。由于数组长度不超过 100，因此该算法在实际应用中是可以接受的。然而，如果数组长度非常大，则需要考虑优化算法以降低时间复杂度。

3. 输出格式：

   • 注意输出格式的要求，包括下标对的表示和多个下标对之间的空格分隔。
   • 如果输出结果为空，则确保输出 NULL 而不是空字符串或其他内容。

4. 代码优化：

   • 可以使用滑动窗口算法来优化时间复杂度，将时间复杂度降低到 O(n)。
   • 可以使用哈希表或其他数据结构来存储和快速查找满足条件的时间段。

5. 错误处理：

   • 添加输入验证，确保输入的 minAverageLost 和数组元素都是有效的整数。
   • 处理可能的异常情况，如输入格式不正确或数组元素超出范围等。

运行解析

解析步骤

1、读取输入：

• minAverageLost 为 1。
• 数组 arr 为 [0, 1, 2, 3, 4]。

2、遍历所有可能的子区间：

• 从数组的每个起始点开始，尝试找到所有可能的子数组，并计算其平均值。
• 如果子数组的平均值小于等于 minAverageLost，则将其记录为有效区间。

3、记录有效区间：

• 起始点为 0：
  • 子数组 [0]，平均值为 0，满足条件。
  • 子数组 [0, 1]，平均值为 0.5，满足条件。
  • 子数组 [0, 1, 2]，平均值为 1，满足条件。
  • 子数组 [0, 1, 2, 3]，平均值为 1.5，不满足条件。
  • 子数组 [0, 1, 2, 3, 4]，平均值为 2，不满足条件。
• 起始点为 1：
  • 子数组 [1]，平均值为 1，满足条件。
  • 子数组 [1, 2]，平均值为 1.5，不满足条件。
  • 子数组 [1, 2, 3]，平均值为 2，不满足条件。
  • 子数组 [1, 2, 3, 4]，平均值为 2.5，不满足条件。
• 起始点为 2：
  • 子数组 [2]，平均值为 2，不满足条件。
  • 子数组 [2, 3]，平均值为 2.5，不满足条件。
  • 子数组 [2, 3, 4]，平均值为 3，不满足条件。
• 起始点为 3：
  • 子数组 [3]，平均值为 3，不满足条件。
  • 子数组 [3, 4]，平均值为 3.5，不满足条件。
• 起始点为 4：
  • 子数组 [4]，平均值为 4，不满足条件。

综上所述，有效区间为：

• [0, 0]
• [0, 1]
• [0, 2]
• [1, 1]

4、排序有效区间：

• 按照区间长度降序排序，如果区间长度相同，则按照区间起始位置升序排序。
• 排序后的有效区间为：
  • [0, 2]
  • [0, 1]
  • [0, 0]
  • [1, 1]

5、输出结果：

• 最长有效区间的长度为 3。
• 找到所有长度为 3 的有效区间：
  • [0, 2]
    因此，最终输出为：

0-2