大厂真题 / 阿里巴巴

阿里 4.1 笔试真题 - 算法岗

本场考试概述

考试时间：2026年4月1日 考试岗位：算法岗 难度评级：简单到中等

考点分析：

第一题：分组排序（难度简单）
第二题：双向枚举 + 试除判质（难度简单）
第三题：分段DP + 分组背包（难度困难）

建议策略：

前两题思路清晰，注意第二题等距取较小的细节
第三题是 DP 难题，关键是先把字符串拆分成连续段，再对每段独立 DP 后背包合并

第一题：等步长交换

题目描述

给定一个长度为 n 的整数数组和一个正整数 k。可以进行任意次操作：选择下标 i（满足 i+k < n），将 a[i] 与 a[i+k] 交换。求最终能得到的字典序最大的数组。

样例

输入

输出

1 4 1 3
6 4 1 3 2
8 7 6

思路分析

第一步：观察题目性质

位置 i 可以和 i+k 交换，通过传递性，所有下标模 k 相同的位置之间可以自由交换。例如 k=2 时，位置 0、2、4 之间可以任意排列，位置 1、3、5 之间也可以任意排列。

第二步：问题转化

将下标按 i % k 分组，同一组内的元素可以任意排列。要让整个数组字典序最大，只需让每一组内的元素降序排列——这样从左到右扫描时，每个位置都能拿到它所在组内剩余最大的元素。

第三步：实现要点

将 n 个元素按 mod k 分成 k 组，每组内部降序排序，再按原始下标顺序依次取出即可。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    # 按 mod k 分组，每组降序排列
    groups = [[] for _ in range(k)]
    for i in range(n):
        groups[i % k].append(a[i])
    for g in groups:
        g.sort(reverse=True)
    # 按原位顺序取出
    idx = [0] * k
    res = []
    for i in range(n):
        g = i % k
        res.append(str(groups[g][idx[g]]))
        idx[g] += 1
    print(" ".join(res))

T = int(input())
for _ in range(T):
    solve()

复杂度分析

时间复杂度：O(n log n)，每组排序的总元素数为 n。 空间复杂度：O(n)，存储分组。

第二题：找质数

题目描述

给定一个整数 x，找到一个质数 p，使得

p - x

尽可能小。如果存在两个质数与 x 距离相同，输出较小的那个。

样例

输入

输出

思路分析

第一步：观察题目性质

x 可达 10^9，不能预筛所有质数。但由 Bertrand 假设，相邻质数间距在 10^9 范围内不超过几百，从 x 向两侧同时扩展即可快速找到。

第二步：算法选择

从 x 开始，先检查 x 本身是否为质数。若不是，令距离 d 从 1 开始递增，每次同时检查 x-d 和 x+d。等距时取较小者。试除法判质只需遍历到 sqrt(n)，在 10^9 量级下只需约 31623 次除法。

第三步：实现要点

试除法的 6k±1 优化可以跳过 2 和 3 的倍数，实际除法次数更少。注意 x-d 可能小于 2，需要额外判断。

题解代码

import sys
input = sys.stdin.readline

def is_prime(n):
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def find_closest(x):
    if is_prime(x):
        return x
    for d in range(1, 1000):
        lo, hi = x - d, x + d
        lo_ok = lo >= 2 and is_prime(lo)
        hi_ok = is_prime(hi)
        # 等距取较小
        if lo_ok:
            return lo
        if hi_ok:
            return hi

T = int(input())
for _ in range(T):
    x = int(input())
    print(find_closest(x))

复杂度分析

时间复杂度：O(G * sqrt(x))，G 为质数间距，实际不超过几百。 空间复杂度：O(1)，只需常数变量。

第三题：字符串分段压缩

题目描述

给定一个只包含 0 和 1 的字符串，长度为 n。可以进行若干次”分段压缩”操作：选择一段由相同字符构成的连续子串，长度为 k，将其整体压缩为一个特殊字符（长度为 1），代价为 a[k]。被压缩过的段不能再次参与压缩，不同压缩段不能重叠。

给定目标长度上限 m，要求将字符串长度压到恰好为 m 的最小总代价。若无法压到长度 m，输出 -1。

样例

输入

3
5 3
00111
3 5 7 9 11
4 2
0101
1 1 1 1
6 2
111000
10 2 5 10 20 50

输出

7
-1
10

思路分析

第一步：观察题目性质

压缩段只能在同字符的连续 run 内部选取，不同 run 之间互不影响。例如 “00111” 分成 run “00”（长度 2）和 “111”（长度 3），每个 run 内部独立决策。

第二步：问题转化

对每个 run 独立求解”减少 r 个长度的最小代价”，然后用分组背包将所有 run 的结果合并，求总共减少 n - m 个长度的最小代价。

第三步：单段 DP

对于一个长度为 L 的连续段，定义 f[i][r] 为处理前 i 个字符、减少长度 r 的最小代价。转移分两种：第 i 个字符不压缩（f[i][r] = f[i-1][r]）；以第 i 个字符结尾取长度为 k 的压缩组（f[i][r] = f[i-k][r-(k-1)] + a[k]）。

第四步：分组背包合并

设 g[r] 为所有段合并后减少 r 长度的最小总代价。逐段合并，最终答案为 g[n-m]。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    s = input().strip()
    a = list(map(int, input().split()))
    target = n - m
    if target == 0:
        print(0)
        return

    # 分割连续段
    runs = []
    i = 0
    while i < n:
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        runs.append(j - i)
        i = j

    INF = float('inf')
    # 全局背包
    g = [INF] * (target + 1)
    g[0] = 0

    for L in runs:
        maxr = min(L - 1, target)
        if maxr <= 0:
            continue
        # 单段DP：f[i][r] = 前i个字符减少r的最小代价
        f = [[INF] * (maxr + 1) for _ in range(L + 1)]
        f[0][0] = 0
        for i in range(1, L + 1):
            for r in range(maxr + 1):
                f[i][r] = f[i - 1][r]
            for k in range(2, i + 1):
                dr = k - 1
                cost = a[k - 1]
                for r in range(dr, maxr + 1):
                    if f[i - k][r - dr] < INF:
                        val = f[i - k][r - dr] + cost
                        if val < f[i][r]:
                            f[i][r] = val
        # 合并到全局背包
        ng = [INF] * (target + 1)
        for r in range(target + 1):
            if g[r] >= INF:
                continue
            for r2 in range(min(maxr, target - r) + 1):
                if f[L][r2] < INF:
                    val = g[r] + f[L][r2]
                    if val < ng[r + r2]:
                        ng[r + r2] = val
        g = ng

    print(g[target] if g[target] < INF else -1)

T = int(input())
for _ in range(T):
    solve()

复杂度分析

时间复杂度：O(n^2)，其中各段 DP 合计 O(ΣL^2)，背包合并 O(n * target)。 空间复杂度：O(n)，单段 DP 表和全局背包数组。

小结

第一题分组排序，核心是发现 mod k 相同的位置可以自由交换，每组降序排列即字典序最大
第二题双向枚举 + 试除判质，从 x 两侧同时扩展找最近质数，等距时取较小者
第三题分段 DP + 分组背包是本场难点，关键在于先把字符串按同字符 run 拆分，每个 run 独立 DP 后用背包合并

这篇文章有帮助吗？

| GitHub 留言