大厂真题 / 阿里巴巴

阿里 4.15 笔试真题 - AI算法岗

本场考试概述

考试时间：2026年4月15日 考试岗位：AI算法岗 难度评级：困难

考点分析：

第一题：贪心 + 负数奇偶性分析（难度简单）
第二题：动态规划 + 前缀和（难度中等）
第三题：并查集 + 稀疏表（难度困难）

建议策略：

第一题是签到题，抓住”操作不改变负数个数的奇偶性”这个不变量即可
第二题识别出约束等价于”任意两个假话间距 ≥ k”，用 DP 逐位置决策
第三题数据量大，需要并查集维护连续段合并 + 稀疏表 O(1) 回答区间最大值查询

第一题：富豪

题目描述

给定长度为 n 的数组 a，可以执行若干次操作：选择相邻的两个元素，同时翻转它们的符号（即 a[i] 变为 -a[i]，a[i+1] 变为 -a[i+1]）。求操作后数组元素之和的最大值。

样例

输入

输出

10
6

思路分析

第一步：观察操作的不变量

一次操作同时翻转两个元素的符号，负数个数的变化只可能是 +2、-2 或 0——也就是说，负数个数的奇偶性始终不变。这是关键不变量。

第二步：分情况讨论

为了让总和最大，理想情况是所有元素都取绝对值。设绝对值之和为 S，负数个数为 neg_cnt。

neg_cnt 为偶数：每次挑一对负数同时翻转为正，最终全部非负，答案就是 S
neg_cnt 为奇数但存在 0：可以对 0 和一个负数执行操作——负数变正，0 翻转后还是 0，等价于”免费消掉一个负数”，答案也是 S
neg_cnt 为奇数且无 0：必须保留恰好一个负数。为了让损失最小，让绝对值最小的元素当负数。答案为 S - 2·min_abs（减 2 倍是因为 S 已经把它算成正的，改回负数一来一回差了 2 倍）

第三步：实现要点

一次遍历即可统计绝对值之和、负数个数、是否有零、最小绝对值。

题解代码

import sys
input = sys.stdin.readline

def solve(a):
    total = sum(abs(x) for x in a)
    neg_cnt = sum(1 for x in a if x < 0)
    has_zero = any(x == 0 for x in a)
    min_abs = min(abs(x) for x in a)
    if neg_cnt % 2 == 0 or has_zero:
        return total
    return total - 2 * min_abs

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(a))

复杂度分析

时间复杂度：O(n)，遍历数组一次。 空间复杂度：O(1)，只需常数个变量。

第二题：何物为真

题目描述

一共有 n 句话，部分已知真假（1 表示真，0 表示假，-1 表示未知）。规则：在任意连续的 k 句话中，最多只有 1 句是假话。求有多少种合法的填充方式，答案对 10⁹+7 取模。

样例

输入

3
2
-1 -1 -1 -1 -1
3
-1 0 -1
1
-1 -1 -1 -1 0

输出

13
1
16

思路分析

第一步：转化约束条件

“任意连续 k 句最多 1 句假话”等价于”任意两句假话之间的间距至少为 k”。这是因为如果两句假话的间距 < k，就能找到一个长度为 k 的窗口同时包含它们。

第二步：设计 DP 状态

设 f[i] 表示只考虑前 i 句话时，所有合法填充方案的总数。初始 f[0] = 1（零句话只有一种方案）。

对于第 i 句话，有两种选择：

填真（前提：a[i] ≠ 0，即没被强制为假）：前 i-1 句的任何合法方案后接一个”真”仍然合法，贡献 f[i-1]
填假（前提：a[i] ≠ 1，即没被强制为真）：根据间距约束，第 i 句为假时，前面 k-1 个位置必须全部为真。如果这段区间内存在已知假话（值为 0），就矛盾了，不能填假。否则方案数等于跳过这 k-1 个被锁死为真的位置，继承 f[max(0, i-k)]

第三步：前缀和加速判断

判断窗口内有没有已知假话，预处理前缀和记录前 i 个位置中有多少个 0，对任意区间做一次减法即可 O(1) 判断。

以样例 2 为例（n=4, k=3, 序列 [1,-1,0,-1]）：

i=1: a[1]=1，只能填真，f[1]=f[0]=1
i=2: a[2]=-1，填真贡献 f[1]=1；填假时检查区间 [1,1] 无已知假话，贡献 f[0]=1。f[2]=2
i=3: a[3]=0，强制为假，不能填真；填假时检查区间 [1,2] 无已知假话，贡献 f[0]=1。f[3]=1
i=4: a[4]=-1，填真贡献 f[3]=1；填假时检查区间 [2,3]，其中 a[3]=0 是已知假话，矛盾。f[4]=1

题解代码

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7

T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split()))  # 1-indexed

    # 前缀和统计 0 的个数，用于 O(1) 判断区间内是否有已知假话
    zero_cnt = [0] * (n + 1)
    for i in range(1, n + 1):
        zero_cnt[i] = zero_cnt[i - 1] + (1 if a[i] == 0 else 0)

    f = [0] * (n + 1)
    f[0] = 1
    for i in range(1, n + 1):
        # 第 i 句填真的贡献
        if a[i] != 0:
            f[i] = f[i - 1]
        # 第 i 句填假的贡献
        if a[i] != 1:
            lo = max(1, i - k + 1)
            # 检查窗口 [lo, i-1] 内是否有已知假话
            if i == 1 or zero_cnt[i - 1] - zero_cnt[lo - 1] == 0:
                prev = max(0, i - k)
                f[i] = (f[i] + f[prev]) % MOD
    print(f[n])

