华为OD刷题C卷 – 每日刷题 19（查找接口成功率最优时间段、最大N个数与最小N个数的和）

1、（查找接口成功率最优时间段）：

这段代码是解决“查找接口成功率最优时间段”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，以及一个辅助方法getSum，用于找出数组中最长的时间段，该时间段内的平均失败率小于等于给定的容忍值minAverageLost。

main方法首先读取失败率容忍值minAverageLost和失败率数组arr，然后调用getResult方法并打印满足条件的最长时间段的下标对。

getResult方法使用双层循环遍历数组arr的所有可能子区间，通过getSum方法计算每个子区间的和，然后根据和与容忍值minAverageLost的关系来判断该子区间是否满足条件。如果满足条件，就更新最长时间段的记录，并存储下标对。最后，将所有满足条件的最长时间段的下标对按从小到大排序并返回。

getSum方法用于计算数组arr从索引start到end的元素之和。

2、（最大N个数与最小N个数的和）：

这段代码是解决“最大N个数与最小N个数的和”的问题。它提供了一个Java类Main，其中包含main方法和getSum方法，用于计算数组中最大N个数与最小N个数的和，同时需要对数组进行去重。

main方法首先读取数组的大小M和数组内容，然后读取需要计算的个数N，接着调用getSum方法并打印结果。

getSum方法首先检查输入的合法性，包括数组是否为空、数字是否在指定范围内。然后，使用HashSet对数组进行去重，并检查去重后的集合大小是否小于2 * N，如果是，则返回-1表示输入非法。接着，将去重后的集合转换为列表并排序。最后，使用双指针技术计算最大N个数与最小N个数的和。

package OD282;
import java.util.*;
/**
* @description 查找接口成功率最优时间段
* @level 6
* @score 100
*/
/**
* 题目描述
* 服务之间交换的接口成功率作为服务调用关键质量特性，某个时间段内的接口失败率使用一个数组表示，
* 

* 数组中每个元素都是单位时间内失败率数值，数组中的数值为0~100的整数，
* 

* 给定一个数值(minAverageLost)表示某个时间段内平均失败率容忍值，即平均失败率小于等于minAverageLost，
* 

* 找出数组中最长时间段，如果未找到则直接返回NULL。
* 

* 输入描述
* 输入有两行内容，第一行为{minAverageLost}，第二行为{数组}，数组元素通过空格(” “)分隔，
* 

* minAverageLost及数组中元素取值范围为0~100的整数，数组元素的个数不会超过100个。
* 

* 输出描述
* 找出平均值小于等于minAverageLost的最长时间段，输出数组下标对，格式{beginIndex}-{endIndx}(下标从0开始)，
* 

* 如果同时存在多个最长时间段，则输出多个下标对且下标对之间使用空格(” “)拼接，多个下标对按下标从小到大排序。
*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//minAverageLost
int minAverageLost = Integer.parseInt(sc.nextLine());
int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
System.out.println(getResult(arr, minAverageLost));
}
//找出平均值小于等于n的最长时间段，输出对应下标 如0-1 3-4 多个下标对按从小到大排序
public static String getResult(int[] arr, int minAverageLost) {
//存放最长时间段 可以有多个
List<int[]> list = new ArrayList<>();
//初始化最大长度
int maxLen = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
//区间[i,j]的和
int sum = getSum(arr, i, j);
int len = j - i + 1;
int lost = len * minAverageLost;
if (sum <= lost) {
//如果len>maxLen 则清空list，并添加最新的，重置maxLen
//如果len=maxLen，则直接添加进list
if (len >= maxLen) {
if (len > maxLen) {
//清空之前maxLen长度的list
list.clear();
}
//然后再添加
list.add(new int[]{i, j});
maxLen = len;
}
}
}
}
//未找到则返回NULL
if (list.isEmpty()) {
return "NULL";
}
//按开始下标升序排序
list.sort(Comparator.comparingInt(a -> a[0]));
//添加进结果
StringJoiner sj = new StringJoiner(" ");
list.forEach(t -> sj.add(t[0] + "-" + t[1]));
//for (int[] temp : list) {
//    sj.add(temp[0] + "-" + temp[1]);
//}
return sj.toString();
}
//从数组中start加到end位置的和
public static int getSum(int[] arr, int start, int end) {
int sum = 0;
for (int i = start; i <= end; i++) {
sum += arr[i];
}
return sum;
}
}

package OD283;
import java.util.*;
/**
* @description 最大N个数与最小N个数的和
* @level 6
*/
/**
* 题目描述
* 给定一个数组，编写一个函数来计算它的最大N个数与最小N个数的和。你需要对数组进行去重。
* 

* 说明：
* 

* 数组中数字范围[0, 1000]
* 最大N个数与最小N个数不能有重叠，如有重叠，输入非法返回-1
* 输入非法返回-1
* 输入描述
* 第一行输入M， M标识数组大小
* 第二行输入M个数，标识数组内容
* 第三行输入N，N表达需要计算的最大、最小N个数
* 输出描述
* 输出最大N个数与最小N个数的和
*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//数字个数
int m = Integer.parseInt(sc.nextLine());
int[] arr = new int[m];
for (int i = 0; i < m; i++) {
arr[i] = sc.nextInt();
}
//最大最小个数
int n = sc.nextInt();
System.out.println(getSum(arr, n));
}
//返回数组中最大最小n个数的和，有重叠返回-1
public static int getSum(int[] arr, int n) {
if (arr == null || arr.length == 0 || n <= 0) {
return -1;
}
//数字范围为0-1000
Set<Integer> set = new HashSet<>();
for (int num : arr) {
if (num < 0 || num > 1000) {
return -1;
}
set.add(num);
}
//去重后如果set的大小小于2n，则一定会重叠
if (set.size() < 2 * n) {
return -1;
}
//排序set中的数
List<Integer> list = new ArrayList<>(set);
Collections.sort(list);
//最大最小n个数的和
int ans = 0;
//左指针
int l = 0;
//右指针
int r = list.size() - 1;
while (n > 0) {
ans += list.get(l) + list.get(r);
l++;
r--;
n--;
}
return ans;
}
}