Akuna OA SDE NG｜OA2 三题真题解析：最少交换、配送排序、电影选择

Akuna 今年发放量大，OA 做完之后一小时收到 OA2。实际体验下来，OA2 想一把过风险不小，第一次接触或不熟练的同学还是建议优先把真题思路理清。三道题用 Hackerrank，覆盖置换环、BFS 和动态规划，都不是纯背模板能过的。

Question 1：按降序排列的最少交换次数

题意

给定一个元素互不相同的数组，每次可以交换任意两个位置，要求计算将数组按降序排列所需的最少交换次数。

思路

先复制并按降序得到目标数组，再建立每个元素在原数组中的位置映射；从左到右检查错位元素，将当前位置的元素与目标元素所在位置交换，并同步更新映射。也可以把位置关系看成若干个置换环：每个长度为 k 的环最少需要交换 k-1 次，累加所有环即可，最少交换次数等于 n 减环数。

def min_swaps_desc(arr):
    target = sorted(arr, reverse=True)
    pos = {v: i for i, v in enumerate(arr)}
    swaps = 0
    for i in range(len(arr)):
        while arr[i] != target[i]:
            j = pos[target[i]]
            arr[i], arr[j] = arr[j], arr[i]
            pos[arr[j]] = j
            pos[arr[i]] = i
            swaps += 1
    return swaps

时间复杂度 O(n log n)（排序主导），交换过程 O(n)。每次交换要同步更新 pos 映射，否则后续定位会错；元素互不相同是能直接用值映射的前提。

Question 2：配送城市排序

题意

给定若干城市及连接它们的双向道路，从公司所在城市出发，按最短距离由近到远安排配送；若多个城市距离相同，优先配送编号较小的城市；无法到达的城市不输出，公司所在城市本身也不计入结果。

思路

建立无向图并从起点执行 BFS，记录每座可达城市的最短距离，再将这些城市按 (距离, 城市编号) 升序排序后输出。

from collections import deque

def delivery_order(n, roads, start):
    graph = [[] for _ in range(n)]
    for u, v in roads:
        graph[u].append(v)
        graph[v].append(u)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    reachable = [(dist[i], i) for i in range(n) if i != start and dist[i] != -1]
    reachable.sort()
    return [i for _, i in reachable]

时间复杂度 O(n + m + n log n)，n 为城市数、m 为道路数。BFS 保证最短距离；排序键用 (距离, 编号) 元组，天然满足距离相同时按编号升序。

Question 3：电影评分选择

题意

从电影评分数组中按原顺序选择若干部电影，使评分总和最大，但不能连续跳过两部电影。

思路

由于评分可能为负数，不能套用「相邻元素不能同时选择」的打家劫舍转移。维护两个状态：take 表示选择当前电影时的最大得分，skip 表示跳过当前电影时的最大得分。转移为 newTake = max(take, skip) + rating[i]（当前电影被选，前一部选或跳都行），newSkip = take（当前电影若跳过，上一部必须被选择）。遍历结束后返回 max(take, skip)。

def max_rating(ratings):
    take = skip = 0
    for r in ratings:
        new_take = max(take, skip) + r
        new_skip = take
        take, skip = new_take, new_skip
    return max(take, skip)

时间复杂度 O(n)，空间复杂度 O(1)。关键在于「不能连续跳过两部」这个约束翻译成「若跳过当前，上一部必须选」，也就是 newSkip = take，而不是 max(take, skip)。

FAQ

最少交换次数为什么是 n 减置换环个数？

一个长度为 k 的置换环用 k-1 次交换即可全部归位，各环互不影响，所以总次数等于 (k1-1)+(k2-1)+… = n - 环数。

电影选择题为什么不能直接套打家劫舍？

评分有负数时，「不选当前」不一定更优，且约束是「不能连续跳两部」而不是「不能相邻选两部」，状态含义和转移都要按题意重定义，直接套模板会错。

参考来源

• LeetCode 41 — First Missing Positive
• LeetCode 207 — Course Schedule
• LeetCode 198 — House Robber

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。