大厂真题 / 阿里巴巴

阿里 3.28 笔试真题 - 算法岗

本场考试概述

考试时间：2026年3月28日 考试岗位：算法岗 难度评级：中等

考点分析：

第一题：数学推导/博弈（难度简单）
第二题：枚举/完全平方数判断（难度中等）
第三题：排序 + 并查集（难度中等偏难）

建议策略：

第一题数学推导出 A-B 是常数，O(n) 秒杀
第二题枚举所有完全平方数逐个检查切分点，注意前导零
第三题离线排序 + 并查集合并，需要熟悉并查集模板

第一题：回合制游戏

题目描述

给定两个长度均为 n 的整数数组 a 与 b，进行一场回合制对抗游戏。Alice 先手，两人轮流选择未被选择的位置。Alice 选位置 i 净收益为 a[i]-b[i]，Bob 选位置 j 净收益为 b[j]-a[j]。

Alice 希望最大化 A-B，Bob 希望最小化 A-B，双方完全理性。求最优博弈下的分差 A-B。

样例

输入

输出

0
0
-5

题解：数学推导

无论双方如何选择，A - B 恒等于 sum(a) - sum(b)，是一个与策略无关的常数。直接计算两个数组的元素和之差即可。

时间复杂度：O(n)。

import sys
input = sys.stdin.readline

def main():
    T = int(input())
    out = []
    for _ in range(T):
        n = int(input())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        out.append(str(sum(a) - sum(b)))
    print("\n".join(out))

main()

第二题：完全平方数

题目描述

定义”完完全全平方数”：该数本身是完全平方数，且存在一个切分点将十进制表示切为两段，两段均非空且都是完全平方数（不允许前导零，除非该段仅为 0）。

给定上界 n，问不超过 n 的完完全全平方数共有多少个。

样例

输入

1
1500

输出

题解：枚举

n <= 10^9，完全平方数最多约 31623 个，直接枚举每个完全平方数并检查所有切分点。

时间复杂度：O(sqrt(n) * D)，D 为数字位数（最多 10）。

import sys
input = sys.stdin.readline
from math import isqrt

def is_perfect_square(x):
    if x < 0:
        return False
    s = isqrt(x)
    return s * s == x

def check(x):
    s = str(x)
    for j in range(1, len(s)):
        left, right = s[:j], s[j:]
        if len(left) > 1 and left[0] == '0':
            continue
        if len(right) > 1 and right[0] == '0':
            continue
        if is_perfect_square(int(left)) and is_perfect_square(int(right)):
            return True
    return False

def main():
    T = int(input())
    out = []
    for _ in range(T):
        n = int(input())
        count = sum(1 for i in range(1, isqrt(n) + 1) if check(i * i))
        out.append(str(count))
    print("\n".join(out))

main()

第三题：弦上生花

题目描述

给定由 n 个整数构成的数组 a，对于每个整数 k (1 <= k <= n)，求最长连续子数组使得所有相邻元素差的绝对值不超过 k。

样例

输入

1
5
1 3 5 2 4

输出

1 3 5 5 5

题解：排序 + 并查集

令 d[i] =

a[i+1] - a[i]

，随着 k 增大，越来越多的 d[i] 被”激活”，相邻段合并变长。按 d 值从小到大排序后逐步用并查集合并，维护最大连通块。

时间复杂度：O(n log n)。

import sys
input = sys.stdin.readline

def main():
    T = int(input())
    out = []
    for _ in range(T):
        n = int(input())
        a = list(map(int, input().split()))
        if n == 1:
            out.append("1")
            continue

        par = list(range(n))
        sz = [1] * n

        def find(x):
            while par[x] != x:
                par[x] = par[par[x]]
                x = par[x]
            return x

        def unite(x, y):
            px, py = find(x), find(y)
            if px == py:
                return sz[px]
            if sz[px] < sz[py]:
                px, py = py, px
            par[py] = px
            sz[px] += sz[py]
            return sz[px]

        edges = sorted((abs(a[i + 1] - a[i]), i) for i in range(n - 1))

        ans = [0] * (n + 1)
        max_sz, ei = 1, 0
        for k in range(1, n + 1):
            while ei < n - 1 and edges[ei][0] <= k:
                max_sz = max(max_sz, unite(edges[ei][1], edges[ei][1] + 1))
                ei += 1
            ans[k] = max_sz
        out.append(" ".join(str(ans[k]) for k in range(1, n + 1)))
    print("\n".join(out))

main()

小结

第一题博弈看似复杂，数学推导后发现 A-B 是常数 sum(a)-sum(b)
第二题枚举所有完全平方数并检查切分点，注意前导零判断
第三题离线排序 + 并查集是经典套路：随阈值递增逐步合并，维护最大连通块

这篇文章有帮助吗？

| GitHub 留言