大厂真题 / 阿里巴巴

阿里 4.8 笔试真题 - 研发岗

本场考试概述

考试时间：2026年4月8日 考试岗位：研发岗 难度评级：困难

考点分析：

第一题：哈希集合 + 枚举分割点（难度中等）
第二题：奇偶分组贪心（难度困难）
第三题：离线树状数组（难度困难）

建议策略：

第一题是字符串哈希枚举，思路直接，优先保分
第二题需要发现”操作不改变 i+j 奇偶性”这一关键性质，需要一定观察力
第三题是经典离线 + 树状数组组合，需要较强的算法基础

第一题：可删去的字符串

题目描述

给你 n 个字符串。称某个字符串是”可删去的”，当且仅当它能由序列中两个不同位置的非空字符串拼接而成。统计满足条件的字符串下标数量。

样例

输入

2
5
a
b
ab
abc
bc
4
a
aa
a
aaa

输出

2
2

思路分析

第一步：观察题目性质

对于每个字符串 s_i，如果它长度为 L，则至多有 L-1 个分割点。只要枚举每个分割点，判断左半段和右半段是否同时出现在集合中即可。

第二步：问题转化

所有字符串的分割点总数等于”字符串总长度”，因此整体复杂度只与总长度线性相关。将所有字符串放入哈希集合，并用计数器记录每个字符串的出现次数。

第三步：实现要点

对每个 s_i 枚举分割点 k，得到 a = s_i[:k] 与 b = s_i[k:]。若 a != b，两者都在集合中即可；若 a == b，需要该字符串出现至少 2 次。

题解代码

import sys
from collections import Counter
input = sys.stdin.readline

def solve():
    n = int(input())
    strs = [input().strip() for _ in range(n)]
    cnt = Counter(strs)

    ans = 0
    for s in strs:
        L = len(s)
        ok = False
        for k in range(1, L):
            a, b = s[:k], s[k:]
            if a not in cnt or b not in cnt:
                continue
            # 若 a == b 需要两个不同位置都等于 a
            if a != b or cnt[a] >= 2:
                ok = True
                break
        if ok:
            ans += 1
    print(ans)

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

复杂度分析

时间复杂度：O(S)，其中 S 为所有字符串总长度。每个分割点的子串构造与哈希查找均摊为常数。 空间复杂度：O(S)，用于存放所有字符串及哈希集合。

第二题：网格路径最大和

题目描述

给定一个 2×n 的网格。可以任意次交换 a[0][j] 与 a[1][j+1]（即交换异行且列号相差 1 的两个格子）。交换完成后，从 (0,0) 出发只能向下或向右走到 (1,n-1)，求路径上元素之和的最大值。

样例

输入

输出

8
24

思路分析

第一步：观察题目性质

每次操作交换 a[0][j] 与 a[1][j+1]，被交换的两格的坐标和 (i+j) 同奇偶。因此所有操作都不改变每个值所在格子的 (i+j) 奇偶性——每个值始终待在它原本属于的”奇偶类”里。

第二步：问题转化

同奇偶类内部可以任意置换（连通性可证明），但两类之间不能混。从 (0,0) 走到 (1,n-1) 的路径恰好包含 ceil((n+1)/2) 个偶格和 floor((n+1)/2) 个奇格。

第三步：算法选择

将原网格 2n 个数按 (i+j) 的奇偶分入两组。偶组取前 ceil((n+1)/2) 大、奇组取前 floor((n+1)/2) 大，二者之和即为答案。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    row0 = list(map(int, input().split()))
    row1 = list(map(int, input().split()))

    evens = []
    odds = []
    for j in range(n):
        # row0[j] 的坐标和为 0+j=j
        if j % 2 == 0:
            evens.append(row0[j])
        else:
            odds.append(row0[j])
        # row1[j] 的坐标和为 1+j
        if (1 + j) % 2 == 0:
            evens.append(row1[j])
        else:
            odds.append(row1[j])

    evens.sort(reverse=True)
    odds.sort(reverse=True)
    # 路径包含 ceil((n+1)/2) 个偶格，floor((n+1)/2) 个奇格
    ke = (n + 2) // 2
    ko = (n + 1) // 2
    ans = sum(evens[:ke]) + sum(odds[:ko])
    print(ans)

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

复杂度分析

时间复杂度：O(n log n)，瓶颈是两次排序。 空间复杂度：O(n)，用于保存两个分组数组。

第三题：相邻等值对贡献和

题目描述

给定一个长度为 n 的数组。称一对下标 (i,j) 为”相邻等值对”，当且仅当 i < j，a[i] = a[j]，且对于任意 i < k < j 都有 a[k] != a[i]（即 i 和 j 是同一个值在数组中相邻的两次出现）。

对每个相邻等值对 (i,j)，定义其贡献为区间 (i,j) 内严格小于 a[i] 的元素个数。求所有相邻等值对的贡献之和。

样例

输入

2
5
2 1 2 1 2
6
3 2 2 1 3 2

输出

2
4

思路分析

第一步：观察题目性质

枚举所有相邻等值对 (i,j)，需要快速回答”区间 [i+1,j-1] 内值小于 a[i] 的元素个数”。等值对最多 n 个，若每次朴素扫描则总复杂度可达 O(n^2)，无法承受。

第二步：问题转化

所有询问都是”区间 + 阈值”形式，且阈值就是等值对的值。把询问按阈值升序排序后，每个询问要求”位置在 [i+1,j-1] 且值 < v 的元素个数”。

第三步：算法选择——离线 + 树状数组

把所有原数组下标按值升序排序，用双指针配合询问推进。处理阈值 v 的询问前，先把所有值 < v 的下标插入树状数组（标记为 1），然后对每个询问做一次区间前缀和差，即可得到区间内值 < v 的元素计数。每个下标只插入一次，总复杂度 O(n log n)。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    # 树状数组
    bit = [0] * (n + 2)

    def add(i):
        i += 1
        while i <= n:
            bit[i] += 1
            i += i & -i

    def pre(i):
        i += 1
        r = 0
        while i > 0:
            r += bit[i]
            i -= i & -i
        return r

    def query(l, r):
        if l > r:
            return 0
        return pre(r) - (pre(l - 1) if l > 0 else 0)

    # 收集相邻等值对
    prev_pos = {}
    queries = []  # (阈值v, l, r)
    for i in range(n):
        v = a[i]
        if v in prev_pos:
            queries.append((v, prev_pos[v] + 1, i - 1))
        prev_pos[v] = i

    # 下标按值升序排列
    idx_order = sorted(range(n), key=lambda x: a[x])
    # 查询按阈值升序排列
    queries.sort()

    ptr = 0
    ans = 0
    for v, l, r in queries:
        # 把所有值 < v 的位置插入树状数组
        while ptr < n and a[idx_order[ptr]] < v:
            add(idx_order[ptr])
            ptr += 1
        ans += query(l, r)

    print(ans)

T = int(input())
for _ in range(T):
    # 重置树状数组需要在 solve 内部
    solve()

复杂度分析

时间复杂度：O(n log n)，每个下标只插入一次，每次查询是树状数组的两次前缀和。 空间复杂度：O(n)，用于存储数组、树状数组以及查询列表。

小结

第一题哈希集合 + 枚举分割点，所有分割点总数等于字符串总长度，线性复杂度
第二题奇偶分组贪心，核心是发现交换操作不改变 (i+j) 奇偶性，同类内部可任意置换
第三题离线树状数组，按阈值升序排列询问和元素，双指针 + 树状数组实现 O(n log n) 查询

这篇文章有帮助吗？

| GitHub 留言