华为od机考2025A卷真题 -查找接口成功率最优时间段

CTwZVfsAII

题目描述与示例

题目描述

服务之间交换的接口成功率作为服务调用关键质量特性，某个时间段内的接口失败率使用一个数组表示，数组中每个元素都是单位时间内失败率数值，数组中的数值为 0~100 的整数，给定一个数值(minAverageLost)表示某个时间段内平均失败率容忍值，即平均失败率小于等于 minAverageLost，找出数组中最长时间段，如果未找到则直接返回 NULL。
题目练习网址：https://www.algomooc.com/problem/P3281
输入描述

输入有两行内容，第一行为minAverageLost，第二行为数组，数组元素通过空格" "分隔，minAverageLost 及数组中元素取值范围为 0~100 的整数，数组元素的个数不会超过 100 个。
输出描述

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

输入

10 1 2 3 4输出

0-2说明

A、输入解释：minAverageLost=1，数组[0, 1, 2, 3, 4]
B、前 3 个元素的平均值为 1，因此数组第一个至第三个数组下标，即 0-2
示例二

输入

20 0 100 2 2 99 0 2输出

0-1 3-4 6-7说明

A、输入解释：minAverageLost = 2，数组[0, 0, 100, 2, 2, 99, 0, 2]
B、通过计算小于等于 2 的最长时间段为：数组下标为 0-1 即[0, 0]，数组下标为 3-4 即[2, 2]，数组下标为 6-7 即[0, 2]，这三个部分都满足平均值小于等 2 的要求，因此输出 0-1 3-4 6-7
解题思路

本题数据规模不大，可以用暴力法枚举所有的区间来解决。
暴力法就略去不表，这里主要讲解复杂度较优秀的解法。
贪心思想

由于题目要求我们找到数组中平均失败率小于等于 minAverageLost的中最长时间段，我们贪心地优先从区间长度更大的情况开始考虑。
对于已知长度为n的数组nums而言，其中的连续子区间的长度l的最大值即为n。
故我们可以从n开始到1结束，逆序遍历连续子区间的长度l，即
for l in range(n, 0, -1):    pass一旦发现，对于某一个固定长度l，我们能够找到长度为l的连续区间的区间和的平均值小于等于minAverageLost，则说明我们一定找到的是最长的满足题意的区间。
将除法转换为乘法

由于计算平均值涉及到除法，我们在计算过程中应该尽量地避免除法（尤其是可能出现不整除的情况）。
对于某个特定的l，连续区间的长度已经确定为l，假设连续区间和为interval_sum，那么满足题意的式子interval_sum / l <= minAverageLost可以转化为interval_sum <= minAverageLost * l。
设阈值threshold = minAverageLost * l，我们就可以把问题进一步转化为，求在特定l的情况下，存在哪一些区间满足条件interval_sum <= threshold了。
所以剩下的问题，就是解决如何方便地计算长度为l的连续区间和了。
计算连续子数组的和相关的题目，一般就是使用滑窗或者前缀和来解决。
固定滑窗

对于某一个确定的l值，我们可以使用固定滑窗算法来计算连续区间和（即窗口和）interval_sum。
整个过程的核心代码为
# 计算阈值threshold，# 连续区间和必须小于这个阈值才可以threshold = minAverageLost * l# 初始化第一个窗口的窗口和interval_sum = sum(nums[:l])if interval_sum <= threshold:    ans.append(f"{0}-{l-1}")# 固定滑窗过程for right, num_right in enumerate(nums[l:], l):    # A1    interval_sum += num_right    # A2    interval_sum -= nums[right-l]    # A3    if interval_sum <= threshold:        # 储存的区间是左闭右闭区间，故左边界应该为right-l+1        ans.append(f"{right-l+1}-{right}")前缀和

考虑前缀和技巧。构建前缀和数组为pre_sum（注意前缀和数组的大小比原数组nums多一位，为n+1）。
我们可以枚举所有区间的起始点i，那么所有长度为l的连续区间和可以表示为pre_sum[i+l]-pre_sum
这里唯一的难点在于确定起始位置i的范围。我们可以通过取特殊边界值代入的方式来确定。若

• 选取l = n
  
  
  
  • 原数组仅存在一个连续区间nums[0:n]
    
  • 区间和interval_sum = pre_sum[n]-pre_sum[0]
    
  • i的范围应该是range(0, 1)
    
  • 考虑右边界，1 = n - n + 1 = n - l + 1，故确定区间范围应该是range(0, n-l+1)
    
  
  
