华为 · 计算几何 · 算法编程题
华为 计算几何 时限 1 秒 / 256 MB

题目描述

给定一个整数序列与一个窗口大小列表。对每一行输入,固定一个公共右边界,对窗口列表中的每个窗口长度各取一个“右对齐”的子数组,分别计算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) < 任一窗口大小,则输出为空。

输入输出

输入描述
支持多行输入;每行一组数据,格式为:
[整数序列], [窗口大小序列]
例如:[1, 2, 3, 4, 5], [2, 3]
输出描述
对每一行输入,按行输出多个结果行;每个结果行是该位置处按窗口列表顺序拼接的统计量列表。
若该行输入不满足条件(如数组过短),仅输出一行“[]”。

样例共 2 组

样例 1 · 最长窗口为4,右对齐到各行的共同右边界 R,因此共有 6-4+1=3 行。 第1行:w=2 用 [6,8],w=4 用 [2,4,6,8];依序拼接5个特征后输出。其余行同理。
输入
[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]
样例 2 · 输入序列长度为 2,最大窗口为 4,因 2 < 4 无法形成任何右对齐窗口,按规则该行仅输出“[]”。
输入
[10, 20], [3, 4]
输出
[]

算法解析依据一般

考点:计算几何

限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:计算几何

把几何关系转成坐标运算,用整数运算避免浮点误差。

思路框架(计算几何 通法 · 非本题专属)

  1. 把点、向量、线段用坐标表示。
  2. 几何判定(平行、垂直、共线、相交)尽量用叉积/点积的整数形式:叉积为 0 即共线。
  3. 距离用平方比较,避免开方带来的浮点误差。
  4. 面积用叉积(鞋带公式)计算。

实现要点:叉积 cross = x1*y2 - x2*y1;用它判断顺时针/逆时针和共线。

复杂度:时间 O(n) ~ O(n²) | 空间 O(n)

该范式的通法易错点

  • 用浮点相等判断几何关系(应用整数叉积)。
  • 没考虑三点共线、重合等退化情况。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例解读

样例 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,

最长窗口为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 无法形成任何右对齐窗口,按规则该行仅输出“[]”。

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2025年秋招-华为-9月10号AI岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解