 |
|
发布时间：2025-10-03 20:26:11
| 8.30美团算法笔试（带答案） 8.30美团算法笔试（带答案）\n解题思路：\n一、小美的神秘运算 2\n核心是批量处理偶数操作 + 循环快速跳转，避免逐次操作超时。当 n 为偶数时，通过计算二进制末尾 0 的个数，一次性完成多次除以 2 的操作；当 n 为奇数时，仅执行一次 3n+1 操作（因奇数操作后必为偶数，可衔接批量处理）；若 n 变为 1，利用 1→4→2→1 的循环规律，通过剩余步数对 3 取余直接确定结果，整体复杂度远低于 10¹⁸的操作上限。\n \n二、线性判别分析\n围绕Fisher 线性判别核心逻辑实现二分类。先拆分训练集为两类样本，计算每类的均值向量；再构建类内散度矩阵并加入正则项避免奇异；通过求解线性方程得到最佳投影方向，将样本投影到一维空间；最后对比测试样本投影值与两类投影均值的距离，距离更近的即为预测类别，消除投影方向符号影响。\n \n三、连续数列\n先做问题转化，将子数组权值拆分为 “（最大值 - 最小值）-（长度 - 1）”，总权值和即为所有子数组的（最大值 - 最小值）和减去（长度 - 1）和。其中（长度 - 1）和可通过公式直接计算；（最大值 - 最小值）和需用单调栈，分别统计每个元素作为子数组最大值、最小值的贡献次数，再计算对应和，整体复杂度 O (n)，适配 2×10⁵的数组长度。\n \n四、树上最小公倍数追踪\n基于重链剖分 + 线段树，结合 LCM 的素数特性求解。先预分解 1-100 的素数指数，将每个节点权值转为素数指数向量；用重链剖分把树根到节点的路径拆分为 O (logn) 个链段；线段树维护每个区间黑色节点的素数最大指数（白色节点指数为 0），翻转颜色对应点更新，查询路径时合并各链段的素数最大指数，最终通过素数幂乘积计算 LCM 并取模。\n#大厂校招 #秋招 #秋招信息差 #美团 #美团笔试 #美团校招 #美团秋招 #华为#秋招笔试 #大厂秋招 |
上一篇：前端秋招笔试/刷题阶段性大总结！
