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

淘天/阿里国际2025实习笔试算法题深度解析从“不相邻偶数对”到“环形黄蓝灯”1. 笔试概况与备战策略淘天集团与阿里国际的实习笔试向来以高难度著称2025届的笔试结构延续了往年的风格选择题27分/9题、不定项选择题18分/6题和算法题55分/3题。根据考生反馈算法题往往决定成败而选择题则覆盖操作系统、数据库、设计模式等计算机基础。高效备战建议时间分配建议按5:3:2分配准备时间50%精力专攻算法30%巩固计算机基础20%模拟实战核心算法重点突破动态规划背包问题、状态机模型图论DFS/BFS、拓扑排序、最短路径贪心算法区间调度、环形处理数学思维组合计数、奇偶分析提示阿里系笔试常考察变形题即在经典算法题基础上增加特殊约束条件如环形结构、不相邻限制等需重点练习这类题型。2. 不相邻偶数对问题解析题目描述 给定长度为n的数组a要求统计有多少对(i,j)满足i ≠ j 且 |i-j| 1不相邻a[i] a[j] 为偶数示例 输入5 [1, 2, 3, 4, 6]输出3有效组合13, 24, 262.1 数学建模与优化思路关键观察偶数 奇奇 或 偶偶总对数 C(odd,2) C(even,2) - 相邻奇数对 - 相邻偶数对优化解法步骤统计奇数总数odds和偶数总数evens遍历数组对每个元素a[i]若a[i]为奇数有效对数 (总奇数 - 1 - 左右相邻奇数)若a[i]为偶数有效对数 (总偶数 - 1 - 左右相邻偶数)累加所有有效对数后除以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[i1] % 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[i1] % 2 0: invalid 1 total (evens - 1 - invalid) return total // 2时间复杂度O(n)仅需一次遍历统计和一次遍历计算2.2 边界条件处理常见陷阱及解决方案全奇数/全偶数数组需确保不重复计算自身相邻元素相等需要严格判断索引差绝对值1空数组或单元素数组直接返回03. 环形黄蓝灯最大积分问题题目描述 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)*3O(n)空间复杂度可优化到O(1)只保存前一个状态3.2 贪心算法的局限性虽然该问题看似适合贪心每次选择较大值但实际会失败于如下case3 [10,1] [1,10] [10,1]贪心选择黄(10)→蓝(10)→?冲突 最优解蓝(1)→黄(10)→蓝(1)12分4. 高频考点与变种题型4.1 不相邻问题变种题型约束条件解法思路最大不相邻子序列和不能选相邻元素动态规划dp[i]max(dp[i-1], dp[i-2]arr[i])不相邻染色问题相邻颜色不同状态机DP记录最后颜色环形不相邻问题首尾也视为相邻拆分为两种情况选首不选尾/选尾不选首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. 笔试实战技巧时间管理策略快速审题5分钟标记题目中的约束条件如不相邻、环形等关键词难度评估3分钟优先解决有思路的题目放弃需要长时间推导的难题编码调试每题15-20分钟先写核心算法再处理边界case检查验证5分钟用示例数据手工验证代码逻辑常见失分点规避变量未初始化特别是DP问题的初始状态数组越界环形问题的取模处理整数溢出特别是组合数计算时特殊输入未处理空数组、全相同元素等注意阿里笔试常设置部分分测试用例即使无法AC也应确保基础case的正确性这对最终排名至关重要。