華為OD機試真題——查找接口成功率最優時間段（2025A卷：100分）Java/python/JavaScript/C/C++/GO最佳實現

在這里插入圖片描述

2025 A卷 100分 題型

本專欄內全部題目均提供Java、python、JavaScript、C、C++、GO六種語言的最佳實現方式；
并且每種語言均涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、3個測試用例以及綜合分析；
本文收錄于專欄：《2025華為OD真題目錄+全流程解析+備考攻略+經驗分享》

華為OD機試真題《查找接口成功率最優時間段》：

文章快捷目錄

題目描述及說明

Java

python

JavaScript

C

GO

更多內容

題目名稱：查找接口成功率最優時間段

知識點： 滑動窗口、前綴和、邏輯處理
時間限制： 1秒
空間限制： 256MB
限定語言： 不限

題目描述

服務之間交換的接口成功率作為服務調用關鍵質量特性，某個時間段內的接口失敗率使用一個數組表示，數組中每個元素都是單位時間內失敗率數值，數組中的數值為0~100的整數。給定一個數值minAverageLost表示某個時間段內平均失敗率容忍值（即平均失敗率需小于等于該值），要求找出數組中滿足條件的最長時間段，若未找到則返回NULL。

輸入描述：

  • 第一行為minAverageLost。
  • 第二行為數組，元素通過空格分隔。
  • minAverageLost及數組元素取值范圍為0~100的整數，數組長度不超過100。

輸出描述：

  • 輸出所有滿足條件的最長時間段下標對，格式為{beginIndex}-{endIndex}（下標從0開始）。
  • 若存在多個相同長度的最優時間段，按起始下標從小到大排序，并用空格拼接。

用例：

  1. 輸入：

    1  
0 1 2 3 4

    輸出：

    0-2

    說明：前3個元素的平均值為1，滿足條件。

  2. 輸入：

    2  
0 0 100 2 2 99 0 2

    輸出：

    0-1 3-4 6-7

    說明：下標0-1、3-4、6-7對應的子數組平均值均≤2，且均為最長時段。

Java

問題分析

我們需要找到數組中所有滿足平均失敗率小于等于給定值的最長連續子數組，并輸出這些子數組的起始和結束下標。如果有多個相同長度的子數組，按起始下標升序排列。

解題思路

  1. 轉換數組：將每個元素減去給定的平均失敗率，問題轉化為尋找子數組的和小于等于0的最長長度。
  2. 前綴和數組：計算轉換后數組的前綴和，便于快速計算子數組的和。
  3. 遍歷所有可能的子數組：對于每個可能的結束下標，遍歷所有可能的起始下標，記錄滿足條件的最長子數組。
  4. 收集結果：記錄所有最長的子數組，按起始下標排序后輸出。

代碼實現

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int minAverageLost = Integer.parseInt(scanner.nextLine());String[] parts = scanner.nextLine().split(" ");int[] nums = new int[parts.length];for (int i = 0; i < parts.length; i++) {nums[i] = Integer.parseInt(parts[i]);}// 轉換為每個元素減去minAverageLost的數組int[] b = new int[nums.length];for (int i = 0; i < nums.length; i++) {b[i] = nums[i] - minAverageLost;}// 計算前綴和數組int[] prefixSum = new int[b.length + 1];for (int i = 0; i < b.length; i++) {prefixSum[i + 1] = prefixSum[i] + b[i];}int maxLen = 0;List<int[]> result = new ArrayList<>();// 遍歷所有可能的結束下標jfor (int j = 0; j < b.length; j++) {// 遍歷所有可能的起始下標ifor (int i = 0; i <= j; i++) {// 檢查子數組i到j的和是否<=0if (prefixSum[j + 1] <= prefixSum[i]) {int currentLen = j - i + 1;if (currentLen > maxLen) {maxLen = currentLen;result.clear();result.add(new int[]{i, j});} else if (currentLen == maxLen) {result.add(new int[]{i, j});}}}}if (maxLen == 0) {System.out.println("NULL");return;}// 按起始下標排序Collections.sort(result, (a, bArr) -> {if (a[0] != bArr[0]) {return a[0] - bArr[0];} else {return a[1] - bArr[1];}});// 使用LinkedHashSet去重并保持順序LinkedHashSet<String> seen = new LinkedHashSet<>();for (int[] interval : result) {seen.add(interval[0] + "-" + interval[1]);}// 輸出結果System.out.println(String.join(" ", seen));}
}

代碼詳細解析

  1. 輸入處理：讀取輸入的平均失敗率和數組。
  2. 數組轉換：將每個元素減去平均失敗率，轉換為新數組b。
  3. 前綴和計算：構建前綴和數組prefixSum，用于快速計算子數組的和。
  4. 遍歷子數組：雙重循環遍歷所有可能的起始和結束下標，檢查子數組的和是否滿足條件。
  5. 記錄最長子數組：動態更新最長長度，并記錄所有符合條件的子數組。
  6. 結果排序與去重：按起始下標排序，使用LinkedHashSet去重并保持順序。
  7. 輸出結果：拼接結果字符串并輸出。

示例測試

示例1輸入：
1  
0 1 2 3 4

輸出：

0-2
示例2輸入：
2  
0 0 100 2 2 99 0 2

輸出：

