(C卷,100分)- 查找接口成功率最优时间段（Java & JS & Python & C）

题目描述

服务之间交换的接口成功率作为服务调用关键质量特性，某个时间段内的接口失败率使用一个数组表示，

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

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

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

输入描述

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

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

输出描述

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

如果同时存在多个最长时间段，则输出多个下标对且下标对之间使用空格(” “)拼接，多个下标对按下标从小到大排序。

用例

题目解析

本题需要求出第二行输入的所有区间，比如0 1 2 3 4区间有

• 0
• 0~1, 1
• 0~2, 1~2, 2
• 0~3, 1~3, 2~3, 3
• 0~4, 1~4, 2~4, 3~4, 4

我们需要计算出这些区间的平均失败率容忍值averageLost，和第一行输入的minAverageLost比较，

如果averageLost > minAverageLost，则不考虑

如果averageLost  <= minAverageLost，则考虑

最后将考虑中所有区间进行比较，保留最长的，注意可能有多个相同时间长度的。

这里模拟出上面区间，很明显需要使用双重for

for(let i=0; i<arr.length; i++) { // 区间右边界，包含
        for(let j=0; j<i; j++) {// 区间左边界，不包含
            
        }
}

这里，我们为了避免陷入遍历i到j，来计算区间[i, j]的总和，我们可以事先定义一个dp数组，dp[i]表示以0~i区间的和（即前缀和）。

因此[j, i]区间总和的计算就是dp[j] – dp[i-1]。

更多前缀和求解任意区间子序列和的知识请看：

同时为了避免计算平均失败率，我们可以计算总最低失败率，即(j – i + 1) * minAverageLost

JavaScript算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const minAverageLost = parseInt(await readline());
  const nums = (await readline()).split(" ").map(Number);

  const n = nums.length;

  const preSum = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    preSum[i] = preSum[i - 1] + nums[i - 1];
  }

  let ans = [];
  let maxLen = 0;

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j <= n; j++) {
      // sum 是 区间 [i, j-1] 的和
      let sum = preSum[j] - preSum[i];
      let len = j - i;
      let lost = len * minAverageLost;

      if (sum <= lost) {
        if (len >= maxLen) {
          if (len > maxLen) {
            ans = [];
          }
          ans.push([i, j - 1]);
          maxLen = len;
        }
      }
    }
  }

  if (ans.length == 0) {
    console.log("NULL");
  } else {
    console.log(
      ans
        .sort((a, b) => a[0] - b[0])
        .map((arr) => arr.join("-"))
        .join(" ")
    );
  }
})();

Java算法源码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int minAverageLost = Integer.parseInt(sc.nextLine());
    int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    System.out.println(getResult(nums, minAverageLost));
  }

  public static String getResult(int[] nums, int minAverageLost) {
    int n = nums.length;

    int[] preSum = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      preSum[i] = preSum[i - 1] + nums[i - 1];
    }

    ArrayList<int[]> ans = new ArrayList<>();
    int maxLen = 0;

    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j <= n; j++) {
        // sum 是 区间 [i, j-1] 的和
        int sum = preSum[j] - preSum[i];
        int len = j - i;
        int lost = len * minAverageLost;

        if (sum <= lost) {
          if (len >= maxLen) {
            if (len > maxLen) {
              ans = new ArrayList<>();
            }
            ans.add(new int[] {i, j - 1});
            maxLen = len;
          }
        }
      }
    }

    if (ans.size() == 0) return "NULL";

    ans.sort((a, b) -> a[0] - b[0]);

    StringJoiner sj = new StringJoiner(" ");
    for (int[] an : ans) sj.add(an[0] + "-" + an[1]);
    return sj.toString();
  }
}

Python算法源码

# 输入获取
minAverageLost = int(input())
nums = list(map(int, input().split()))


# 算法入口
def getResult():
    n = len(nums)

    preSum = [0] * (n + 1)
    for i in range(1, n + 1):
        preSum[i] = preSum[i - 1] + nums[i - 1]

    ans = []
    maxLen = 0
    for i in range(n):
        for j in range(i + 1, n + 1):
            # sumV 是 区间 [i, j-1] 的和
            sumV = preSum[j] - preSum[i]
            length = j - i
            lost = length * minAverageLost

            if sumV <= lost:
                if length > maxLen:
                    ans = [[i, j - 1]]
                    maxLen = length
                elif length == maxLen:
                    ans.append([i, j - 1])

    ans.sort(key=lambda x: x[0])

    if len(ans) == 0:
        return "NULL"
    else:
        return " ".join(map(lambda x: "-".join(map(str, x)), ans))


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 100

int cmp(const void *a, const void *b) {
    int *A = (int *) a;
    int *B = (int *) b;
    return A[0] - B[0];
}

int main() {
    int minAverageLost;
    scanf("%d", &minAverageLost);

    int nums[MAX_SIZE];
    int nums_size = 0;

    while (scanf("%d", &nums[nums_size++])) {
        if (getchar() != ' ') break;
    }

    int preSum[nums_size + 1];
    preSum[0] = 0;

    for (int i = 1; i <= nums_size; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }

    int arrList[MAX_SIZE][2];
    int arrList_size = 0;

    int maxLen = 0;
    for (int i = 0; i < nums_size; i++) {
        for (int j = i + 1; j <= nums_size; j++) {
            // sum 是 区间 [i, j-1] 的和
            int sum = preSum[j] - preSum[i];
            int len = j - i;
            int lost = len * minAverageLost;

            if (sum <= lost) {
                if (len >= maxLen) {
                    if (len > maxLen) {
                        arrList_size = 0;
                    }
                    arrList[arrList_size][0] = i;
                    arrList[arrList_size][1] = j - 1;
                    arrList_size++;
                    maxLen = len;
                }
            }
        }
    }

    if (arrList_size == 0) {
        puts("NULL");
    } else {
        qsort(arrList, arrList_size, sizeof(int *), cmp);

        char res[10000];
        for (int i = 0; i < arrList_size; i++) {
            char tmp[100];
            sprintf(tmp, "%d-%d", arrList[i][0], arrList[i][1]);
            strcat(res, tmp);
            strcat(res, " ");
        }

        res[strlen(res) - 1] = '';

        puts(res);
    }

    return 0;
}