• 选取l = 1
  
  
  
  • 考虑原数组最后一个连续区间nums[n-1:n]
    
  • 区间和interval_sum = pre_sum[n]-pre_sum[n-1]
    
  • i的范围应该是range(0, n)
    
  • 考虑右边界，n = n - 1 + 1 = n - l + 1，故确定区间范围应该是range(0, n-l+1)
    
  
  

故整个过程的核心代码为
# 计算阈值threshold，# 连续区间和必须小于这个阈值才可以threshold = minAverageLost * l# 遍历区间的起始位置i，其范围为[0, n-l+1)# 这里的范围，可以用特殊值代入法来确定：# 选取特例l = n，那么n-l+1 = 1# 由于前缀和数组的长度为n+1，因此选取pre_sum[i+l]才不越界for i in range(0, n-l+1):    # 对于每一个区间的起始位置i，我们都需要考虑长度为l的区间[i:i+l]的区间和    # 使用前缀和计算区间和interval_sum    interval_sum = pre_sum[i+l] - pre_sum    # 如果区间和小于等于阈值，则这个区间是满足题意的区间，将其加入ans中    if interval_sum <= threshold:        # 储存的区间是左闭右闭区间，故右边界应该为i+l-1        ans.append(f"{i}-{i+l-1}")代码

解法一：前缀和

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！# 地址：https://www.odalgo.comfrom itertools import accumulate# 输入minAverageLost = int(input())nums = list(map(int, input().split()))# 构建解决问题的函数def solve(minAverageLost, nums):    # 数据长度    n = len(nums)    # 构建前缀和数组，注意首位需要填充一个0，表示不选取任何数字的前缀和    pre_sum = [0] + list(accumulate(nums))    # 构建答案数组    ans = list()    # 逆序遍历区间的长度l，    # 贪心地优先考虑尽可能大的区间    for l in range(n, 0, -1):        # 计算阈值threshold，        # 连续区间和必须小于这个阈值才可以        threshold = minAverageLost * l        # 遍历区间的起始位置i，其范围为[0, n-l+1)        # 这里的范围，可以用特殊值代入法来确定：        # 选取特例l = n，那么n-l+1 = 1        # 由于前缀和数组的长度为n+1，因此选取pre_sum[i+l]才不越界        for i in range(0, n-l+1):            # 对于每一个区间的起始位置i，我们都需要考虑长度为l的区间[i:i+l]的区间和            # 使用前缀和计算区间和interval_sum            interval_sum = pre_sum[i+l] - pre_sum            # 如果区间和小于等于阈值，则这个区间是满足题意的区间，将其加入ans中            if interval_sum <= threshold:                # 储存的区间是左闭右闭区间，故右边界应该为i+l-1                ans.append(f"{i}-{i+l-1}")        # 在考虑大小为l的区间之后，如果ans中有值        # 则说明找到了最长的满足题意的区间，将ans合并后返回输出        if ans:            return " ".join(ans)        # 如果退出循环后，没有返回任何的一个ans，则说明找不到任意一个区间满足题意    # 此时应该返回"NULL"输出    return "NULL"# 调用函数并输出答案print(solve(minAverageLost, nums))Java