0-1 3-4 6-7
示例3輸入：
3  
1 1 1

輸出：

0-2

綜合分析

  1. 時間復雜度：O(n2)，遍歷所有可能的子數組，適用于數組長度較小的情況（n ≤ 100）。
  2. 空間復雜度：O(n)，存儲前綴和數組和結果列表。
  3. 優勢：利用前綴和數組快速計算子數組的和，確保正確性和效率。
  4. 適用場景：適用于需要查找連續子數組滿足特定條件的場景，如平均值、和等限制。

python

問題分析

我們需要找到數組中所有滿足平均失敗率 ≤ 給定值的最長連續子數組，并輸出這些子數組的起始和結束下標。如果有多個相同長度的子數組，按起始下標升序排列。

解題思路

  1. 數學轉換：
    將問題轉換為：尋找子數組的和 ≤ 0 的最長連續區間（原數組每個元素減去平均值后的新數組）。

  2. 前綴和數組：
    計算新數組的前綴和，利用前綴和快速判斷子數組的和是否 ≤ 0。

  3. 暴力遍歷：
    遍歷所有可能的子數組，記錄滿足條件的最長區間。

  4. 結果處理：
    去重并排序結果，按指定格式輸出。

代碼實現

def main():import sysinput = sys.stdin.read().splitlines()min_avg = int(input[0].strip())  # 讀取容忍值arr = list(map(int, input[1].strip().split()))  # 讀取失敗率數組# 轉換為差值數組（元素 - 容忍值）diff = [num - min_avg for num in arr]n = len(diff)# 計算前綴和數組（多一位方便計算）prefix = [0] * (n + 1)for i in range(n):prefix[i+1] = prefix[i] + diff[i]max_len = 0result = []# 遍歷所有可能的子數組for end in range(n):for start in range(end + 1):# 子數組和是否 <= 0（prefix[end+1] <= prefix[start]）if prefix[end+1] <= prefix[start]:current_len = end - start + 1if current_len > max_len:max_len = current_lenresult = [(start, end)]elif current_len == max_len:result.append((start, end))if max_len == 0:print("NULL")return# 去重并排序（起始下標升序）unique = sorted(list(set(result)), key=lambda x: (x[0], x[1]))# 格式化輸出output = ' '.join([f"{s}-{e}" for s, e in unique])print(output)if __name__ == "__main__":main()

代碼詳細解析

1. 輸入處理
min_avg = int(input[0].strip())  # 讀取容忍值
arr = list(map(int, input[1].strip().split()))  # 讀取失敗率數組
  • 第一行為容忍值 min_avg。
  • 第二行為空格分隔的失敗率數組。
2. 數學轉換
diff = [num - min_avg for num in arr]
  • 將每個元素減去容忍值，轉換為新數組 diff。問題轉化為：尋找 diff 中子數組和 ≤ 0 的最長區間。
3. 前綴和計算
prefix = [0] * (n + 1)
for i in range(n):prefix[i+1] = prefix[i] + diff[i]
  • 構建前綴和數組 prefix，其中 prefix[i] 表示原數組前 i 個元素的和。
  • 例如：diff[1..3] 的和 = prefix[4] - prefix[1]。
4. 暴力遍歷所有子數組
for end in range(n):for start in range(end + 1):if prefix[end+1] <= prefix[start]:current_len = end - start + 1if current_len > max_len:max_len = current_lenresult = [(start, end)]elif current_len == max_len:result.append((start, end))
  • 外層循環遍歷子數組的結束下標 end。
  • 內層循環遍歷子數組的起始下標 start。
  • 通過前綴和判斷 diff[start..end] 的和是否 ≤ 0。
  • 動態更新最長長度和結果列表。
5. 結果處理
unique = sorted(list(set(result)), key=lambda x: (x[0], x[1]))
output = ' '.join([f"{s}-{e}" for s, e in unique])
  • 使用 set 去重重復的區間。
  • 按起始下標升序、結束下標升序排序。
  • 格式化為 0-2 形式拼接輸出。

示例測試

示例1輸入：
1  
0 1 2 3 4

輸出：

0-2

解析：
子數組 [0,1,2] 的平均值為 1，滿足條件，長度為3，是唯一最長。

示例2輸入：
2  
0 0 100 2 2 99 0 2

輸出：

0-1 3-4 6-7

解析：

  • 0-1 平均值 0
  • 3-4 平均值 2
  • 6-7 平均值 1
    均為長度2的最長區間。
示例3輸入：
3  
1 1 1

輸出：

NULL

解析：
所有子數組的平均值均為 1，無法滿足容忍值 3。

綜合分析

  1. 時間復雜度：O(n2)

    • 雙重循環遍歷所有可能的子數組，適用于 n ≤ 100 的題目限制。

  2. 空間復雜度：O(n)

    • 存儲前綴和數組和結果列表，空間與數組長度成線性關系。

  3. 優勢：

    • 避免浮點運算：通過前綴和與差值數組，用整數運算判斷條件。
    • 代碼簡潔：利用Python的列表推導和排序函數簡化邏輯。

  4. 適用場景：

    • 需要查找滿足條件的連續子數組，且輸入規模較小的場景。

JavaScript

問題分析

我們需要找到數組中所有滿足平均失敗率 ≤ 給定值的最長連續子數組，并輸出這些子數組的起始和結束下標。如果有多個相同長度的子數組，按起始下標升序排列。