复杂度分析

时间复杂度：O(n)，每个位置的转移为常数时间。 空间复杂度：O(n)，存储 f 数组和前缀和数组。

第三题：连连看

题目描述

一排 n 个位置，初始时第 i 个位置的颜色为 i。接下来进行 t 次操作，第 k 次操作选择位置 x：先找到包含 x 的最大同色连续段 [l, r]，然后将整个 [l, r] 的颜色改为位置 x+1 当前的颜色（即与右边的同色段合并）。

有 q 次询问，每次给出区间 [l, r]，问最早在第几秒该区间内只有一种颜色。若到最后也没实现，输出 -1。

样例

输入

输出

思路分析

第一步：将问题转化为”隔墙消失”

想象相邻位置之间有一道”隔墙”——位置 i 和 i+1 颜色不同时隔墙存在，颜色相同时隔墙消失。区间 [l, r] 颜色全部统一，等价于位置 l 到 r-1 之间的所有隔墙都已消失。因此，查询答案就是这些隔墙中最后一道消失的时刻。

设 mt[i] 为位置 i 和 i+1 之间隔墙消失的时刻。那么查询 [l, r] 的答案就是 max(mt[l], mt[l+1], …, mt[r-1])。

第二步：用并查集模拟合并过程

把颜色相同的连续段看作并查集中的一组，每组记录左端点、右端点和颜色。处理第 k 秒的操作（位置 x）：

查 x 所在段 rx，若 x+1 也在同一段内，说明已经同色，操作无效
否则查 x+1 所在段 ry，将 rx 段的颜色改为 ry 段的颜色，合并两段，记录隔墙消失时刻 mt[rht[rx]] = k
合并后新段的颜色可能与左邻段撞色，需要级联合并：不断检查左邻段是否同色，若同色则继续合并并记录隔墙时刻。每道隔墙最多消失一次，所以级联合并的总开销为 O(n)

第三步：稀疏表回答区间最大值查询

收集完所有 mt[i] 后，需要快速回答”区间最大值”。稀疏表（Sparse Table）花 O(n log n) 时间建表后，每次查询 O(1)。

对于查询 [l, r]：若 l == r（单个位置天然统一），答案为 0；否则取 max(mt[l], …, mt[r-1])，若最大值超过 t 说明有隔墙到最后也没消失，输出 -1。

题解代码

import sys
input = sys.stdin.readline

n, t, q = map(int, input().split())

par = list(range(n + 1))
lft = list(range(n + 1))
rht = list(range(n + 1))
col = list(range(n + 1))
mt = [t + 1] * (n + 1)  # 隔墙消失时刻，初始为 t+1 表示未消失

def find(x):
    while par[x] != x:
        par[x] = par[par[x]]  # 路径压缩
        x = par[x]
    return x

def unite(a, b):
    a, b = find(a), find(b)
    if a == b:
        return a
    # 按段长度合并
    if rht[a] - lft[a] < rht[b] - lft[b]:
        a, b = b, a
    lft[a] = min(lft[a], lft[b])
    rht[a] = max(rht[a], rht[b])
    par[b] = a
    return a

for k in range(1, t + 1):
    x = int(input())
    rx = find(x)
    # 如果 x+1 已在同一段内，操作无效
    if rht[rx] >= x + 1:
        continue
    ry = find(x + 1)
    new_color = col[ry]
    mt[rht[rx]] = k  # 记录隔墙消失时刻
    merged = unite(rx, ry)
    col[merged] = new_color
    # 级联合并：新段可能与左邻段撞色
    while lft[merged] > 1:
        ln = find(lft[merged] - 1)
        if col[ln] != new_color:
            break
        mt[rht[ln]] = k
        merged = unite(merged, ln)
        col[merged] = new_color

# 稀疏表建表，支持 O(1) 区间最大值查询
LOG = max(1, (n - 1).bit_length()) if n > 1 else 1
sp = [[0] * (LOG + 1) for _ in range(n + 1)]
for i in range(1, n):
    sp[i][0] = mt[i]
for j in range(1, LOG + 1):
    for i in range(1, n - (1 << j) + 2):
        sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1])

out = []
for _ in range(q):
    l, r = map(int, input().split())
    if l == r:
        out.append("0")
        continue
    length = r - l
    kk = length.bit_length() - 1
    ans = max(sp[l][kk], sp[r - 1 - (1 << kk) + 1][kk])
    out.append(str(-1 if ans > t else ans))
print("\n".join(out))

复杂度分析

时间复杂度：O(n log n + t·α(n) + q)，稀疏表建表 O(n log n)，并查集操作近线性，每次查询 O(1)。 空间复杂度：O(n log n)，稀疏表占用主要空间。

小结

第一题是经典的符号翻转贪心。核心不变量：一次操作同时翻转两个符号，负数个数的奇偶性不变。偶数个负数可全消，奇数个必须保留一个——让绝对值最小的元素当”牺牲品”，损失最小。
第二题的约束”连续 k 句最多 1 句假话”等价于”任意两句假话间距 ≥ k”，这是 DP 的经典建模。状态 f[i] 表示前 i 句的合法方案数，每个位置考虑填真或填假两种转移，前缀和 O(1) 判断窗口内是否存在冲突。
第三题将”区间颜色统一”转化为”所有隔墙消失”，用并查集维护连续段合并并记录每道隔墙消失时刻，再用稀疏表 O(1) 查询区间最大值。级联合并的均摊复杂度是关键——每道隔墙最多消失一次，保证总开销为 O(n)。

这篇文章有帮助吗？

| GitHub 留言