import java.util.ArrayList;import java.util.List;import java.util.Scanner;import java.util.StringJoiner;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        // 输入        int minAverageLost = scanner.nextInt();        scanner.nextLine(); // 读取换行符        String line = scanner.nextLine();        String[] numStrs = line.split(" ");        int[] nums = new int[numStrs.length];        for (int i = 0; i < numStrs.length; i++) {            nums = Integer.parseInt(numStrs);        }        // 调用函数并输出答案        System.out.println(solve(minAverageLost, nums));    }    // 构建解决问题的函数    public static String solve(int minAverageLost, int[] nums) {        // 数据长度        int n = nums.length;        // 构建前缀和数组，注意首位需要填充一个0，表示不选取任何数字的前缀和        int[] preSum = new int[n + 1];        for (int i = 1; i <= n; i++) {            preSum = preSum[i - 1] + nums[i - 1];        }        // 构建答案数组        List<String> ans = new ArrayList<>();        // 逆序遍历区间的长度l，        // 贪心地优先考虑尽可能大的区间        for (int l = n; l > 0; l--) {            // 计算阈值threshold，            // 连续区间和必须小于这个阈值才可以            int threshold = minAverageLost * l;            // 遍历区间的起始位置i，其范围为[0, n-l+1)            // 这里的范围，可以用特殊值代入法来确定：            // 选取特例l = n，那么n-l+1 = 1            // 由于前缀和数组的长度为n+1，因此选取preSum[i+l]才不越界            for (int i = 0; i <= n - l; i++) {                // 对于每一个区间的起始位置i，我们都需要考虑长度为l的区间[i:i+l]的区间和                // 使用前缀和计算区间和intervalSum                int intervalSum = preSum[i + l] - preSum;                // 如果区间和小于等于阈值，则这个区间是满足题意的区间，将其加入ans中                if (intervalSum <= threshold) {                    // 储存的区间是左闭右闭区间，故右边界应该为i+l-1                    ans.add(i + "-" + (i + l - 1));                }            }            // 在考虑大小为l的区间之后，如果ans中有值            // 则说明找到了最长的满足题意的区间，将ans合并后返回输出            if (!ans.isEmpty()) {                StringJoiner result = new StringJoiner(" ");                for (String s : ans) {                    result.add(s);                }                return result.toString();            }        }        // 如果退出循环后，没有返回任何的一个ans，则说明找不到任意一个区间满足题意        // 此时应该返回"NULL"输出        return "NULL";    }}C++

#include <iostream>#include <vector>#include <string>#include <sstream>#include <numeric>using namespace std;string solve(int minAverageLost, const vector<int>& nums) {    // 数据长度    int n = nums.size();    // 构建前缀和数组，注意首位需要填充一个0，表示不选取任何数字的前缀和    vector<int> pre_sum(n + 1, 0);    partial_sum(nums.begin(), nums.end(), pre_sum.begin() + 1);    // 构建答案数组    vector<string> ans;    // 逆序遍历区间的长度l，    // 贪心地优先考虑尽可能大的区间    for (int l = n; l > 0; --l) {        // 计算阈值threshold，        // 连续区间和必须小于这个阈值才可以        int threshold = minAverageLost * l;        // 遍历区间的起始位置i，其范围为[0, n-l+1)        // 这里的范围，可以用特殊值代入法来确定：        // 选取特例l = n，那么n-l+1 = 1        // 由于前缀和数组的长度为n+1，因此选取pre_sum[i+l]才不越界        for (int i = 0; i <= n - l; ++i) {            // 对于每一个区间的起始位置i，我们都需要考虑长度为l的区间[i:i+l]的区间和            // 使用前缀和计算区间和interval_sum            int interval_sum = pre_sum[i + l] - pre_sum;            // 如果区间和小于等于阈值，则这个区间是满足题意的区间，将其加入ans中            if (interval_sum <= threshold) {                // 储存的区间是左闭右闭区间，故右边界应该为i+l-1                ans.push_back(to_string(i) + "-" + to_string(i + l - 1));            }        }        // 在考虑大小为l的区间之后，如果ans中有值        // 则说明找到了最长的满足题意的区间，将ans合并后返回输出        if (!ans.empty()) {            string result;            for (size_t i = 0; i < ans.size(); ++i) {                if (i > 0) {                    result += " ";                }                result += ans;            }            return result;        }    }    // 如果退出循环后，没有返回任何的一个ans，则说明找不到任意一个区间满足题意    // 此时应该返回"NULL"输出    return "NULL";}int main() {    int minAverageLost;    // 输入    cin >> minAverageLost;    cin.ignore();  // 忽略换行符    string line;    getline(cin, line);    stringstream ss(line);    vector<int> nums;    int num;    while (ss >> num) {        nums.push_back(num);        if (ss.peek() == ',') {            ss.ignore();        }    }    // 调用函数并输出答案    cout << solve(minAverageLost, nums) << endl;    return 0;}解法二：固定滑窗

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！# 地址：https://www.odalgo.com# 输入minAverageLost = int(input())nums = list(map(int, input().split()))# 构建解决问题的函数def solve(minAverageLost, nums):    # 数据长度    n = len(nums)    # 构建答案数组    ans = list()    # 逆序遍历区间的长度l，    # 贪心地优先考虑尽可能大的区间    for l in range(n, 0, -1):        # 计算阈值threshold，        # 连续区间和必须小于这个阈值才可以        threshold = minAverageLost * l        # 初始化第一个窗口的窗口和        interval_sum = sum(nums[:l])        if interval_sum <= threshold:            ans.append(f"{0}-{l-1}")        # 固定滑窗过程        for right, num_right in enumerate(nums[l:], l):            # A1            interval_sum += num_right            # A2            interval_sum -= nums[right-l]            # A3            if interval_sum <= threshold:                # 储存的区间是左闭右闭区间，故左边界应该为right-l+1                ans.append(f"{right-l+1}-{right}")        if len(ans) > 0:            return " ".join(ans)    # 如果退出循环后，没有返回任何的一个ans，则说明找不到任意一个区间满足题意    # 此时应该返回"NULL"输出    return "NULL"# 调用函数并输出答案print(solve(minAverageLost, nums))Java