解題思路

  1. 數學轉換：將每個元素減去容忍值，問題轉化為尋找子數組的和 ≤ 0 的最長區間。
  2. 前綴和數組：計算轉換后的數組的前綴和，快速判斷子數組的和是否滿足條件。
  3. 暴力遍歷：遍歷所有可能的子數組，記錄滿足條件的最長區間。
  4. 結果處理：按起始下標排序后輸出。

代碼實現

const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout,terminal: false
});let lines = [];
rl.on('line', (line) => {lines.push(line.trim());
});rl.on('close', () => {const minAverageLost = parseInt(lines[0]);const arr = lines[1].split(' ').map(Number);const n = arr.length;// 轉換為差值數組（元素 - 容忍值）const diff = arr.map(num => num - minAverageLost);// 計算前綴和數組const prefixSum = [0];for (let i = 0; i < n; i++) {prefixSum.push(prefixSum[i] + diff[i]);}let maxLen = 0;const result = [];// 遍歷所有可能的子數組for (let end = 0; end < n; end++) {for (let start = 0; start <= end; start++) {const sum = prefixSum[end + 1] - prefixSum[start];if (sum <= 0) {const currentLen = end - start + 1;if (currentLen > maxLen) {maxLen = currentLen;result.length = 0; // 清空舊結果result.push([start, end]);} else if (currentLen === maxLen) {result.push([start, end]);}}}}if (maxLen === 0) {console.log('NULL');return;}// 按起始下標排序result.sort((a, b) => a[0] - b[0] || a[1] - b[1]);// 轉換為字符串輸出const output = result.map(pair => `${pair[0]}-${pair[1]}`).join(' ');console.log(output);
});

代碼詳細解析

  1. 輸入處理：

    • readline 逐行讀取輸入，存入 lines 數組。
    • minAverageLost 讀取為整數，arr 讀取為整數數組。

  2. 數學轉換：

    const diff = arr.map(num => num - minAverageLost);
    • 將每個元素減去容忍值，轉換為差值數組。

  3. 前綴和計算：

    const prefixSum = [0];
