大厂真题 / 阿里巴巴

阿里 4.11 笔试真题 - 算法岗

本场考试概述

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

考点分析：

第一题：字符映射（难度中等）
第二题：构造（同奇偶配对）（难度困难）
第三题：动态规划（位集优化）（难度困难）

建议策略：

第一题关键在于发现只需维护 26 个字母的映射关系而非逐次扫描整个字符串
第二题需要深入观察同奇偶数的和差性质，边界情况较多
第三题是模 k 子集和的经典 DP，熟悉位集优化可以大幅提升效率

第一题：轮转

题目描述

给你一个长度为 n 的字符串 s，接下来进行 q 次操作。每次操作给出字符 x 和 y，将当前字符串里所有的字符 x 替换为字符 y。输出完成所有操作后的字符串。

样例

输入

2
3 2
abc
a b
b c
5 1
abcde
a z

输出

ccc
zbcde

思路分析

第一步：观察题目性质

数据规模 n, q 可达 10^5，逐次扫描字符串替换的暴力做法是 O(nq)，会超时。但每次操作只涉及 26 个小写字母之间的映射变换。

第二步：问题转化

维护一个长度为 26 的映射数组 mp，其中 mp[c] 表示原始字符 c 经过所有已处理操作后最终会变成什么字符。对于每次操作 x → y，遍历映射数组，将所有 mp[c] == x 的位置改为 y。这一步仅需 O(26) 时间。

第三步：实现要点

处理完所有操作后，对原始字符串的每个字符查表 mp 即得最终字符。

题解代码

import sys
input = sys.stdin.readline

def solve(s, ops):
    # mp[c] 记录字符 c 最终会变成什么
    mp = list(range(26))
    for x, y in ops:
        for c in range(26):
            if mp[c] == x:
                mp[c] = y
    return ''.join(chr(mp[ord(ch) - 97] + 97) for ch in s)

T = int(input())
for _ in range(T):
    n, q = map(int, input().split())
    s = input().strip()
    ops = []
    for _ in range(q):
        parts = input().split()
        ops.append((ord(parts[0]) - 97, ord(parts[1]) - 97))
    print(solve(s, ops))

复杂度分析

时间复杂度：O(26q + n)，每次操作扫描映射表 O(26)，最后遍历字符串 O(n)。 空间复杂度：O(n)，存储字符串和映射表。

第二题：凑对

题目描述

构造一个 1 到 n 的排列（n 为偶数），使得每对相邻位置 (a[2i-1], a[2i]) 的和与差的绝对值都不是质数。若不存在合法排列，输出 -1。

样例

输入

2
2
12

输出

-1
7 8 5 4 1 9 2 12 3 11 6 10

思路分析

第一步：观察题目性质

两个同奇偶的数，和与差都是偶数。大于 2 的偶数一定不是质数。因此只需保证差不等于 2（即两数不相差 2），同时和也不等于 2（最小的两个同奇偶数之和至少为 1+3=4，必然满足）。

第二步：问题转化

将 1 到 n 按奇偶分成两组，每组内部排序后对半拆分配对。第 i 个前半元素与第 i 个后半元素配对，差值恒为 n/2（即组长度），当 n >= 8 时 n/2 >= 4 是大于 2 的偶数，必定不是质数。

第三步：实现要点

当 n <= 6 时（即 n=2,4,6），可以枚举验证不存在合法排列，输出 -1。当 n % 4 == 2 且 n >= 10 时，奇偶组各有奇数个元素，先取出跨奇偶对 (4,5)（和为 9、差为 1，均非质数），再对剩余元素分组配对。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    if n <= 6:
        print(-1)
        return
    result = []
    if n % 4 == 0:
        # 奇数组和偶数组各自对半配对
        odds = list(range(1, n, 2))
        evens = list(range(2, n + 1, 2))
        m = len(odds)
        for i in range(m // 2):
            result.extend([odds[i], odds[i + m // 2]])
        m = len(evens)
        for i in range(m // 2):
            result.extend([evens[i], evens[i + m // 2]])
    else:
        # n%4==2, n>=10: 先用跨奇偶对 (4,5), sum=9, diff=1
        result.extend([4, 5])
        odds = [x for x in range(1, n, 2) if x != 5]
        evens = [x for x in range(2, n + 1, 2) if x != 4]
        m = len(odds)
        for i in range(m // 2):
            result.extend([odds[i], odds[i + m // 2]])
        m = len(evens)
        for i in range(m // 2):
            result.extend([evens[i], evens[i + m // 2]])
    print(' '.join(map(str, result)))

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

复杂度分析

时间复杂度：O(n)，构造排列只需线性遍历。 空间复杂度：O(n)，存储结果排列。

第三题：模 k 最大子序列

题目描述

给定一个长度为 n 的整数数组 a 和正整数 k。选择一个非空子序列（不要求连续），使元素之和对 k 取模的结果最大。

样例

输入

输出

4
0
3

思路分析

第一步：观察题目性质

从数组中选非空子序列，使元素和 mod k 最大。这本质上是一个模 k 子集和问题：需要判断 [0, k-1] 中哪些余数可达，暴力枚举 2^n 个子集不可行。

第二步：问题转化

我们只关心子序列和对 k 的余数，而非具体和值。可以用布尔数组 f 记录可达余数集合，每加入一个元素 x（余数 v = x % k），已有的每个可达余数 j 变为 (j + v) % k。

第三步：算法选择——位集优化

在 Python 中，可将 f 压缩为一个 k 位整数（位集）。加入元素余数 v 等价于对位集做循环左移 v 位再取并集。单次操作仅需 O(k/w) 的位运算（w 为机器字长），总复杂度 O(nk/w)。

题解代码

import sys
input = sys.stdin.readline

def solve(n, k, a):
    # 用整数位集表示可达余数集合，第 j 位为 1 表示余数 j 可达
    f = 0
    mask = (1 << k) - 1
    for x in a:
        v = x % k
        # 循环左移 v 位：已有余数 j 变为 (j+v) % k
        shifted = ((f << v) | (f >> (k - v))) & mask
        shifted |= (1 << v)  # 单独选这个元素
        f |= shifted
    # 从高位往低位找第一个 1
    for j in range(k - 1, -1, -1):
        if f & (1 << j):
            return j
    return 0

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

复杂度分析

时间复杂度：O(nk/w)，其中 w 为机器字长，Python 大整数位运算常数较大但仍可接受。 空间复杂度：O(k/w)，存储可达余数集合的位集。

小结

第一题字符映射，维护 26 个字母的映射表而非逐次扫描字符串，O(26q + n) 高效解决
第二题同奇偶配对构造，核心是发现同奇偶数的和差都是偶数，对半配对保证差值为大偶数
第三题位集优化 DP，将模 k 子集和问题压缩为整数位运算，循环左移实现余数转移

这篇文章有帮助吗？

| GitHub 留言