✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🤖 内容包含AI辅助生成，题解和代码均经过多轮验证，有问题欢迎评论

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

团子-2026.04.11-算法岗

题目总览

题号	题名	主要做法	难度
01	选盒子	分类计数	简单
02	IRLS 线性分类	迭代优化 + 数值计算	困难
03	长度为 m 的窗口和	约束转化 + 计数	困难
04	函数图求和	函数图分解	困难

这套美团算法岗不太适合一口气平推。第一题可以先收掉，第二题直接转到数值计算实现，第三题还要做窗口约束转化，第四题再补上函数图。时间分配如果没有提前控好，后半段会比较挤。

01. 小兰的奇偶盒子挑选

问题描述

小兰把一段长度为 的整数序列按顺序打包成若干个“小盒子”。

• 第 个盒子装的是 ；
• 第 个盒子装的是 ；
• 依此类推；
• 如果 是奇数，那么还会剩下一个单元素盒 。

现在他需要恰好选出 个盒子，并且从每个被选中的盒子里拿出且仅拿出一个数。

小兰希望拿出的这些数之和是奇数。请你判断是否存在一种选择方案。

输入格式

每个测试文件包含多组数据。

第一行输入一个整数 ，表示测试数据组数。

对于每组数据：

• 第一行输入两个整数 ；
• 第二行输入 个整数 。

输出格式

对于每组数据：

• 如果存在合法方案，输出 Yes；
• 否则输出 No。

样例输入

3
5 2
1 2 3 4 5
3 1
1 3 5
5 3
2 2 2 2 2

样例输出

Yes
Yes
No

样例说明

• 第一组里可以选盒 和 ，拿出 与 ，总和为 。
• 第二组里只有一个双元素盒和一个单元素盒，任选那个只装着 的单元素盒即可。
• 第三组所有数都是偶数，不可能拼出奇数和。

数据范围

• 
• 
• 
• 
• 单个测试文件中所有 的总和不超过

题解

这题只需要先看清“每个盒子能提供什么奇偶性”。

把每个盒子分成三类：

1. 固定偶盒：盒里只能拿到偶数。
2. 固定奇盒：盒里只能拿到奇数。
3. 可调盒：盒里一个奇数、一个偶数，可以按需要拿成奇数，也可以拿成偶数。

设这三类盒子的数量分别是：

• evenBox
• oddBox
• flexBox

1. 只要选到了可调盒，答案就一定是 Yes

因为题目要求恰好选 个盒子，而输入保证 不会超过盒子总数。

如果我们选出的 个盒子里至少有一个可调盒，那么一步总可以通过它来“修正奇偶性”：

• 前面若已经凑成偶数，就让它贡献奇数；
• 前面若已经凑成奇数，就让它贡献偶数。

所以：

• 只要 flexBox > 0，答案直接就是 Yes。

2. 没有可调盒时，只能靠固定奇盒的个数来决定

这时每个被选盒子的贡献奇偶性都已经固定了。

如果选了 个固定奇盒、 个固定偶盒，那么总和是奇数，当且仅当：

• 是奇数。

同时还要满足数量限制：

• 
• 

把第二个条件整理一下，得到：

所以问题就变成：

• 这个区间里是否存在一个奇数。

如果存在，输出 Yes；否则输出 No。

3. 复杂度

每个盒子只会被扫一遍。

• 时间复杂度：
• 空间复杂度：（不计输入数组）

参考代码（Python）

import sys

def input() -> str:
    return sys.stdin.readline().strip()

def solve() -> None:
    # Read input in ACM mode and build the answer directly.
    t = int(input())
    out = []
    for _ in range(t):
        # Process each test case independently.
        n, x = map(int, input().split())
        arr = list(map(int, input().split()))

        even_box = 0
        odd_box = 0
        flex_box = 0

        i = 0
        while i < n:
            if i + 1 == n:
                if arr[i] & 1:
                    odd_box += 1
                else:
                    even_box += 1
            else:
                p1 = arr[i] & 1
                p2 = arr[i + 1] & 1
                if p1 != p2:
                    flex_box += 1
                elif p1 == 1:
                    odd_box += 1
                else:
                    even_box += 1
            i += 2

        if flex_box > 0:
            out.append("Yes")
            continue

        left = max(0, x - even_box)
        right = min(x, odd_box)
        first_odd = left if left & 1 else left + 1
        out.append("Yes" if first_odd <= right else "No")

    print("\n".join(out))

if __name__ == "__main__":
    # Standard ACM entry.
    solve()

02. 园子的优惠券购买判别器

问题描述

园子在整理一批优惠券投放样本，想用一个二分类模型判断用户是否会下单领取。

现在给出训练集 train 和测试集 test。训练集一列是标签：

• 1 表示会购买；
• 0 表示不会购买。

你需要按照题面规定的流程，手写实现一个对数几率回归（Logistic Regression）模型，并输出测试集的预测类别。

模型要求如下：

1. 读入数据