for (let i = 0; i < n; i++) {prefixSum.push(prefixSum[i] + diff[i]);
}
    • 構建前綴和數組 prefixSum，用于快速計算子數組的和。

  4. 暴力遍歷子數組：

    for (let end = 0; end < n; end++) {for (let start = 0; start <= end; start++) {const sum = prefixSum[end + 1] - prefixSum[start];if (sum <= 0) {const currentLen = end - start + 1;// 更新最長結果}}
}
    • 雙重循環遍歷所有子數組，計算子數組的和是否 ≤ 0。
    • 動態更新最長長度和結果數組。

  5. 結果處理：

    result.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const output = result.map(pair => `${pair[0]}-${pair[1]}`).join(' ');
    • 按起始下標排序，轉換為字符串格式輸出。

示例測試

示例1輸入：
1  
0 1 2 3 4

輸出：

0-2
示例2輸入：
2  
0 0 100 2 2 99 0 2

輸出：

0-1 3-4 6-7
示例3輸入：
3  
1 1 1

輸出：

NULL

綜合分析

  1. 時間復雜度：O(n2)

    • 雙重循環遍歷所有子數組，適用于輸入規模較小（數組長度 ≤ 100）的場景。

  2. 空間復雜度：O(n)

    • 存儲前綴和數組和結果數組，空間與輸入規模成線性關系。

  3. 優勢：

    • 避免浮點運算：通過差值數組和前綴和，用整數運算快速判斷條件。
    • 嚴格順序處理：確保結果按起始下標排序。

  4. 適用場景：

    • 需要快速處理連續子數組的平均值問題的場景。

C++

問題分析

我們需要找到數組中所有滿足平均失敗率 ≤ 給定值的最長連續子數組，并輸出這些子數組的起始和結束下標。如果有多個相同長度的子數組，按起始下標升序排列。

解題思路

  1. 數學轉換：
    將問題轉換為：尋找子數組的和 ≤ 0 的最長連續區間（原數組每個元素減去平均值后的新數組）。

  2. 前綴和數組：
    計算新數組的前綴和，利用前綴和快速判斷子數組的和是否 ≤ 0。

  3. 暴力遍歷：
    遍歷所有可能的子數組，記錄滿足條件的最長區間。

  4. 結果處理：
    去重并排序結果，按指定格式輸出。

代碼實現

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>using namespace std;int main() {// 讀取輸入int minAverageLost;cin >> minAverageLost;cin.ignore(); // 忽略換行符string line;getline(cin, line);    // 讀取數組行istringstream iss(line);vector<int> nums;int num;while (iss >> num) {   // 解析數組元素nums.push_back(num);}int n = nums.size();if (n == 0) {          // 處理空數組cout << "NULL" << endl;return 0;}// 轉換為差值數組（元素 - 容忍值）vector<int> diff(n);for (int i = 0; i < n; ++i) {diff[i] = nums[i] - minAverageLost;}// 計算前綴和數組vector<long long> prefixSum(n + 1, 0);for (int i = 0; i < n; ++i) {prefixSum[i + 1] = prefixSum[i] + diff[i];}int maxLen = 0;vector<pair<int, int>> result; // 存儲所有滿足條件的區間// 遍歷所有可能的子數組for (int end = 0; end < n; ++end) {for (int start = 0; start <= end; ++start) {// 檢查子數組的和是否 <= 0if (prefixSum[end + 1] <= prefixSum[start]) {int currentLen = end - start + 1;if (currentLen > maxLen) {maxLen = currentLen;result.clear();       // 清空舊結果result.emplace_back(start, end);} else if (currentLen == maxLen) {result.emplace_back(start, end);}}}}if (maxLen == 0) { // 沒有滿足條件的區間cout << "NULL" << endl;return 0;}// 按起始下標排序，若起始相同則按結束下標排序sort(result.begin(), result.end(), [](const auto& a, const auto& b) {if (a.first != b.first) return a.first < b.first;return a.second < b.second;});// 去重（可能因不同路徑產生相同區間）set<pair<int, int>> uniqueSet(result.begin(), result.end());result.assign(uniqueSet.begin(), uniqueSet.end());// 格式化輸出bool first = true;for (const auto& [s, e] : result) {if (!first) cout << " ";cout << s << "-" << e;first = false;}cout << endl;return 0;
}

代碼詳細解析

1. 輸入處理
int minAverageLost;
cin >> minAverageLost;
cin.ignore(); // 忽略換行符
string line;
getline(cin, line); // 讀取數組行
istringstream iss(line);
  • 讀取容忍值 minAverageLost。
  • 讀取數組行并使用 istringstream 分割元素。
2. 轉換為差值數組
vector<int> diff(n);
for (int i = 0; i < n; ++i) {diff[i] = nums[i] - minAverageLost;
}
  • 將每個元素減去容忍值，生成新數組 diff。問題轉化為：尋找 diff 中子數組和 ≤ 0 的最長區間。
3. 前綴和數組計算
vector<long long> prefixSum(n + 1, 0);
for (int i = 0; i < n; ++i) {prefixSum[i + 1] = prefixSum[i] + diff[i];
}
  • 構建前綴和數組 prefixSum，其中 prefixSum[i] 表示前 i 個元素的和。
  • 例如：diff[1..3] 的和 = prefixSum[4] - prefixSum[1]。
4. 遍歷所有子數組
for (int end = 0; end < n; ++end) {for (int start = 0; start <= end; ++start) {if (prefixSum[end + 1] <= prefixSum[start]) {// 更新結果}}
}
  • 外層循環遍歷子數組的結束下標 end。
  • 內層循環遍歷起始下標 start。
  • 通過前綴和判斷子數組的和是否 ≤ 0。
5. 動態更新結果
if (currentLen > maxLen) {maxLen = currentLen;result.clear();result.emplace_back(start, end);
} else if (currentLen == maxLen) {result.emplace_back(start, end);
}
  • 發現更長的子數組時清空舊結果，保存新區間。
  • 遇到等長子數組時追加結果。
6. 排序與去重
sort(result.begin(), result.end(), [](const auto& a, const auto& b) {if (a.first != b.first) return a.first < b.first;return a.second < b.second;
});
set<pair<int, int>> uniqueSet(result.begin(), result.end());
  • 按起始下標升序、結束下標升序排序。
  • 使用 set 去重，確保結果唯一。
7. 格式化輸出
for (const auto& [s, e] : result) {if (!first) cout << " ";cout << s << "-" << e;first = false;
}
  • 將結果轉換為 0-2 格式輸出，用空格分隔。

示例測試

示例1輸入：
1  
0 1 2 3 4

輸出：

0-2
示例2輸入：
2  
0 0 100 2 2 99 0 2

輸出：

0-1 3-4 6-7
示例3輸入：
3  
1 1 1

輸出：

NULL

綜合分析

  1. 時間復雜度：O(n2)

    • 雙重循環遍歷所有子數組，適用于數組長度較小（n ≤ 100）的場景。

  2. 空間復雜度：O(n2)

    • 最壞情況下存儲所有可能的子數組區間（例如所有元素相同）。

  3. 優勢：

    • 避免浮點運算：通過整數運算快速判斷條件。
    • 嚴格排序與去重：確保結果符合題目要求。

  4. 適用場景：

    • 需要快速處理連續子數組的平均值問題，且輸入規模較小的場景。

C

問題分析

我們需要找到數組中所有滿足平均失敗率 ≤ 給定值的最長連續子數組，并輸出這些子數組的起始和結束下標。如果有多個相同長度的子數組，按起始下標升序排列。

解題思路

  1. 數學轉換：
    將每個元素減去容忍值，問題轉化為尋找子數組的和 ≤ 0 的最長連續區間。

  2. 前綴和數組：
    計算轉換后的數組的前綴和，利用前綴和快速判斷子數組的和是否滿足條件。

  3. 暴力遍歷：
    遍歷所有可能的子數組，記錄滿足條件的最長區間。

  4. 結果處理：
    去重并排序結果，按指定格式輸出。

代碼實現

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct {int start;int end;
} Interval;int compare_intervals(const void *a, const void *b) {Interval *ia = (Interval *)a;Interval *ib = (Interval *)b;if (ia->start != ib->start) return ia->start - ib->start;return ia->end - ib->end;
}int main() {int minAverageLost;char line[1000];// 讀取容忍值fgets(line, sizeof(line), stdin);minAverageLost = atoi(line);// 讀取數組行fgets(line, sizeof(line), stdin);int nums[100], n = 0;char *token = strtok(line, " ");while (token != NULL && n < 100) {nums[n++] = atoi(token);token = strtok(NULL, " ");}if (n == 0) {printf("NULL\n");return 0;}// 轉換為差值數組（元素 - 容忍值）int diff[100];for (int i = 0; i < n; i++) {diff[i] = nums[i] - minAverageLost;}// 計算前綴和數組long long prefixSum[101] = {0};for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + diff[i];}// 收集所有滿足條件的區間Interval *intervals = NULL;int interval_count = 0, interval_capacity = 0;int max_len = 0;for (int end = 0; end < n; end++) {for (int start = 0; start <= end; start++) {if (prefixSum[end + 1] <= prefixSum[start]) {// 記錄區間if (interval_count >= interval_capacity) {interval_capacity = (interval_capacity == 0) ? 1 : interval_capacity * 2;intervals = realloc(intervals, interval_capacity * sizeof(Interval));}intervals[interval_count].start = start;intervals[interval_count].end = end;interval_count++;// 更新最大長度int current_len = end - start + 1;if (current_len > max_len) max_len = current_len;}}}if (max_len == 0) {printf("NULL\n");free(intervals);return 0;}// 篩選出最長區間Interval *result = NULL;int result_count = 0, result_capacity = 0;for (int i = 0; i < interval_count; i++) {int len = intervals[i].end - intervals[i].start + 1;if (len == max_len) {if (result_count >= result_capacity) {result_capacity = (result_capacity == 0) ? 1 : result_capacity * 2;result = realloc(result, result_capacity * sizeof(Interval));}result[result_count++] = intervals[i];}}free(intervals);// 排序和去重qsort(result, result_count, sizeof(Interval), compare_intervals);int unique_count = 0;for (int i = 0; i < result_count; i++) {if (i == 0 || (result[i].start != result[i-1].start || result[i].end != result[i-1].end)) {result[unique_count++] = result[i];}}// 輸出結果if (unique_count == 0) {printf("NULL\n");} else {for (int i = 0; i < unique_count; i++) {printf("%d-%d", result[i].start, result[i].end);if (i != unique_count - 1) printf(" ");}printf("\n");}free(result);return 0;
}

代碼詳細解析

  1. 輸入處理：

    • 使用 fgets 讀取輸入行，strtok 分割字符串并轉換為整數數組。

  2. 數學轉換：

    int diff[100];
for (int i = 0; i < n; i++) {diff[i] = nums[i] - minAverageLost;
}
    • 將每個元素減去容忍值，生成新數組 diff。

  3. 前綴和計算：

    long long prefixSum[101] = {0};
for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + diff[i];
}
    • 構建前綴和數組 prefixSum，用于快速計算子數組的和。

  4. 遍歷子數組：

    for (int end = 0; end < n; end++) {for (int start = 0; start <= end; start++) {if (prefixSum[end + 1] <= prefixSum[start]) {// 記錄區間}}
}
    • 雙重循環遍歷所有子數組，判斷其和是否 ≤ 0。

  5. 動態數組管理：

    • 使用 realloc 動態擴展數組 intervals 和 result，存儲區間數據。

  6. 篩選最長區間：

    • 遍歷所有區間，篩選出長度等于 max_len 的區間。

  7. 排序與去重：

    qsort(result, result_count, sizeof(Interval), compare_intervals);
for (int i = 0; i < result_count; i++) {if (i == 0 || (result[i].start != result[i-1].start || result[i].end != result[i-1].end)) {result[unique_count++] = result[i];}
}
    • 按起始下標排序，遍歷去重相鄰重復項。

  8. 輸出結果：

    • 按格式輸出所有唯一的最長區間。

示例測試

示例1輸入：
1  
0 1 2 3 4

輸出：

0-2
示例2輸入：
2  
0 0 100 2 2 99 0 2

輸出：

0-1 3-4 6-7
示例3輸入：
3  
1 1 1

輸出：

NULL

綜合分析

  1. 時間復雜度：O(n2)

    • 雙重循環遍歷所有子數組，適用于數組長度較小（n ≤ 100）的場景。

  2. 空間復雜度：O(n2)

    • 最壞情況下存儲所有可能的子數組區間。

  3. 優勢：

    • 避免浮點運算：通過整數運算快速判斷條件。
    • 嚴格排序與去重：確保結果符合題目要求。

  4. 適用場景：

    • 需要快速處理連續子數組的平均值問題，且輸入規模較小的場景。

GO

問題分析

我們需要找到數組中所有滿足平均失敗率 ≤ 給定值的最長連續子數組，并輸出這些子數組的起始和結束下標。如果有多個相同長度的子數組，按起始下標升序排列。

解題思路

  1. 數學轉換：
    將每個元素減去容忍值，問題轉化為尋找子數組的和 ≤ 0 的最長連續區間。

  2. 前綴和數組：
    計算轉換后的數組的前綴和，快速判斷子數組的和是否滿足條件。

  3. 暴力遍歷：
    遍歷所有可能的子數組，記錄滿足條件的最長區間。

  4. 結果處理：
    篩選最長區間，排序并去重后輸出。

代碼實現

package mainimport ("bufio""fmt""os""sort""strconv""strings"
)type Interval struct {start, end int
}func main() {scanner := bufio.NewScanner(os.Stdin)// 讀取輸入參數scanner.Scan()minAverageLost, _ := strconv.Atoi(scanner.Text())scanner.Scan()numsLine := scanner.Text()numsStr := strings.Fields(numsLine)nums := make([]int, len(numsStr))for i, s := range numsStr {nums[i], _ = strconv.Atoi(s)}// 轉換數組為差值數組（元素 - 容忍值）diff := make([]int, len(nums))for i, num := range nums {diff[i] = num - minAverageLost}// 計算前綴和數組prefix := make([]int, len(diff)+1)prefix[0] = 0for i := 0; i < len(diff); i++ {prefix[i+1] = prefix[i] + diff[i]}// 收集所有滿足條件的區間var allIntervals []Intervalfor end := 0; end < len(diff); end++ {for start := 0; start <= end; start++ {if prefix[end+1] <= prefix[start] {allIntervals = append(allIntervals, Interval{start, end})}}}if len(allIntervals) == 0 {fmt.Println("NULL")return}// 找到最大長度maxLen := 0for _, interval := range allIntervals {length := interval.end - interval.start + 1if length > maxLen {maxLen = length}}// 篩選出最長區間的候選var candidates []Intervalfor _, interval := range allIntervals {if interval.end-interval.start+1 == maxLen {candidates = append(candidates, interval)}}// 排序候選區間（按起始下標升序，結束下標升序）sort.Slice(candidates, func(i, j int) bool {if candidates[i].start != candidates[j].start {return candidates[i].start < candidates[j].start}return candidates[i].end < candidates[j].end})// 去重（跳過相鄰重復項）var results []Intervalfor i, interval := range candidates {if i == 0 || (interval.start != candidates[i-1].start || interval.end != candidates[i-1].end) {results = append(results, interval)}}// 輸出結果if len(results) == 0 {fmt.Println("NULL")} else {output := make([]string, len(results))for i, interval := range results {output[i] = fmt.Sprintf("%d-%d", interval.start, interval.end)}fmt.Println(strings.Join(output, " "))}
}

代碼詳細解析

  1. 輸入處理：

    • 使用 bufio.Scanner 讀取輸入，轉換第一行為 minAverageLost，第二行為整數數組。

  2. 數學轉換：

    diff := make([]int, len(nums))
for i, num := range nums {diff[i] = num - minAverageLost
}
    • 將每個元素減去容忍值，生成新數組 diff。問題轉化為：尋找 diff 中和 ≤ 0 的子數組。

  3. 前綴和計算：

    prefix := make([]int, len(diff)+1)
for i := 0; i < len(diff); i++ {prefix[i+1] = prefix[i] + diff[i]
}
    • 構建前綴和數組 prefix，prefix[i] 表示前 i 個元素的和。

  4. 收集所有符合條件的區間：

    for end := 0; end < len(diff); end++ {for start := 0; start <= end; start++ {if prefix[end+1] <= prefix[start] {allIntervals = append(allIntervals, Interval{start, end})}}
}
    • 雙重循環遍歷所有子數組，判斷其和是否 ≤ 0，記錄符合條件的區間。

  5. 篩選最長區間：

    • 遍歷 allIntervals 找到最大長度 maxLen。
    • 篩選出所有長度為 maxLen 的區間存入 candidates。

  6. 排序與去重：

    sort.Slice(candidates, ...) // 按起始下標升序排序
for i, interval := range candidates {if i == 0 || ... { // 去重相鄰重復項results = append(results, interval)}
}
    • 排序后遍歷跳過重復項，確保結果唯一。

  7. 輸出結果：

    • 將結果格式化為字符串并輸出，若無有效結果輸出 NULL。

示例測試

示例1輸入：
1  
0 1 2 3 4

輸出：

0-2
示例2輸入：
2  
0 0 100 2 2 99 0 2

輸出：

0-1 3-4 6-7
示例3輸入：
3  
1 1 1

輸出：

NULL

綜合分析

  1. 時間復雜度：O(n2)

    • 雙重循環遍歷所有子數組，適用于數組長度較小（n ≤ 100）的場景。

  2. 空間復雜度：O(n2)

    • 最壞情況下存儲所有可能的子數組區間（如所有元素相同）。

  3. 優勢：

    • 避免浮點運算：通過整數運算快速判斷條件。
    • 嚴格順序處理：確保結果按起始下標排序。

  4. 適用場景：

    • 需要快速處理連續子數組的平均值問題，且輸入規模較小的場景。

更多內容：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文發表于【紀元A夢】，關注我，獲取更多實用教程/資源！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/78275.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/78275.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/78275.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

華為OD機試真題——繪圖機器（2025A卷：100分）Java/python/JavaScript/C++/C/GO最佳實現

華為OD機試真題——繪圖機器（2025A卷：100分）Java/python/JavaScript/C++/C/GO最佳實現

2025 A卷 100分 題型 本文涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、測試用例以及綜合分析&#xff1b; 并提供Java、python、JavaScript、C、C語言、GO六種語言的最佳實現方式&#xff01; 本文收錄于專欄&#xff1a;《2025華為OD真題目錄全流程解析/備考攻略/經驗…
閱讀更多...
基于 Python（selenium） 的百度新聞定向爬蟲：根據輸入的關鍵詞在百度新聞上進行搜索，并爬取新聞詳情頁的內容

基于 Python（selenium） 的百度新聞定向爬蟲：根據輸入的關鍵詞在百度新聞上進行搜索，并爬取新聞詳情頁的內容

該項目能夠根據輸入的關鍵詞在百度新聞上進行搜索，并爬取新聞詳情頁的內容。 一、項目準備 1. 開發環境配置 操作系統：支持 Windows、macOS、Linux 等主流操作系統，本文以 Windows 為例進行說明。Python 版本：建議使用 Python 3.8 及以上版本，以確保代碼的兼容性和性能。…
閱讀更多...
MySQL表的操作 -- 表的增刪改查

MySQL表的操作 -- 表的增刪改查

目錄 1. 表的創建2. 表的查看3. 表的修改4. 表的刪除5. 總結 1. 表的創建 1.查看字符集及效驗規則 2. 表的創建 CREATE TABLE table_name ( field1 datatype, field2 datatype, field3 datatype ) character set 字符集 collate 校驗規則 engine 存儲引擎;創建用戶表1 創建用…
閱讀更多...
如何解決極狐GitLab 合并沖突？

如何解決極狐GitLab 合并沖突？

極狐GitLab 是 GitLab 在中國的發行版&#xff0c;關于中文參考文檔和資料有&#xff1a; 極狐GitLab 中文文檔極狐GitLab 中文論壇極狐GitLab 官網 合并沖突 (BASIC ALL) 合并沖突發生在合并請求的兩個分支&#xff08;源分支和目標分支&#xff09;對相同代碼行進行了不同…
閱讀更多...
oracle不同數據庫版本的自增序列

oracle不同數據庫版本的自增序列

-- 查看數據庫版本 SELECT * FROM v$version WHERE banner LIKE Oracle%; 1. Oracle 12c及以上版本支持 id NUMBER GENERATED ALWAYS AS IDENTITY PRIMARY KEY, id NUMBER GENERATED ALWAYS AS IDENTITY (START WITH 1 INCREMENT BY 1) PRIMARY KEY, -- 語法 id NUMBER GENER…
閱讀更多...
VIC-3D非接觸全場應變測量系統用于小尺寸測量之電子元器件篇—研索儀器DIC數字圖像相關技術

VIC-3D非接觸全場應變測量系統用于小尺寸測量之電子元器件篇—研索儀器DIC數字圖像相關技術

在5G通信、新能源汽車電子、高密度集成電路快速迭代的今天&#xff0c;電子元件的尺寸及連接工藝已進入亞毫米級競爭階段&#xff0c;這種小尺寸下的力學性能評估對測量方式的精度有更高的要求&#xff0c;但傳統應變測量手段常因空間尺寸限制及分辨率不足難以捕捉真實形變場。…
閱讀更多...
pod 創建私有庫指南

pod 創建私有庫指南

步驟 參考&#xff1a;iOS Pod 私有庫創建指南-百度開發者中心 下面主要是對參考鏈接里面的解釋&#xff1a; 創建兩個倉庫&#xff1a; 一個叫podframe.git&#xff0c;用來存放自定義的framework&#xff0c;比如TestPodFrame.framework一個叫podspec.git&#xff0c;用來…
閱讀更多...
【JavaEE】Spring AOP的注解實現

【JavaEE】Spring AOP的注解實現

目錄 一、AOP 與 Spring AOP二、Spring AOP簡單實現三、詳解Spring AOP3.1 Spring AOP 核心概念3.1.1 切點&#xff08;Pointcut&#xff09;3.1.2 連接點&#xff08;Join Point&#xff09;3.1.3 通知&#xff08;Advice&#xff09;3.1.4 切面&#xff08;Aspect&#xff09…
閱讀更多...
協作開發攻略：Git全面使用指南 — 結語

協作開發攻略：Git全面使用指南 — 結語

協作開發攻略&#xff1a;Git全面使用指南 — 結語 Git 是一種分布式版本控制系統&#xff0c;用于跟蹤文件和目錄的變更。它能幫助開發者有效管理代碼版本&#xff0c;支持多人協作開發&#xff0c;方便代碼合并與沖突解決&#xff0c;廣泛應用于軟件開發領域。 文中內容僅限技…
閱讀更多...
如何用AI主動突出畫面主體！涂鴉新方案助剪輯、工業巡檢、醫療影像等領域，實現自動追蹤+智能放大

如何用AI主動突出畫面主體！涂鴉新方案助剪輯、工業巡檢、醫療影像等領域，實現自動追蹤+智能放大

隨著智能 IPC 設備&#xff08;如安防攝像頭、寵物陪伴機器人、嬰兒監視器等&#xff09;日益普及&#xff0c;越來越多的生活場景被實時記錄。然而在實際使用中&#xff0c;由于設備安裝位置不當、廣角鏡頭視野過大等原因&#xff0c;經常會出現拍攝主體占比過小的問題&#x…
閱讀更多...
數據湖DataLake和傳統數據倉庫Datawarehouse的主要區別是什么？優缺點是什么？

數據湖DataLake和傳統數據倉庫Datawarehouse的主要區別是什么？優缺點是什么？

數據湖和傳統數據倉庫的主要區別 以下是數據湖和傳統數據倉庫的主要區別&#xff0c;以表格形式展示&#xff1a; 特性數據湖傳統數據倉庫數據類型支持結構化、半結構化及非結構化數據主要處理結構化數據架構設計扁平化架構&#xff0c;所有數據存儲在一個大的“池”中多層架…
閱讀更多...
當智駕成標配，車企暗戰升級｜2025上海車展

當智駕成標配，車企暗戰升級｜2025上海車展

文&#xff5c;劉俊宏 編&#xff5c;王一粟 智能化無處不在的2025年上海車展&#xff0c;回歸了賣車的初衷。 光錐智能在展會暴走兩天&#xff0c;最大的感觸是今年的車展少了爭奇斗艷&#xff0c;多了些許務實。 回顧智能汽車時代的三場重要車展。2023年的上海車展充滿了…
閱讀更多...
如何在Spring Boot中禁用Actuator端點安全性

如何在Spring Boot中禁用Actuator端點安全性

在 Spring Boot 應用中&#xff0c;Spring Boot Actuator 提供了一系列用于監控和管理應用的端點&#xff08;如 /actuator/health、/actuator/metrics&#xff09;&#xff0c;這些端點默認可能受到 Spring Security 的保護&#xff0c;要求身份驗證或授權。然而&#xff0c;在…
閱讀更多...
【mongodb】系統保留的數據庫名

【mongodb】系統保留的數據庫名

目錄 1. admin2. config3. local4. test&#xff08;非嚴格保留&#xff0c;但常作為默認測試數據庫&#xff09;5. 注意事項6. 其他相關說明 1. admin 1.用途&#xff1a;用于存儲數據庫的權限和用戶管理相關數據。2.特點&#xff1a;該數據庫是 MongoDB 的超級用戶數據庫&am…
閱讀更多...
Redis是單線程的，如何提高多核CPU的利用率？

Redis是單線程的，如何提高多核CPU的利用率？

一句話回答&#xff1a; Redis 是單線程處理客戶端命令&#xff0c;但可以通過 多實例部署、I/O 多路復用、后臺線程 Redis 6 的 I/O Thread 支持&#xff0c;來充分利用多核 CPU。 一、Redis 單線程 ≠ 整個 Redis 都是單線程&#xff01; Redis 主要的 網絡事件 命令執行 …
閱讀更多...
關于mysql的事務和索引

關于mysql的事務和索引

1. 事務四大特性&#xff08;ACID&#xff09; 原子性&#xff1a;事務的操作要么全部成功&#xff0c;要么全部失敗回滾&#xff0c;不可分割。 一致性&#xff1a;事務執行前后&#xff0c;數據必須滿足業務規則&#xff08;如賬戶總額不變&#xff09;。 隔離性&#xff1…
閱讀更多...
【Python】保持Selenium穩定爬取的方法（防檢測策略）

【Python】保持Selenium穩定爬取的方法（防檢測策略）

selenium 防檢測策略的方法匯總&#xff1a; 合理設置延遲&#xff1a;請求間添加隨機延遲 (2-10秒) 限制爬取頻率&#xff1a;控制每小時/每天的請求量 輪換用戶代理&#xff1a;準備至少10個不同的User-Agent 使用住宅代理&#xff1a;優先選擇高質量的住宅代理IP 處理驗…
閱讀更多...
SpringSecurity源碼解讀AbstractAuthenticationProcessingFilter

SpringSecurity源碼解讀AbstractAuthenticationProcessingFilter

一、介紹 AbstractAuthenticationProcessingFilter 是 Spring Security 框架里的一個抽象過濾器，它在處理基于表單的認證等認證流程時起著關鍵作用。它繼承自 GenericFilterBean，并實現了 javax.servlet.Filter 接口。此過濾器的主要功能是攔截客戶端發送的認證請求，對請求…
閱讀更多...
什么是DDD？為什么它正在取代傳統架構？

什么是DDD？為什么它正在取代傳統架構？

什么是DDD&#xff1f;為什么它正在取代傳統架構&#xff1f; 1. 傳統開發模式的痛點 在經典的MVC架構中&#xff0c;開發流程往往從數據庫表結構設計開始&#xff0c;業務邏輯散落在Service層&#xff0c;隨著需求迭代容易形成「大泥球」代碼&#xff1a; 實體類變成純粹的…
閱讀更多...
基于外部中中斷機制，實現以下功能： 1.按鍵1，按下和釋放后，點亮LED 2.按鍵2，按下和釋放后，熄滅LED 3.按鍵3，按下和釋放后，使得LED閃爍

基于外部中中斷機制，實現以下功能： 1.按鍵1，按下和釋放后，點亮LED 2.按鍵2，按下和釋放后，熄滅LED 3.按鍵3，按下和釋放后，使得LED閃爍

題目&#xff1a; 參照外部中斷的原理和代碼示例,再結合之前已經實現的按鍵切換LED狀態的實驗&#xff0c;用外部中斷改進其實現。 請自行參考文檔《中斷》當中&#xff0c;有關按鍵切換LED狀態的內容, 自行連接電路圖&#xff0c;基于外部中斷機制&#xff0c;實現以下功能&am…
閱讀更多...
最新文章

Copyright @ 2022~2023