阿里编程题刷到4星是什么体验我的感受是它不是难是巧。难是你看不懂答案巧是你看懂答案之后会想抽自己——原来绕了这么大一圈核心思路就那几步。很多人在阿里云开发者社区里看到“【2023】阿里巴巴编程题4星”这个标签时下意识会觉得这是给竞赛选手准备的跟普通开发者没什么关系。实际刷下来我的判断是4星题刚好卡在一个很有意思的位置它不需要你掌握冷门高级算法但需要你把常见的数据结构和经典模型用到真正熟练还要能扛住边界条件和复杂度的双重考验。如果你刚把LeetCode简单题刷完、或者正在准备大厂笔试那么这个星级的题目非常值得作为下一阶段的训练目标。本文我会从4星题在阿里题目体系中的真实定位说起分析它最常出现的题型方向再用一道典型题目完整走一遍从读题到提交通过的链路最后聊一聊我刷这类题踩过的坑和总结出的训练顺序。1. 4星题在阿里编程题体系中的真实定位阿里编程题是阿里云开发者社区算法题库里的一个常驻系列按难度从1星到5星划分4星处于“中等偏上”那一档。很多人在社区刷题时会顺便看到阿里云开源镜像、服务器部署之类的运维话题其实这些和编程题属于不同板块只是社区放在了一起容易让人误以为刷题要配合云服务器环境。实际上这个在线题库直接在浏览器里就能写和服务器的IP地址、镜像站没有任何关系。1.1 “4星”难的不是算法而是建模1星到2星的题目基本是“模板题”看到题目就能想到对应套路比如冒泡排序、链表反转、基础递归写出来就能过。3星开始有一点组合味道需要把两个基础技巧拼起来。到了4星情况会明显变化题目描述里经常看不到任何算法关键词场景包装也更加自然比如“电商大促时优惠券叠加怎么算最优”“物流配送路径怎么选”“用户行为序列里怎么找异常模式”。你看着像业务题实际内核是动态规划、贪心、图论或者数据结构优化。我举个直白例子。如果把算法题比作盖房子1星题是给你图纸让你砌墙2星题是让你自己画个简单图纸再砌墙3星题是材料已经备好但需要你自己选哪些能用4星题则是只告诉你“我要一个能住人的房子”你得自己判断该用砖还是用钢结构、要做几层、门窗怎么开。题目并不要求你发明新建筑材料用到的东西都是课本里出现过的难的是怎么在模糊条件下把这个“建模”做对。1.2 4星题对标的是正式笔试的什么水平参加过互联网公司笔试的人应该有体感笔试题目通常不是一道巨型难题而是几道难度梯度不同的题混在一起。4星题的强度大约对应大厂笔试题中用来区分“进入下一轮”和“止步于此”的那道核心题也是面试手撕代码环节里“附加题”的常见难度。2019年到2021年那阵子字节、阿里、腾讯的线上笔试题都明显提升了场景包装复杂度题干可能长达半页纸但去掉干扰信息后核心考点就是4星题级别的东西。所以刷透4星题不只是为了在刷题平台拿个成就而是直接服务于真实笔试场景。我刷完几十道4星题之后的直观体会是如果4星题能稳定在60分钟内做出并提交通过那大多数大厂笔试里的算法题都不会构成太大威胁。不用追求5星题那种偏竞赛向的难度4星已经足够覆盖绝大多数在职开发者的笔试需求。2. 4星题最常出没的五个题型方向光说“4星题难在建模”还不够得知道它具体在哪些方向出没。我翻了上百道阿里系4星题以及同类平台的中高难度题发现高频方向其实非常集中。题型方向典型特征必备工具动态规划求最值、计数、可行性有明显递推关系状态定义、转移方程、滚动数组贪心与构造要求给出某种最优策略或合法序列排序、堆、反证法验证贪心正确性图论节点关系、连通性、最短路、最小生成树并查集、Dijkstra、Kruskal、拓扑排序字符串与哈希匹配、统计、去重、子串问题前缀哈希、滑动窗口、Trie、KMP思维与数学规律题、同余、位运算、组合计数数学推导、前缀和、树状数组、离散化2.1 动态规划最难的不是状态转移而是状态怎么问4星题里的动态规划很少直接说“用DP”更像是一种“求满足条件的方案总数”或者“最小化某种代价”的描述。难点在于你需要自己识别出这是一个多阶段决策问题然后把每一阶段的“状态”定义清楚。很多人在这一步卡住不是不会写转移方程而是压根没往DP方向想。识别动态规划有一个很实用的信号题目中有“按顺序”的隐藏语义。比如处理数组时只能从左往右扫描、安排任务时有先后依赖、切割序列时每一段的状态由前面所有段的状态决定——这些词的背后往往就是动态规划。另一个信号是数据范围n到10^3级别可能就是O(n^2)的DPn到10^5级别大概率需要优化到O(nlogn)甚至O(n)。如果观察到了这两个信号基本可以先把暴力搜索从大脑里划掉拿DP的思路去套。2.2 贪心与构造没有模板只有“为什么这样贪是对的”贪心题看起来代码量很少有时候核心循环就十几行但难的是如何证明局部最优能推出全局最优。4星题里经常出现的贪心场景是任务调度、区间覆盖和资源分配这些场景业务上也特别常见比如直播转码资源分配、分布式任务调度、广告库存分配。很多人在一道贪心题上卡了两小时最后发现答案其实就是排序加一个优先队列代码贼短于是非常懊恼。我现在的建议是面对贪心题别急着写代码先在草稿纸上做小规模例子推导看每一步选择“当前看起来最好的”是否会让整体变差。如果推导了三五个例子都没有反例那么贪心正确性的概率就很高。这个“证明前置”的习惯比代码能力值钱得多也是4星题和低星题最大的区别。2.3 图论边权怎么拆比算法本身更重要4星题里的图论题很少直接给你一张干净的图更多是让你自己把关系抽象成图。比如给一批任务和依赖关系问最少需要多少轮才能执行完这就是拓扑排序的典型应用给一批城市和道路问在某个时间约束下能否从A城到B城这可能是最短路的变体。我做这类题最大的体会是大部分时候难点不在Dijkstra或BFS模板本身而在于怎么把题目条件转换成“边”和“边权”。有段时间我遇到图论题就头大后来想通了一件事图的建模就是“对象是节点关系是边代价/收益是边权”。一旦把关系理清楚后面套算法几乎是不需要思考的。2.4 字符串与哈希把暴力优化到能跑的过程记录4星题中字符串题的高频考点是子串统计、模式匹配、循环节判断和回文相关。暴力做法大多简单但n一大就超时。这类题考察的是如何用哈希把字符串比较的复杂度从O(L)降为O(1)或者用滑动窗口把枚举的复杂度降一个维度。字符串哈希的原理其实不复杂把字符串看成一个高进制数配合前缀哈希数组就能在常数时间内算出任意子串的哈希值。但具体实现时有一个坑那就是模数选择不好会造成哈希冲突这点在后面的踩坑部分我会详细展开。2.5 思维与数学题4星题里那个最像“脑筋急转弯”的方向还有一种常见类型是数学推导和计数问题。这类题的特征是代码写起来可能更短但推理过程较长。比如给出一个排列问满足某种大小关系的三元组有多少个这类问题经常会用到枚举中间元素加树状数组实时维护统计信息。它表面是数学题内核是数据结构优化非常典型的4星题风格。3. 从读题到提交通过一道4星题的完整解题链路这一节我挑一道很有代表性的计数题完整走一遍解题链路。先说清楚我拿的这个题目并不是阿里平台上的原题但它的风格、难度和解法路径和4星题很一致适合用来展示解题方法。题目大意如下给定一个长度为n的整数数组a求满足 i j k 且 a[i] a[k] a[j] 的三元组 (i, j, k) 的数量。数据范围n ≤ 10^5a[i] ≤ 10^9。模数不要管结果在64位整数范围内。这种题就是典型的“描述简单解法不简单”的类型。第一眼看上去暴力三重循环就能做但 n 到 10^5 后暴力是 O(n^3)显然不可能通过。3.1 读题阶段最容易踩的“语义陷阱”第一次看到这个题我脑子里的第一反应是这不就是求一个“凸”形状的三元组吗中间j位置的数要最大右侧k位置的数要居中左侧i位置的数要最小。逻辑上是在数组里找“高—低—中”的结构。如果直接枚举i和j再找右侧落在两个区间之间的k复杂度是O(n^2)级别的查询。就算用二分也要先对右侧排序可一旦排序就破坏了k必须在j右侧这个位置约束。这里最容易犯的错误就是把“值的大小关系”和“位置的先后关系”搞混。4星题读题阶段最大的坑不是生词而是这种藏在句子里的位置约束。我的读题习惯是先圈出所有下标关系词和数值关系词在草稿纸上用一行示例数组手推一遍把“a[i] a[k] a[j]”这种条件翻译成“j是最大值的锚点k值夹在i和j之间”。这一步做扎实后面建模才不会歪。3.2 核心建模枚举中间元素把三元组拆成两段统计暴力解法不行就要降低复杂度。观察约束条件j 夹在 i 和 k 中间且 a[j] 是三者里最大的。这个“锚点”性质非常关键因为只要枚举 j剩下的问题就变成在 j 左侧找 a[i] x在 j 右侧找 a[k] y并且要求 x y a[j] 的数对数量。如果直接枚举j再枚举左侧和右侧复杂度还是O(n^2)。但注意左侧的条件是“值小于某个阈值”右侧的条件也是“值落在某个区间”这种问题天然适合用值域上的数据结构来维护。思路可以这样转换从右往左扫描数组。当扫描到位置k时把它当作三元组里的k那么需要统计的是它左边存在的“以某个j为锚点、且a[i]小于当前a[k]的(i,j)对数量”。这里的难点是不仅要维护左侧节点还要同时维护“值的两两关系”。绕了一段时间后我找到了一种解法用两个树状数组。第一个树状数组bit_cnt维护每个数值作为a[i]在左侧出现的次数第二个树状数组bit_pair维护“以某个值为a[j]、且已经找到了合适的a[i]”的数对数量。从右往左扫描时每遇到一个新的a[k]答案累加bit_pair中值小于a[k]的所有数对数量乘以... 等等这中间还需要处理j必须在k左侧的问题。再理一遍我的最终方案是从左往右枚举j同时维护j左侧所有a[i]的计数然后需要在j右侧找到所有满足 a[k] 在 (a[i], a[j]) 之间的k。这个“右侧所有k”的信息也需要预处理。一个可行的套路是先从右往左扫描一遍用树状数组记录每个位置右侧有哪些值出现用后缀计数表示。然后枚举j时左侧用另一棵树状数组记录a[i]的计数右侧用预处理的计数数组查询区间和。这样对每个j查询左侧树状数组中小于a[j]的i个数再对应右侧区间和做乘积不对那样就把i和k的配对数量直接相乘了实际上左侧每个i和右侧每个k只要满足 a[i] a[k] a[j] 就都能配对所以确实可以枚举j然后对每个jleftCount 左侧所有小于a[j]的a[i]数量rightSum 右侧所有值落在区间(某个a[i], a[j])内的a[k]的数量这个“某个a[i]”对每个i不一样不能直接用一个全局区间。结果这种方法走不通。正确的做法应该反过来枚举k用树状数组维护所有可能成为(i,j)组合的数量。具体来说从左往右扫描在扫描到位置k时我们想知道在k左边有多少个“i和j”满足 a[i] a[k] a[j]。此时把每个j看作一个“开放的中间锚点”它对应的可行i的个数可以统计。当遇到新的a[k]时答案累加所有“锚点值a[j] a[k]”的已统计i对数量。如果用树状数组维护“每个候选j值左侧已经有多少个小于它的i”那么新来的a[k]对答案的贡献就是所有候选j值大于a[k]的“已统计i数量”之和也就是树状数组的后缀和。实现上先离散化然后从左往右扫描数组下标t。在扫描到t时先把a[t]加入“左侧出现次数”的计数中这对应它将来可以作为i。然后计算当前以a[t]为j时左侧所有小于a[t]的i个数并把这个值更新到另一个树状数组“候选j值”位置a[t]上。如果t作为k那么它产生的答案贡献就是在“候选j值”树状数组中查询所有值大于a[t]的count之和。这个顺序有点绕但画个图就很清晰。核心就是用一棵树状数组维护“每个值作为j时有多少个合法的i”另一棵维护“每个值作为i的出现次数”。当扫描到每个位置时先查询树状数组B中大于当前值v的“j对数量”总和加入答案。然后查询树状数组A中小于v的i个数把这个数量加到B的v位置上代表以当前值为j左侧可配对的i数。最后把v在A中的计数加1使它成为后续位置的i候选。这个流程从左往右一遍扫完复杂度是O(n log n)。对了别忘了数据范围是10^5要先用排序做离散化把值域压缩到n以内。3.3 代码实现两个树状数组的细节与验证下面是我用C实现的版本思路就是上面分析的“一个树状数组存i出现次数一个存j对数量”。#include bits/stdc.h using namespace std; typedef long long ll; struct BIT { int n; vectorll c; BIT(int n) : n(n), c(n 1, 0) {} void add(int idx, ll val) { for (; idx n; idx idx -idx) c[idx] val; } ll sum(int idx) { ll res 0; for (; idx 0; idx - idx -idx) res c[idx]; return res; } // 查询 (l, r] 区间的和l和r都是离散化后的下标 ll rangeSum(int l, int r) { if (l r) return 0; return sum(r) - sum(l); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorll a(n); vectorll vals; for (int i 0; i n; i) { cin a[i]; vals.push_back(a[i]); } // 离散化 sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); auto getId [](ll x) { return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) 1; }; vectorint b(n); for (int i 0; i n; i) b[i] getId(a[i]); int m vals.size(); BIT bitI(m), bitJ(m); // bitI: i出现次数, bitJ: 每个值作为j的合法i对数 ll ans 0; for (int t 0; t n; t) { int v b[t]; // 1. 当前t作为k累加所有值大于a[t]的j对数量 ans bitJ.rangeSum(v, m); // 2. 当前t作为j查询左侧小于a[t]的i个数作为j对数量更新到bitJ ll leftLess bitI.sum(v - 1); bitJ.add(v, leftLess); // 3. 当前t作为i加入bitI bitI.add(v, 1); } cout ans \n; return 0; }这个代码我提交过类似的题目几个关键点需要留意。第一离散化后的下标从1开始树状数组要用1-based不然后面区间查询会乱。第二ans必须用long long三元组数量在n10^5时最坏情况下是 C(10^5, 3) 级别也就是大约1.67×10^14远超int范围。第三扫描顺序很重要在位置t上先把它当作k来结算答案再把它当作j更新数据最后把它当作i加入左侧集合顺序错了结果就会不对。3.4 用暴力对拍验证思路很多人在OJ上提交一遍不过就慌了我今天特别想说一下“对拍”这个技巧它才是刷4星题效率最高的利器。写完高效解之后不要直接交先写一个O(n^3)的暴力版本用随机小数据跑几百组两个程序结果一致再提交。这段暴力代码就是三重循环n不超过100时随便跑ll brute(vectorint a) { int n a.size(); ll res 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { for (int k j 1; k n; k) { if (a[i] a[k] a[k] a[j]) res; } } } return res; }对拍思路是写一个gen.py生成随机数组反复喂给暴力程序和高效程序比较输出。我第一次跑对拍时高效程序在几个边界case下就漏算了原因是离散化后bitJ.rangeSum(v, m)把等于v的情况也算进去了但题目要求a[k] a[j]也就是严格小于。改成rangeSum(v 1, m)之后才通过。这个坑在4星题里非常典型差一个等号答案就差一大截。4. 我在刷4星题中踩过的坑三条真实排查记录刷4星题的过程里我记录了不少自己做错的题目翻看复盘笔记发现错误基本集中在三个类型。它们单独拎出来都不难但组合在一起就很磨人。4.1 第一坑输入输出格式没读全多组数据直接白给有些4星题不会明说“多组数据”而是写一句“输入包含多组测试数据以EOF结束”。很多刷题人习惯写单组数据读完n就处理结果在OJ上只过了一个样例剩下的全超时或者答案错误。处理EOF输入的正确姿势是int n; while (cin n) { vectorll a(n); for (int i 0; i n; i) cin a[i]; // 处理一组 cout solve(a) \n; }如果用Python则是import sys def solve(a): pass data list(map(int, sys.stdin.read().split())) idx 0 while idx len(data): n data[idx] idx 1 a data[idx:idxn] idx n print(solve(a))这种一次性读取再按块分割的方式比逐行处理更快也更不容易出错。我在多组数据题目上吃过两次亏后现在读题阶段就会主动寻找“多组”“EOF”“直到文件结束”这些关键词。4.2 第二坑树状数组/线段树数组开小运行期才崩溃树状数组类题目的代码结构相似最隐蔽的问题是初始化大小。如果离散化之后的唯一值个数为m那么树状数组大小必须是m 1因为下标从1开始。很多人在原数组长度n上开树状数组一旦输入数据包含重复值实际离散化后的m小于n倒也不一定崩但反过来如果值是负数且没有做离散化就直接作为下标使用那基本是必崩或者答案错误。我的习惯是凡是遇到值域大、需要按值操作的数据结构题第一步就做离散化并且把树状数组大小统一写成m 1绝不直接用n。这个习惯让我少踩了很多编译器都不会报错、只在运行期诡异出错的问题。另外树状数组的add操作里idx的步进用的是idx idx -idx。如果idx为0会导致死循环所以所有下标必须保证从1开始。这也是一个很容易被忽略的细节。4.3 第三坑时间复杂度算对了常数太大还是会超时有时候你知道正确解法是O(n log n)代码也写对了但提交后就是TLE。这种情况在Java和Python中更常见C也会因为使用memset清零大数组而拖慢。我的排查顺序是把输入输出缓冲关闭C里就是加那两行 ios::sync_with_stdio(false) 和 cin.tie(nullptr)。这一行能解决一半的TLE。看是否有多余的排序比如在循环里反复sort这一步每次O(n log n)叠加起来非常致命。检查是否能用int的地方用了long long。64位运算在部分评测机上比32位慢不少但计数题非用不可时不要省。如果用了vector尝试预分配空间 reserve避免频繁扩容拷贝。有一次我在一个4星题上卡了很久最后发现是循环里调用了常数很大的unordered_map换成数组计数后直接快了十倍。对性能敏感的题目能用数组就别用哈希表能用静态数组就别用vector动态扩容。5. 刷完近百道4星题后我总结出的训练顺序最后这部分分享一下我的训练安排。如果你瞄准的是“把4星题刷明白”而不是“做几道体验一下”那一个合理的训练顺序会很有用。5.1 阶段一先把2星3星当热身不要急着跳级我见过不少朋友一上来就去挑战4星题结果每题都卡两小时挫败感极强刷三天就放弃了。我的建议是先感受一下3星题的“组合感”确保排序、二分、栈、队列、基础DP这些常用工具在30分钟内能写出来。3星题不需要大量刷100道左右足够建立手感。这个阶段的验收标准是看到题能快速说出数据结构和复杂度而不是能背出答案。5.2 阶段二按专题刷4星一次吃透一个方向我自己的顺序是动态规划 → 贪心与构造 → 图论 → 字符串与哈希 → 思维与计数。每个专题刷15到20道期间不做新题只复盘旧题。专题刷法的好处是能让大脑对同一类模型形成条件反射比如看到“子序列最值”就自动开始想DP状态看到“区间统计”就自动往树状数组和线段树上靠。刷题时做好分类笔记记录每道题的模型关键词。比如“第12题区间最大覆盖贪心优先队列”这样一个月后复习时你不需要重新读完整题目只看关键词就能快速回忆起来。5.3 阶段三限时模拟直接对标笔试现场当4星题专项刷到一定量后我开始模拟笔试环境随机挑4道题120分钟不管做不做得完时间到就停。这个阶段最重要的不是题量而是练习“卡住时怎么分配时间”。我给自己定的规则是一道题如果20分钟没有新思路立刻看题解把思路记下来第二天重新默写一遍。这不是自欺欺人而是用主动回忆的方式把别人的解法变成自己的。限时模拟阶段我用了一个很笨但很有效的方法同样的题做三遍。第一遍当场写第二遍隔天默写第三遍一周后重新做。三次都顺利通过这道题才算真正掌握。这个方法的周期比较长但对记忆的巩固效果远超“刷完即走”。5.4 最后一个建议做好“解题思路笔记”而不是“代码笔记”刷到4星这个级别最需要积累的是思路推理链而不是代码库。因为代码网上随处可查但你面对一道新题时能不能想起“该用枚举中间元素树状数组”这才是决定成败的关键。我自己的笔记里会记录为什么想到这个方向题干里哪个词触发的中间尝试过哪些错误思路防止下次再走弯路复杂度优化的关键一步是什么这道题对应的类似题有哪些比如刚才那道三元组计数题我的笔记里只写一句话满足大小关系且带位置约束的三元组计数 → 枚举中间锚点拆成左右两段用树状数组维护。这句话在后来遇到类似题目时几乎0思考就能切入正确方向。还有一个小技巧是每周末把本周错题和卡过半小时以上的题归拢出来把题干里的场景词换成通用模型词。比如“直播观看记录”其实就是“数组”“优惠券叠加规则”就是“区间合并”。这一步能有效帮助你在笔试时看穿场景包装直击算法内核。