有LeetCode算法/华为OD考试扣扣交流群可加 948025485
可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳od1441
了解算法冲刺训练(备注【CSDN】否则不通过)
文章目录
从2024年4月15号开始,OD机考全部配置为2024D卷。
注意两个关键点:
- 会遇到C卷复用题。虽然可能存在幸存者偏差,但肯定还会有一大部分的旧题。
- 现在又支持做完题目之后倒回去改了。就是可以先做200的再做100的,然后可以反复提交。
题目描述与示例
题目描述
服务之间交换的接口成功率作为服务调用关键质量特性,某个时间段内的接口失败率使用一个数组表示,数组中每个元素都是单位时间内失败率数值,数组中的数值为 0~100
的整数,给定一个数值(minAverageLost
)表示某个时间段内平均失败率容忍值,即平均失败率小于等于 minAverageLost
,找出数组中最长时间段,如果未找到则直接返回 NULL
。
输入描述
输入有两行内容,第一行为minAverageLost
,第二行为数组,数组元素通过空格" "
分隔,minAverageLost
及数组中元素取值范围为 0~100
的整数,数组元素的个数不会超过 100
个。
输出描述
找出平均值小于等于 minAverageLost
的最长时间段,输出数组下标对,格式{beginIndex}-{endIndx}
(下标从 0
开始),如果同时存在多个最长时间段,则输出多个下标对且下标对之间使用空格" "
拼接,多个下标对按下标从小到大排序。
示例一
输入
1
0 1 2 3 4
输出
0-2
说明
A、输入解释:minAverageLost=1
,数组[0, 1, 2, 3, 4]
B、前 3
个元素的平均值为 1
,因此数组第一个至第三个数组下标,即 0-2
示例二
输入
2
0 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]
I ->起始点
i+l ->终止点,最大要取到n
I + l = n
I = n - l
For i in range(0, n-l+1)
这里唯一的难点在于确定起始位置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[i]
# 如果区间和小于等于阈值,则这个区间是满足题意的区间,将其加入ans中
if interval_sum <= threshold:
# 储存的区间是左闭右闭区间,故右边界应该为i+l-1
ans.append(f"{i}-{i+l-1}")
代码
解法一:前缀和
python
# 题目:2023C-查找接口成功率最优时间段
# 分值:100
# 作者:闭着眼睛学数理化
# 算法:前缀和
# 代码有看不懂的地方请直接在群上提问
from 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[i]
# 如果区间和小于等于阈值,则这个区间是满足题意的区间,将其加入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[i] = Integer.parseInt(numStrs[i]);
}
// 调用函数并输出答案
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[i] = 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[i];
// 如果区间和小于等于阈值,则这个区间是满足题意的区间,将其加入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";
}
}
cpp
#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[i];
// 如果区间和小于等于阈值,则这个区间是满足题意的区间,将其加入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[i];
}
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
# 题目:2023C-查找接口成功率最优时间段
# 分值:100
# 作者:闭着眼睛学数理化
# 算法:固定滑窗
# 代码有看不懂的地方请直接在群上提问
# 输入
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[i] = Integer.parseInt(numStrs[i]);
}
// 调用函数并输出答案
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[i];
}
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";
}
}
cpp
#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[i];
}
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[i];
}
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)
。仅需若干长度变量。
华为OD算法/大厂面试高频题算法练习冲刺训练
-
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务300+同学成功上岸!
-
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!
-
60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁
-
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
-
可查看链接 大厂真题汇总 & OD真题汇总(持续更新)
-
绿色聊天软件戳
od1336
了解更多