大家可以在 华为刷题 牛客官方练习集刷题

统计量列表

给定一个整数序列与一个窗口大小列表。对每一行输入，固定一个公共右边界，对窗口列表中的每个窗口长度各取一个“右对齐”的子数组，分别计算5个统计量，并按窗口列表的顺序依次拼接成一行结果；沿着序列从左到右依次移动右边界，生成多行输出。 统计量与计算约定

每个子数组输出5项（固定顺序）：mean、std、min、max、slope。
std: 样本标准差（ddof=1）。当窗口长度为1时，std=0。
slope: 最小二乘直线斜率，横坐标为 x=0..w−1。若分母为0或 w=1，则 slope=0。
数值格式：若为整数则不带小数点；非整数最多保留3位小数，四舍五入，去掉末尾无意义的0（如 1.0→1，1.10→1.1，1.1116→1.112）。

窗口对齐与行数

窗口对齐方式：右对齐。第 i 行的公共右边界为 R=i+max(window_array)−1。对窗口大小 w，取子数组 arr[R−w+1…R]。
行数 n = len(input_array) − max(window_array) + 1。若 len(input_array) < 任一窗口大小，则输出为空。

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 输入描述：

支持多行输入；每行一组数据，格式为： [整数序列], [窗口大小序列] 例如：[1, 2, 3, 4, 5], [2, 3]

输出描述：

对每一行输入，按行输出多个结果行；每个结果行是该位置处按窗口列表顺序拼接的统计量列表。 若该行输入不满足条件（如数组过短），仅输出一行“[]”。

示例1 输入例子：

[2, 4, 6, 8, 10, 12], [2, 4]

输出例子：

[7, 1.414, 6, 8, 2, 5, 2.582, 2, 8, 2] [9, 1.414, 8, 10, 2, 7, 2.582, 4, 10, 2] [11, 1.414, 10, 12, 2, 9, 2.582, 6, 12, 2]

例子说明：

最长窗口为4，右对齐到各行的共同右边界 R，因此共有 6-4+1=3 行。 第1行：w=2 用 [6,8]，w=4 用 [2,4,6,8]；依序拼接5个特征后输出。其余行同理。

示例2 输入例子：

[10, 20], [3, 4]

输出例子：

[]

例子说明：

输入序列长度为 2，最大窗口为 4，因 2 < 4 无法形成任何右对齐窗口，按规则该行仅输出“[]”。

题解

这道题考查多尺寸滑动窗口特征提取算法的设计与实现。核心思路是对每个给定窗口大小，在时间序列上进行滑动，并提取统计特征。

算法关键点分析

1. 窗口对齐机制：所有窗口采用右对齐策略，确保不同大小窗口在同一时间点上的特征具有可比性。设最大窗口大小为 ，则第 行对应的窗口 的数据片段为：

   start = i + (M - w)  
   segment = input_array[start : start + w]
   

2. 特征计算：

   • 均值和最值：直接使用内置函数计算
   • 样本标准差：注意使用 ，单元素窗口返回0
   • 线性趋势斜率：利用最小二乘法公式，可预计算 和 以提高效率

3. 数值格式化：使用字符串处理技巧去除尾随零，保持输出格式的美观性

4. 边界处理：当输入长度小于最大窗口时，直接返回空数组

复杂度分析

时间复杂度：，其中 为输出行数， 为窗口数量， 为平均窗口大小。 空间复杂度：，主要用于存储输出结果。

参考代码

• Python

import sys
import ast
import math

input = lambda: sys.stdin.readline().strip()

def format_number(x):
    """格式化数字：整数不显示小数点，小数最多3位并去掉尾随0"""
    if abs(x - round(x)) < 1e-9:
        return str(int(round(x)))
    formatted = f"{x:.3f}".rstrip('0').rstrip('.')
    return formatted

def calc_slope(data_seg):
    """计算线性回归斜率"""
    n = len(data_seg)
    if n == 1:
        return 0.0
    
    # 预计算求和项以提高效率
    sum_x = n * (n - 1) / 2              # 0+1+...+(n-1)
    sum_x_sq = (n - 1) * n * (2 * n - 1) / 6  # 0²+1²+...+(n-1)²  
    sum_y = sum(data_seg)
    sum_xy = sum(i * y for i, y in enumerate(data_seg))
    
    # 最小二乘法计算斜率
    numerator = n * sum_xy - sum_x * sum_y
    denominator = n * sum_x_sq - sum_x * sum_x
    
    return numerator / denominator if denominator != 0 else 0.0

def calc_sample_std(data_seg):
    """计算样本标准差(ddof=1)"""
    n = len(data_seg)
    if n <= 1:
        return 0.0
    
    mean_val = sum(data_seg) / n
    variance = sum((x - mean_val) ** 2 for x in data_seg) / (n - 1)
    
    return math.sqrt(variance)

def parse_input_arrays(text):
    """解析输入的数组格式"""
    text = text.strip()
    
    # 处理单行格式：[1,2], [3,4] 
    if text.count('[') == 2 and ',' in text and text.count(']') == 2:
        parts = text.split(']', 1)
        first_arr = parts[0] + ']'
        second_arr = parts[1].replace(',', '', 1).strip()
        
        array1 = ast.literal_eval(first_arr)
        array2 = ast.literal_eval(second_arr)
        
        return array1, array2
    
    # 处理多行格式
    lines = [line.strip() for line in text.split('\n') if line.strip()]
    array1 = ast.literal_eval(lines[0])
    array2 = ast.literal_eval(lines[1])
    
    return array1, array2

def main():
    input_text = sys.stdin.read()
    if not input_text.strip():
        return
    
    # 解析输入数组
    input_arr, window_arr = parse_input_arrays(input_text)
    
    # 检查边界条件
    if not input_arr or len(input_arr) < max(window_arr):
        print('[]')
        return
    
    max_window = max(window_arr)
    num_rows = len(input_arr) - max_window + 1
    
    # 处理每一行的特征提取
    for row_idx in range(num_rows):
        feature_list = []
        
        # 为每个窗口大小提取特征
        for win_size in window_arr:
            start_idx = row_idx + (max_window - win_size)
            data_segment = input_arr[start_idx:start_idx + win_size]
            
            # 计算五个特征
            mean_val = sum(data_segment) / win_size
            std_val = calc_sample_std(data_segment)
            min_val = min(data_segment)
            max_val = max(data_segment) 
            slope_val = calc_slope(data_segment)
            
            feature_list.extend([mean_val, std_val, min_val, max_val, slope_val])
        
        # 格式化输出
        formatted_features = ', '.join(format_number(x) for x in feature_list)
        print(f'[{formatted_features}]')

if __name__ == '__main__':
    main()

• Cpp

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

// 格式化数字输出
string formatNum(double val) {
    if (abs(val - round(val)) < 1e-9) {
        return to_string((int)round(val));
    }
    
    ostringstream oss;
    oss << fixed << setprecision(3) << val;
    string result = oss.str();
    
    // 去除尾随0和小数点
    while (result.back() == '0') result.pop_back();
    if (result.back() == '.') result.pop_back();
    
    return result;
}

// 计算线性回归斜率
double calcSlope(const vector<double>& seg) {
    int n = seg.size();
    if (n == 1) return 0.0;
    
    double sum_x = (double)n * (n - 1) / 2.0;
    double sum_x_sq = (double)(n - 1) * n * (2 * n - 1) / 6.0;
    double sum_y = 0.0, sum_xy = 0.0;
    
    for (int i = 0; i < n;