import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);                // 输入        int minAverageLost = scanner.nextInt();        scanner.nextLine(); // 读取换行符        String[] numStrs = scanner.nextLine().split(" ");        int[] nums = new int[numStrs.length];        for (int i = 0; i < numStrs.length; i++) {            nums = Integer.parseInt(numStrs);        }        // 调用函数并输出答案        System.out.println(solve(minAverageLost, nums));    }    // 构建解决问题的函数    public static String solve(int minAverageLost, int[] nums) {        // 数据长度        int n = nums.length;        // 构建答案数组        List<String> ans = new ArrayList<>();        // 逆序遍历区间的长度l，        // 贪心地优先考虑尽可能大的区间        for (int l = n; l > 0; l--) {            // 计算阈值threshold，            // 连续区间和必须小于这个阈值才可以            int threshold = minAverageLost * l;            // 初始化第一个窗口的窗口和            int interval_sum = 0;            for (int i = 0; i < l; i++) {                interval_sum += nums;            }            if (interval_sum <= threshold) {                ans.add("0-" + (l - 1));            }            // 固定滑窗过程            for (int right = l; right < n; right++) {                // A1                interval_sum += nums[right];                // A2                interval_sum -= nums[right - l];                // A3                if (interval_sum <= threshold) {                    // 储存的区间是左闭右闭区间，故左边界应该为right-l+1                    ans.add((right - l + 1) + "-" + right);                }            }            if (!ans.isEmpty()) {                return String.join(" ", ans);            }        }        // 如果退出循环后，没有返回任何的一个ans，则说明找不到任意一个区间满足题意        // 此时应该返回"NULL"输出        return "NULL";    }}C++

#include <iostream>#include <vector>#include <string>#include <sstream>#include <algorithm>using namespace std;string solve(int minAverageLost, const vector<int>& nums) {    // 数据长度    int n = nums.size();    // 构建答案数组    vector<string> ans;    // 逆序遍历区间的长度l，    // 贪心地优先考虑尽可能大的区间    for (int l = n; l > 0; --l) {        // 计算阈值threshold，        // 连续区间和必须小于这个阈值才可以        int threshold = minAverageLost * l;        // 初始化第一个窗口的窗口和        int interval_sum = 0;        for (int i = 0; i < l; ++i) {            interval_sum += nums;        }        if (interval_sum <= threshold) {            ans.push_back(to_string(0) + "-" + to_string(l - 1));        }        // 固定滑窗过程        for (int right = l; right < n; ++right) {            // A1            interval_sum += nums[right];            // A2            interval_sum -= nums[right - l];            // A3            if (interval_sum <= threshold) {                // 储存的区间是左闭右闭区间，故左边界应该为right-l+1                ans.push_back(to_string(right - l + 1) + "-" + to_string(right));            }        }        if (!ans.empty()) {            string result;            for (size_t i = 0; i < ans.size(); ++i) {                if (i > 0) {                    result += " ";                }                result += ans;            }            return result;        }    }    // 如果退出循环后，没有返回任何的一个ans，则说明找不到任意一个区间满足题意    // 此时应该返回"NULL"输出    return "NULL";}int main() {    int minAverageLost;    // 输入    cin >> minAverageLost;    cin.ignore();  // 忽略换行符    string line;    getline(cin, line);    stringstream ss(line);    vector<int> nums;    int num;    while (ss >> num) {        nums.push_back(num);        if (ss.peek() == ',') {            ss.ignore();        }    }    // 调用函数并输出答案    cout << solve(minAverageLost, nums) << endl;    return 0;}时空复杂度

时间复杂度：O(N^2)。无论是固定滑窗还是前缀和算法，都需要进行双重循环。
空间复杂度：O(1)。仅需若干长度变量。