Zero2Leetcode

大厂真题 / 阿里巴巴

阿里 4.1 笔试真题 - 研发岗

本场考试概述

考试时间：2026年4月1日 考试岗位：研发岗 难度评级：中等偏难

考点分析：

  1. 第一题：贪心（难度简单）
  2. 第二题：差值约束 + BFS建图（难度中等）
  3. 第三题：前缀和 + 平衡计数（难度困难）

建议策略：

  1. 第一题贪心思路直观，先拿满分稳住心态
  2. 第二题关键在于把差值约束建成带权图，想清楚边权含义是核心
  3. 第三题需要推导中位数条件，将问题转化为前缀和配对，有一定推导难度

第一题：数组对齐

题目描述

给定两个长度均为 n 的非负整数数组 a 与 b。可以反复执行以下三种操作（每次操作使所选元素的值减 1；若元素当前为 0 则不允许执行）：

  • 操作1：选择一个下标 i，令 a[i] -= 1。
  • 操作2：选择一个下标 i，令 b[i] -= 1。
  • 操作3：选择两个下标 i, j（可以相同），同时令 a[i] -= 1 且 b[j] -= 1。

通过若干次操作，使得最终对所有 i 都满足 a[i] == b[i]。求最少操作次数。

样例

输入

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

输出

2
5

题解：贪心

每个位置 i 只能做减法，所以 a[i] 和 b[i] 最终一定等于 min(a[i], b[i])。设 d[i] = a[i] - b[i]，若 d[i] > 0 说明 a 侧需要减 d[i]，若 d[i] < 0 说明 b 侧需要减 d[i] 。
设 sum_a = 所有 d[i] > 0 的 d[i] 之和，sum_b = 所有 d[i] < 0 的 d[i] 之和。操作3 可以同时消耗 a 侧 1 点和 b 侧 1 点，贪心策略是尽量多用操作3 来把两侧消耗并行处理，最多使用 min(sum_a, sum_b) 次，剩余差额只能用操作1 或操作2 逐一消耗。因此答案为 max(sum_a, sum_b)。

时间复杂度：O(n)。 空间复杂度：O(1)。

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    sum_a = sum_b = 0
    for i in range(n):
        d = a[i] - b[i]
        if d > 0:
            sum_a += d
        else:
            sum_b += -d
    print(max(sum_a, sum_b))

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

第二题：约束差值数组

题目描述

构造一个长度为 n 的正整数数组，其中每个元素在 [1, 10^18] 范围内。给定 m 条约束，每条约束给出三元组 (u, v, k)，要求 a[u] - a[v] = k。判断是否存在满足所有约束的数组。若存在则输出任意一个符合条件的数组；否则输出 -1。

样例

输入

2
3 2
1 2 1
2 3 1
2 2
1 2 100
2 1 1

输出

3 2 1
-1

题解：BFS建图

约束 a[u] - a[v] = k 把变量之间建立了严格的线性关系。在同一连通分量内，只要确定一个变量的值，其余所有变量的值都被唯一确定。

建图：每条约束 (u, v, k) 建两条有向边：u -> v 权重 -k，v -> u 权重 k。边权含义是”从已知节点推算邻居时需要加上的偏移量”。

BFS 赋值：对每个未赋值节点出发做 BFS，起点临时赋值 0，沿边推导邻居的值。若到达已赋值节点时发现新旧值矛盾，则无解输出 -1。

平移为正整数：BFS 得到的值可能有负数或零。找到连通分量内最小值 mn，将所有值加上 (1 - mn) 使最小值恰好为 1，再检查最大值是否超过 10^18。

时间复杂度：O(n + m)。 空间复杂度：O(n + m)。

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

def solve():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, k = map(int, input().split())
        adj[u].append((v, -k))
        adj[v].append((u, k))

    val = [None] * (n + 1)
    ok = True

    for s in range(1, n + 1):
        if val[s] is not None:
            continue
        val[s] = 0
        q = deque([s])
        comp = [s]
        while q and ok:
            u = q.popleft()
            for v, w in adj[u]:
                if val[v] is None:
                    val[v] = val[u] + w
                    q.append(v)
                    comp.append(v)
                elif val[v] != val[u] + w:
                    ok = False
                    break
        if not ok:
            break
        mn = min(val[x] for x in comp)
        shift = 1 - mn
        for x in comp:
            val[x] += shift
        mx = max(val[x] for x in comp)
        if mx > 10**18:
            ok = False
            break

    if not ok:
        print(-1)
    else:
        print(" ".join(str(val[i]) for i in range(1, n + 1)))

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

第三题：中，太中了

题目描述

给定一个长度为 n 的排列 a，对每个位置 i，统计元素 a[i] 在多少个连续子区间中恰好是该子区间的中位数。

中位数定义：对于长度为 len 的数组，将所有元素从小到大排序后，位于第 ceil(len/2) 个位置的元素即为中位数。

样例

输入

2
3
1 2 3
3
2 1 3

输出

1 3 2
3 1 2

题解：前缀和 + 平衡计数

暴力枚举所有子区间再排序是 O(n^3 log n)，远超时限。核心观察：判断 a[i] 是否为子区间的中位数，不需要排序，只要看区间里比 a[i] 大的和比 a[i] 小的元素个数的关系。

中位数条件推导：设区间 [l, r] 中比 a[i] 小的有 s 个、比 a[i] 大的有 g 个。a[i] 是中位数等价于 g == s（奇数长度子区间）或 g == s + 1（偶数长度子区间）。给区间内除 a[i] 外的元素打标记：大于记 +1，小于记 -1，则标记总和 balance = g - s。中位数条件变为 balance == 0 或 balance == 1。

前缀和配对：包含位置 i 的子区间的标记和可拆为左半前缀和与右半前缀和。先向左扫描把每种前缀和值的出现次数存入计数数组，再向右扫描对每个 pre_right 查询配对的 -pre_right 和 -pre_right - 1 对应的个数，累加到答案。

时间复杂度：O(n^2)。 空间复杂度：O(n)。

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = [0] * n
    offset = n + 2
    sz = 2 * n + 5

    for i in range(n):
        cnt = [0] * sz
        cnt[0 + offset] = 1
        cur = 0
        # 向左扩展，统计左侧前缀和频次
        for j in range(i - 1, -1, -1):
            cur += 1 if a[j] > a[i] else -1
            cnt[cur + offset] += 1
        # 向右扩展并匹配
        res = 0
        cur = 0
        for r in range(i, n):
            if r > i:
                cur += 1 if a[r] > a[i] else -1
            res += cnt[-cur + offset]
            res += cnt[-cur - 1 + offset]
        ans[i] = res

    print(" ".join(map(str, ans)))

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

小结

  • 第一题贪心，核心是观察到操作3可以并行消耗两侧差值，答案即为两侧差值总和的较大者
  • 第二题差值约束转化为带权图 BFS，逐连通分量赋值后平移至正整数范围，注意矛盾检测
  • 第三题前缀和+平衡计数是中位数类问题的经典技巧，将”排序后第 k 个”转化为大小关系计数，再利用前缀和配对高效统计