淘天/阿里国际2025实习笔试算法题深度解析：从“不相邻偶数对”到“环形黄蓝灯”

1. 笔试概况与备战策略

淘天集团与阿里国际的实习笔试向来以高难度著称，2025届的笔试结构延续了往年的风格：选择题（27分/9题）、不定项选择题（18分/6题）和算法题（55分/3题）。根据考生反馈，算法题往往决定成败，而选择题则覆盖操作系统、数据库、设计模式等计算机基础。

高效备战建议：

• 时间分配：建议按"5:3:2"分配准备时间，50%精力专攻算法，30%巩固计算机基础，20%模拟实战
• 核心算法重点突破：
  • 动态规划（背包问题、状态机模型）
  • 图论（DFS/BFS、拓扑排序、最短路径）
  • 贪心算法（区间调度、环形处理）
  • 数学思维（组合计数、奇偶分析）

提示：阿里系笔试常考察"变形题"，即在经典算法题基础上增加特殊约束条件（如环形结构、不相邻限制等），需重点练习这类题型。

2. 不相邻偶数对问题解析

题目描述： 给定长度为n的数组a，要求统计有多少对(i,j)满足：

1. i ≠ j 且 |i-j| > 1（不相邻）
2. a[i] + a[j] 为偶数

示例： 输入：5 [1, 2, 3, 4, 6]
输出：3（有效组合：1+3, 2+4, 2+6）

2.1 数学建模与优化思路

关键观察：

• 偶数 = 奇+奇 或 偶+偶
• 总对数 = C(odd,2) + C(even,2) - 相邻奇数对 - 相邻偶数对

优化解法步骤：

1. 统计奇数总数odds和偶数总数evens
2. 遍历数组，对每个元素a[i]：
   • 若a[i]为奇数：有效对数 = (总奇数 - 1 - 左右相邻奇数)
   • 若a[i]为偶数：有效对数 = (总偶数 - 1 - 左右相邻偶数)
3. 累加所有有效对数后除以2（去除重复计数）

def count_even_pairs(n, arr): odds = evens = 0 odd_pos = [] even_pos = [] for i in range(n): if arr[i] % 2 == 1: odds += 1 odd_pos.append(i) else: evens += 1 even_pos.append(i) total = 0 # 计算奇数对 for i in odd_pos: invalid = 0 if i > 0 and arr[i-1] % 2 == 1: invalid += 1 if i < n-1 and arr[i+1] % 2 == 1: invalid += 1 total += (odds - 1 - invalid) # 计算偶数对 for i in even_pos: invalid = 0 if i > 0 and arr[i-1] % 2 == 0: invalid += 1 if i < n-1 and arr[i+1] % 2 == 0: invalid += 1 total += (evens - 1 - invalid) return total // 2

时间复杂度：O(n)，仅需一次遍历统计和一次遍历计算

2.2 边界条件处理

常见陷阱及解决方案：

1. 全奇数/全偶数数组：需确保不重复计算自身
2. 相邻元素相等：需要严格判断索引差绝对值>1
3. 空数组或单元素数组：直接返回0

3. 环形黄蓝灯最大积分问题

题目描述： N盏首尾相连的灯，每盏灯有两个分数[x,y]：

• 点亮黄灯得x分
• 点亮蓝灯得y分
• 不点亮得0分 约束：相邻灯颜色不能相同 求可获得的最大积分

示例： 输入：

5 [1,4] [2,5] [4,100] [50,30] [1000,1]

输出：1106（选择：黄(1)、蓝(5)、黄(100)、蓝(30)、黄(1000)）

3.1 环形动态规划解法

解题思路：

• 环形问题转化为线性：枚举第一盏灯的状态，分别计算
• 状态定义：dp[i][c]表示前i盏灯，第i盏灯为c颜色时的最大得分（c∈{黄,蓝,不选}）
• 转移方程：
  • 若当前选黄：前驱只能是蓝或不选
  • 若当前选蓝：前驱只能是黄或不选
  • 若不选：前驱可以是任意状态

def max_light_score(n, lights): if n == 0: return 0 # 三种状态：0=不选，1=黄，2=蓝 dp = [[0]*3 for _ in range(n)] # 情况1：第一盏选黄 dp[0][0], dp[0][1], dp[0][2] = 0, lights[0][0], 0 for i in range(1, n): dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + lights[i][0] dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + lights[i][1] case1 = max(dp[-1][0], dp[-1][2]) # 最后不能选黄 # 情况2：第一盏选蓝 dp[0][0], dp[0][1], dp[0][2] = 0, 0, lights[0][1] for i in range(1, n): dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + lights[i][0] dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + lights[i][1] case2 = max(dp[-1][0], dp[-1][1]) # 最后不能选蓝 # 情况3：第一盏不选 dp[0][0], dp[0][1], dp[0][2] = 0, 0, 0 for i in range(1, n): dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + lights[i][0] dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + lights[i][1] case3 = max(dp[-1][0], dp[-1][1], dp[-1][2]) return max(case1, case2, case3)

复杂度分析：

• 时间复杂度：O(n)*3=O(n)
• 空间复杂度：可优化到O(1)只保存前一个状态

3.2 贪心算法的局限性

虽然该问题看似适合贪心（每次选择较大值），但实际会失败于如下case：

3 [10,1] [1,10] [10,1]

贪心选择：黄(10)→蓝(10)→?（冲突） 最优解：蓝(1)→黄(10)→蓝(1)=12分

4. 高频考点与变种题型

4.1 不相邻问题变种

4.2 环形DP问题模板

def circular_dp(n, arr): if n == 0: return 0 if n == 1: return arr[0] # 情况1：不选第一个元素 dp = [0]*n dp[1] = arr[1] for i in range(2, n): dp[i] = max(dp[i-1], dp[i-2] + arr[i]) case1 = dp[-1] # 情况2：选第一个元素 dp = [0]*n dp[0], dp[1] = arr[0], arr[0] for i in range(2, n-1): dp[i] = max(dp[i-1], dp[i-2] + arr[i]) case2 = dp[-2] return max(case1, case2)

5. 笔试实战技巧

时间管理策略：

1. 快速审题（5分钟）：标记题目中的约束条件（如"不相邻"、"环形"等关键词）
2. 难度评估（3分钟）：优先解决有思路的题目，放弃需要长时间推导的难题
3. 编码调试（每题15-20分钟）：先写核心算法，再处理边界case
4. 检查验证（5分钟）：用示例数据手工验证代码逻辑

常见失分点规避：

• 变量未初始化（特别是DP问题的初始状态）
• 数组越界（环形问题的取模处理）
• 整数溢出（特别是组合数计算时）
• 特殊输入未处理（空数组、全相同元素等）

注意：阿里笔试常设置"部分分"测试用例，即使无法AC也应确保基础case的正确性，这对最终排名至关重要。