• train 是二维数组，前若干列是数值特征，一列是标签；
• test 是二维数组，只包含特征。

2. 模型训练

先在特征矩阵最左侧拼接一列全 1，作为截距项。

然后使用 IRLS（迭代重加权最小二乘）迭代求极大似然解：

其中：

并且：

• ，加在 Hessian 对角线上，防止矩阵奇异；
• 当 时停止；
• 否则最多迭代 次。

3. 预测

测试集也要拼接同样的截距列。

计算：

再按下面规则输出类别：

输入格式

输入只有一行，是一个合法 JSON 对象，格式如下：

{
  "train": [[f11, f12, ..., y1], [f21, f22, ..., y2], ...],
  "test": [[t11, t12, ...], [t21, t22, ...], ...]
}

其中：

• train[i] 的一个元素是标签；
• 其余元素都是数值特征；
• test 的特征维度与训练集保持一致。

输出格式

输出一行合法 JSON 数组，按顺序给出测试样本的预测标签。

例如：

[0, 1]

样例输入

{"train": [[1,2,0],[2,1.8,0],[5,5,1],[4.5,5.2,1]],"test":[[1.5,1.9],[5,5.1]]}

样例输出

[0, 1]

数据范围

• 原题未单独给出额外上界；
• 保证输入 JSON 合法；
• 保证训练集与测试集的特征维度一致。

题解

这题的重点很明确：把 IRLS 版逻辑回归按题面流程完整复现出来。

1. 为什么公式正好是 Newton 迭代

逻辑回归最大化的是对数似然。

把它写成最优化问题后，梯度是：

Hessian 是：

其中 的第 个对角元正是：

所以 Newton 一步更新就是：

题面给出的 IRLS 公式，从模型上看就是这件事。

2. 为什么要加

如果某些特征高度相关，或者样本数太少，矩阵 可能接近奇异。

这时直接求逆会非常不稳定。

在对角线上补一个很小的：

就等于给 Hessian 做了轻微扰动，既不会破坏整体方向，又能避免线性方程组退化。

3. 实现时要注意的三个细节

1. 截距项要真的拼到最左边
   常数列必须算进参数里，不然实现出来的模型就和题面要求对不上。

2. Sigmoid 最好写成稳定版
   当线性值绝对值很大时，直接 exp(-z) 容易溢出。写成分段形式更稳。

3. 不用真的去求逆
   公式里写了逆矩阵，但代码里更好的做法是直接解线性方程组：

   

   然后：

   

   这样数值表现更可靠。

4. 复杂度

设样本数为 ，特征维度（含截距）为 。

每轮迭代主要开销是：

• 计算梯度与 Hessian：
• 解一个 线性方程组：

总共最多迭代 次，完全可以接受。

参考代码（Python）

import json
import math

EPS = 1e-8
STOP = 1e-6
MAX_ITER = 30

def sigmoid(z):
    if z >= 0:
        exp_neg = math.exp(-z)
        return 1.0 / (1.0 + exp_neg)
    exp_pos = math.exp(z)
    return exp_pos / (1.0 + exp_pos)

def solve_linear(a, b):
    n = len(a)
    for i in range(n):
        pivot = i
        for j in range(i + 1, n):
            if abs(a[j][i]) > abs(a[pivot][i]):
                pivot = j
        a[i], a[pivot] = a[pivot], a[i]
        b[i], b[pivot] = b[pivot], b[i]

        div = a[i][i]
        for j in range(i, n):
            a[i][j] /= div
        b[i] /= div

        for row in range(n):
            if row == i:
                continue
            factor = a[row][i]
            if abs(factor) < 1e-15:
                continue
            for col in range(i, n):
                a[row][col] -= factor * a[i][col]
            b[row] -= factor * b[i]
    return b

def solve() -> None:
    data = json.loads(input())

    train = data["train"]
    test = data["test"]

    sample_count = len(train)
    feature_count = len(train[0]) - 1
    dim = feature_count + 1

    x = [[1.0] + [float(train[i][j]) for j in range(feature_count)] for i in range(sample_count)]
    y = [float(train[i][feature_count]) for i in range(sample_count)]
    xt = [[1.0] + [float(v) for v in row] for row in test]

    w = [0.0] * dim

    for _ in range(MAX_ITER):
        p = []
        for row in x:
            z = 0.0
            for j in range(dim):
                z += row[j] * w[j]
            p.append(sigmoid(z))

        grad = [0.0] * dim
        hessian = [[0.0] * dim for _ in range(dim)]
        for i in range(dim):
            hessian[i][i] = EPS

        for i in range(sample_count):
            diff = p[i] - y[i]
            weight = p[i] * (1.0 - p[i])
            row = x[i]
            for r in range(dim):
                grad[r] += row[r] * diff
                scaled = row[r] * weight
                for c in range(dim):
                    hessian[r][c] += scaled * row[c]

        delta = solve_linear(hessian, grad)
        norm2 = 0.0
        for i in range(dim):
            w[i] -= delta[i]
            norm2 += delta[i] * delta[i]