蚂蚁笔试 蚂蚁笔试题 蚂蚁 0326 春招实习笔试真题

笔试时间：2026年3月26日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：排列拼接

题目

给定两个长度为 n 的排列 a 与 b。你可以进行如下操作一次：

选择一个正整数 k，构造数组 c，将排列 a 按原顺序在 c 的末尾依次复制 k 份，得到长度为 n×k 的数组 c；形式化地，对任意 1≤i≤k 与 1≤j≤n，都有 c[(i-1)×n+j] = a[j]。你希望数组 c 中存在至少一个子序列，其按顺序拼接后与排列 b 完全相同。请计算满足该条件的最小 k。

排列： 长度为 n 的排列是由 1 ~ n 这 n 个整数按任意顺序组成的数组，其中每个整数恰好出现一次。

子序列： 子序列为从原序列中删除任意个（可以为零，也可以为全部）元素后，保持相对顺序得到的新序列。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T (1≤T≤10^5) 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 n (1≤n≤10^5) 表示排列长度；
• 第二行输入 n 个整数 a1, a2, ..., an 表示排列 a；
• 第三行输入 n 个整数 b1, b2, ..., bn 表示排列 b。

除此之外，保证单个测试文件的 n 之和不超过 10^5。

输出描述

对于每一组测试数据，新起一行。输出一个整数，表示使得 b 能作为 c 的一个子序列出现所需的最小 k。

样例输入

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

样例输出

2
4

参考题解

解题思路

本题的核心目标是让排列 b 成为拼接数组 c 的子序列，且要求重复次数 k 最小。因为 a 和 b 都是长度为 n 的排列（元素完全没有重复），我们可以记录下每个元素在排列 a 中的索引位置 pos。采取贪心策略遍历排列 b：

1. 我们要在数组 c 中按顺序找到 b 中的每一个元素。
2. 假设当前我们在排列 a 中的第 curr_pos 个位置匹配了 b[i]。接下来要匹配 b[i+1]，我们查找 b[i+1] 在排列 a 中的位置 next_pos。
3. 如果 next_pos > curr_pos，说明 b[i+1] 在 a 中出现的位置比 b[i] 靠后，我们可以在同一个副本中顺便把 b[i+1] 也匹配掉。
4. 如果 next_pos <= curr_pos，说明在当前这一个 a 的副本里，找完 b[i] 后，后面已经没有 b[i+1] 了。我们必须开启一个新的 a 的副本，也就是重复次数 k 必须加 1。
5. 遍历完 b 数组即可得到最小的 k。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];

        // 记录 a 中每个元素对应的索引位置
        vector<int> pos(n + 1);
        for (int i = 0; i < n; i++) pos[a[i]] = i;

        int k = 1;
        int currPos = pos[b[0]];
        for (int i = 1; i < n; i++) {
            int nextPos = pos[b[i]];
            if (nextPos <= currPos) {
                k++;
            }
            currPos = nextPos;
        }

        cout << k << "\n";
    }

    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());

            int[] a = new int[n], b = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) b[i] = Integer.parseInt(st.nextToken());

            // 记录 a 中每个元素对应的索引位置
            int[] pos = new int[n + 1];
            for (int i = 0; i < n; i++) pos[a[i]] = i;

            int k = 1;
            int currPos = pos[b[0]];
            for (int i = 1; i < n; i++) {
                int nextPos = pos[b[i]];
                if (nextPos <= currPos) {
                    k++;
                }
                currPos = nextPos;
            }

            sb.append(k).append("\n");
        }

        System.out.print(sb);
    }
}

Python

import sys

def solve():
    input = sys.stdin.readline
    T = int(input())
    out = []
    for _ in range(T):
        n = int(input())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))

        # 记录 a 中每个元素对应的索引位置
        pos = [0] * (n + 1)
        for i in range(n):
            pos[a[i]] = i

        k = 1
        curr_pos = pos[b[0]]
        for i in range(1, n):
            next_pos = pos[b[i]]
            if next_pos <= curr_pos:
                k += 1
            curr_pos = next_pos
        out.append(str(k))
    sys.stdout.write('\n'.join(out) + '\n')

solve()

第二题：该回家了

题目

给定一张由 n 行、m 列组成的地图。用字符 0 表示天才同学的别墅位置，用字符 1 表示其他位置。对于地图上的每一个位置，定义其到最近别墅的距离为：从该位置出发，每次可以向上、下、左、右四个方向走一步（曼哈顿距离的一步），到达任意一个 0 所需要的最少步数。若该位置本身就是 0，则距离为 0。

输入描述

在一行上输入两个整数 n, m (1≤n,m≤10^3)，表示地图的行数与列数。此后 n 行，每行输入一个长度为 m 的字符串 s，仅由字符 0 和 1 组成。保证至少存在一个位置为 0。

输出描述

输出 n 行。第 i 行输出 m 个整数，分别表示第 i 行每个位置到最近 0 的最短步数。相邻整数之间使用一个空格分隔。

样例输入

3 4
0111
0011
1111

样例输出

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

样例说明

对于样例中第 1 行第 1 列位置是 0，因此距离为 0；第 1 行第 4 列到最近 0 的最短路径长度为 3（一种方法是向左走三步）。

参考题解

解题思路

这道题是一个非常经典的多源最短路径问题（Multi-source BFS），在无权网格图上求最短曼哈顿距离。

1. 我们不需要对每一个 1 都跑一遍搜索，那样会导致 O(n²m²) 的复杂度，绝对会超时。
2. 正确的做法是"反向思考"：把所有别墅 0 视为起点（Source），将它们的初始距离设为 0，并同时推入队列。
3. 通过队列进行广度优先搜索（BFS），每次弹出一个位置，向上下左右四个方向扩展。只要遇到了还没有被访问过的位置，就将它的距离设为当前节点的距离 + 1，并推入队列。
4. 这样就能保证每一个点都是被离它最近的 0 给搜索到的，时间复杂度为 O(n×m)，非常高效。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    for (int i = 0; i < n; i++) cin >> grid[i];

    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    // 找到所有别墅 '0' 的位置，作为多源 BFS 的起点
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '0') {
                dist[i][j] = 0;
                q.push({i, j});
            }
        }
    }

    // 方向数组：上、下、左、右
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    // 开始 BFS
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        int d = dist[r][c];
        for (int k = 0; k < 4; k++) {
            int nr = r + dx[k], nc = c + dy[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && dist[nr][nc] == -1) {
                dist[nr][nc] = d + 1;
                q.push({nr, nc});
            }
        }
    }

    // 输出
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j >