写在前面欢迎大家关注Rocky的知乎Rocky Ding《三年面试五年模拟》AIGC/LLM/AI Agent算法工程师/开发工程师求职面试秘籍独家资源【三年面试五年模拟】WeThinkIn/AIGC-Interview-Book欢迎大家StarRocky最新撰写的10万字AI AgentAI智能体深入浅出全维度解析文章深入浅出完整解析AI AgentAI智能体的核心基础知识AIGC/LLM/AI Agent算法岗/开发岗求职面试内推学习社群涵盖AIGC、LLM大模型、AI Agent、传统深度学习、自动驾驶、机器学习、计算机视觉、自然语言处理、强化学习、大数据挖掘、具身智能、元宇宙、AGI等AI行业最新面试干货经验与核心知识欢迎大家加入https://t.zsxq.com/33pJ0大家好我是Rocky。编程题1. 编程题求abc方案数题意给定数字n要求统计有多少组(a, b, c)满足1 ≤ a ≤ b ≤ c ≤ n 1 \le a \le b \le c \le n1≤a≤b≤c≤n并且a ⊕ b ⊕ c 0 , a b c a \oplus b \oplus c 0,\qquad abca⊕b⊕c0,abc其中^表示按位异或。题解异或满足结合律并且x ⊕ x 0 x \oplus x0x⊕x0、x ⊕ 0 x x \oplus 0xx⊕0x。由a ⊕ b ⊕ c 0 a \oplus b \oplus c0a⊕b⊕c0可得c a ⊕ b ca \oplus bca⊕b因此不需要枚举三元组只需枚举a和b计算唯一可能的c然后检查大小关系和abc。这已经把朴素的O(n^3)降为O(n^2)。defcount_abc(n:int)-int:ans0forainrange(1,n1):forbinrange(a,n1):ca^bifbcnandabc:ans1returnans这里必须保留b c检查因为ca^b并不保证三元组的非降序关系。abc也不能由异或条件推出必须单独判断。正确性检查对任意合法三元组前两个数(a,b)一定会被枚举异或等式又唯一确定ca^b所以不会漏解也不会因为同一个(a,b)产生多个c。反过来代码只统计同时满足b c n和abc的候选因此每个计数项都满足题面约束。时间复杂度为O(n^2)额外空间复杂度为O(1)。n1或没有满足条件的组合时答案自然为0Python 整数不会溢出但其他语言需要使用足够宽的计数类型。如果题目给出的n上限是约 2500枚举a,b通常已经足够是否需要更复杂的位运算优化必须由真实数据范围和时间限制决定不能仅凭“异或题”就过度优化。2. 编程题栈/队列判断题意给定两个相同长度的字符串S和T。按照S的顺序依次输入一个数据结构判断该数据结构的输出顺序可以是否为T。输出结果可能是栈、队列、两者都可能或者两者都不可能。题解队列是先进先出。所有字符都按照S的顺序进入队列因此它唯一可能的输出就是S本身如果S T队列一定可行如果S ! T队列一定不可行。栈是后进先出但每次入栈后可以选择暂不弹出也可以在合适时机弹出。用一个栈模拟即可遍历S每读入一个字符就压栈只要栈顶等于T[j]就不断弹栈并推进j。最终j len(T)说明存在一种弹栈顺序得到T。defjudge_structure(s:str,t:str)-str:iflen(s)!len(t):returnneitherqueue_okst stack[]j0forchins:stack.append(ch)whilestackandjlen(t)andstack[-1]t[j]:stack.pop()j1stack_okjlen(t)ifqueue_okandstack_ok:returnbothifstack_ok:returnstackifqueue_ok:returnqueuereturnneither例如Sabc、Tacb时队列不可行但可以先压入a并弹出再压入b,c最后按c,b弹出所以结果是stack。如果ST栈可以每次入栈后立即弹出因而结果应为both不能简单地把ST判成queue。为什么贪心弹栈是安全的当栈顶已经等于T[j]时若不弹出就无法让T[j]由栈中更底部的元素先输出弹出它不会改变后续入栈顺序且只会推进一个已经确定的目标字符。因此连续弹出所有匹配的栈顶字符不会丢失可行方案。若遍历结束后j len(T)说明剩余元素的栈顶顺序无法匹配目标栈一定不可行。空字符串若题面允许对栈和队列都可行长度不同则两者都不可行。每个字符最多入栈和出栈一次时间复杂度为O(n)额外空间复杂度为O(n)。实现时要特别注意重复字符不能用字符到位置的单值映射代替栈模拟。3. 编程题任务最大收益题意给定n个任务每个任务有开始和结束时间[s_i,e_i)以及价值v_i。选择一组时间上互不冲突的任务使价值总和最大。半开区间意味着任务i结束于e_i后可以接着执行开始于e_i的任务。题解这是带权区间调度问题。按结束时间升序排序令dp[i]表示排序后前i个任务能够获得的最大价值。对于第i个任务有两种选择不选它收益为dp[i-1]选它找到最后一个满足e_j s_i的任务j收益为dp[j] v_i。于是d p [ i ] max ( d p [ i − 1 ] , d p [ p ( i ) ] v i ) dp[i]\max\bigl(dp[i-1],\ dp[p(i)]v_i\bigr)dp[i]max(dp[i−1],dp[p(i)]vi)其中p(i)是按结束时间排序后、结束时间不晚于s_i的最后一个任务下标。由于结束时间有序p(i)可以二分查找。frombisectimportbisect_rightfromtypingimportList,Tupledefmax_task_value(tasks:List[Tuple[int,int,int]])-int:# 每个任务是 (start, end, value)题目保证 start end。taskssorted(tasks,keylambdaitem:item[1])ends[endfor_,end,_intasks]dp[0]*(len(tasks)1)fori,(start,_,value)inenumerate(tasks,start1):# 在前 i-1 个任务中找最后一个 end start 的任务。compatiblebisect_right(ends,start,0,i-1)takedp[compatible]value skipdp[i-1]dp[i]max(skip,take)returndp[-1]为什么可以只看最后一个兼容任务因为前缀dp[compatible]已经代表所有结束时间不晚于start_i的任务组合的最优值选择其中最后一个下标不会丢失更早任务的最优解。排序耗时O(n log n)每个任务进行一次二分查找耗时O(log n)总时间复杂度为O(n log n)额外空间复杂度为O(n)。如果使用按开始时间排序配合小根堆也可以做到O(n log n)但必须明确堆中维护的是已经完成任务的最优价值仅仅“把任务放进堆”并不能自动保证动态规划转移正确。正确性与边界排序后考虑前i个任务最优解要么不含第i个任务对应dp[i-1]要么包含它后一种情况下其余任务必须来自结束时间不晚于s_i的前缀最优收益正是dp[compatible]。两种情况覆盖且互斥归纳即可得到转移正确。半开区间的兼容条件是end start所以必须使用bisect_right。空任务列表返回0价值为负数时dp[i-1]会自然选择“不接这个任务”除非题目另有“必须选择至少一个任务”的约束。4. 编程题价值最大路径题意给定n个点和m条单向边。每条边按输入顺序给出(a_i,b_i,w_i)表示从a_i到b_i、权重为w_i的边。需要选择一条边序列使得后一条边的起点等于前一条边的终点后一条边的权重严格大于前一条边的权重后一条边必须在输入中晚于前一条边出现但不要求边在输入数组中连续。输出满足条件的最长路径边数。这里的“价值最大”容易造成误读题目真正优化的是路径边数w_i只用于约束严格递增不是让权重总和最大。题解按输入顺序处理边。定义best[v][w]表示已经处理的边中以点v为终点、最后一条边权为w的最长合法路径长度。处理当前边(a,b,w)时前一条边必须已经到达a且其权重严格小于w所以c u r 1 max u w b e s t [ a ] [ u ] cur1\max_{uw}best[a][u]cur1uwmaxbest[a][u]然后把这条边作为新路径的最后一条边更新best[b][w] max(best[b][w], cur)。查询必须先于更新因为当前边不能接在自己后面而且使用严格小于w的前缀查询等权边不能连接。每个点上的权重值域可以离散化并为每个点维护一棵 Fenwick Tree树状数组树状数组支持查询权重排名小于当前权重的最大路径长度更新当前终点和当前权重对应的最大值。frombisectimportbisect_leftfromcollectionsimportdefaultdictfromtypingimportList,TupleclassFenwickMax:def__init__(self,size:int)-None:self.tree[0]*(size1)defupdate(self,index:int,value:int)-None:whileindexlen(self.tree):self.tree[index]max(self.tree[index],value)indexindex-indexdefquery(self,index:int)-int:result0whileindex0:resultmax(result,self.tree[index])index-index-indexreturnresultdeflongest_increasing_path(n:int,edges:List[Tuple[int,int,int]])-int:# 先按终点收集该点可能出现的所有权重建立离散坐标。weightsdefaultdict(list)for_,end,weightinedges:weights[end].append(weight)trees{}forvertex,valuesinweights.items():orderedsorted(set(values))trees[vertex](ordered,FenwickMax(len(ordered)))answer0forstart,end,weightinedges:ordered,treetrees[start]ifstartintreeselse([],None)# 当前边的前驱必须权重严格小于 weight。rankbisect_left(ordered,weight)previoustree.query(rank)iftreeisnotNoneelse0currentprevious1target_ordered,target_treetrees[end]target_rankbisect_left(target_ordered,weight)1target_tree.update(target_rank,current)answermax(answer,current)returnanswer上面代码中树建立在“前一条边的终点”上处理当前边时从trees[start]查询再把结果更新到trees[end]。这正是端点衔接条件的实现。正确性检查按输入顺序处理到第i条边时树中只保存第i-1条及之前的状态因而自动满足“后一条边在输入中更晚”。查询start的权重前缀只取 weight恰好对应端点连续且权重严格递增的所有合法前驱若没有前驱前缀最大值为0当前边单独构成长度1的路径。再将current写入end的当前权重位置就维护了所有以该状态结尾的最优值。对输入顺序归纳可知最终answer是所有合法路径的最大边数。参数n只描述点编号范围算法实际只需读取边列表空边列表会返回0。权重可能相同或为负数离散化和bisect_left仍然成立关键是查询排名严格小于当前权重而更新时使用当前权重的排名。设某个点关联的不同权重总数为k_v则每次查询和更新为O(log k_v)总时间复杂度为O(m log m)离散化和树状数组占用O(m)空间。若所有权重已经是小范围整数也可以直接使用数组或线段树不能把复杂度写成O(m log n)除非题目明确说明权重值域或点数与权重离散规模存在相应约束。推荐阅读1. 深入浅出完整解析AI AgentAI智能体的核心基础知识2025年可以说是AI Agent全面落地应用的元年因此Rocky在持续撰写对AI Agent的全维度解析文章深入浅出完整解析AI AgentAI智能体的核心基础知识2. 深入浅出完整解析扩散模型DDPM、DDIM、Score-Based、SDE、LDM、Classifier/Classifier-Free Guidance、Rectified Flow核心基础知识Rocky对扩散模型的本质原理与和核心基础知识进行了全面系统的深入浅出分析讲解同时不断跟进补充扩散模型的最新技术发展希望能给大家带来帮助深入浅出完整解析扩散模型DDPM、DDIM、Score-Based、SDE、LDM、Classifier/Classifier-Free Guidance、Rectified Flow核心基础知识3. 入浅出完整解析FLUX.2、Seedream即梦、Z-image、GLM-Image核心基础知识Rocky对AIGC时代“中场时刻”之后的主流AIGC创作大模型的核心基础知识进行了全面系统的深入浅出分析讲解力求让大家通俗易懂理解AIGC时代的技术浪潮的本质价值入浅出完整解析FLUX.2、Seedream即梦、Z-image、GLM-Image核心基础知识4. 深入浅出完整解析FLUX.1 Kontext和FLUX.1 Krea核心基础知识Rocky对FLUX.1 Kontext和FLUX.1 Krea的核心基础知识作了全面系统的梳理与解析深入浅出完整解析FLUX.1 Kontext和FLUX.1 Krea核心基础知识5. 深入浅出完整解析DeepSeek系列核心基础知识Rocky对DeepSeek系列模型的核心基础知识作了全面系统的梳理与解析深入浅出完整解析DeepSeek系列核心基础知识6. 深入浅出完整解析Stable Diffusion 3SD 3和FLUX.1系列核心基础知识Rocky对Stable Diffusion 3和FLUX.1的核心基础知识作了全面系统的梳理与解析深入浅出完整解析Stable Diffusion 3SD 3和FLUX.1系列核心基础知识7. 深入浅出完整解析Stable Diffusion XLSDXL核心基础知识Rocky对Stable Diffusion XL的核心基础知识作了全面系统的梳理与解析深入浅出完整解析Stable Diffusion XLSDXL核心基础知识8. 深入浅出完整解析Stable DiffusionSD核心基础知识Rocky对Stable Diffusion 1.x-2.x系列模型的核心基础知识做了全面系统的梳理与解析深入浅出完整解析Stable DiffusionSD核心基础知识9. 深入浅出完整解析Stable Diffusion中U-Net的前世今生与核心知识Rocky对Stable Diffusion中最为关键的U-Net结构进行了深入浅出的全面解析包括其在传统深度学习中的价值和在AIGC中的价值深入浅出完整解析Stable Diffusion中U-Net的前世今生与核心知识10. 深入浅出完整解析LoRALow-Rank Adaptation模型核心基础知识对于AIGC时代中的“ResNet”——LoRA模型Rocky进行了深入浅出的全面讲解深入浅出完整解析LoRALow-Rank Adaptation模型核心基础知识11. 深入浅出完整解析ControlNet核心基础知识AIGC图像创作开源社区已经形成以Stable Difffusion/FLUX为核心ConrtolNet和LoRA作为首要AI辅助工具的变化万千的AIGC图像创作工作流。ControlNet正是让AI图像创作社区无比繁荣的关键一环它让AIGC图像创作过程更加的可控更有助于广泛地将AIGC算法解决方案应用到各行各业中深入浅出完整解析ControlNet核心基础知识12. 深入浅出完整解析Sora、Seedance、keling等AI视频大模型核心基础知识AI绘画和AI视频是两个互相促进、相互交融的领域2024年无疑是AI视频领域的爆发之年Rocky对AI视频领域核心的Sora、Seedance、Keling等大模型进行了全面系统的梳理与解析深入浅出完整解析Sora、Seedance、keling等AI视频大模型核心基础知识13. 深入浅出完整解析AIGC时代Transformer核心基础知识在AIGC时代中Transformer为AI行业带来了深刻的变革。Transformer架构正在一步一步重构所有的AI技术方向成为AI技术架构大一统与多模态整合的关键核心基座大有一统“AI江湖”之势。Rocky也对Transformer模型进行持续的深入浅出梳理与解析深入浅出完整解析AIGC时代Transformer核心基础知识14. 深入浅出完整解析ComfyUI、Diffusers、Stable Diffusion WebUI等主流AIGC创作框架核心基础知识AIGC创作框架正是AIGC算法工作流的运行载体目前主流的AIGC创作框架有ComfyUI、Diffusers、Stable Diffusion WebUI等。在传统深度学习时代PyTorch、TensorFlow以及Caffe是传统深度学习模型的基础运行框架到了AIGC时代Rocky相信ComfyUI就是AIGC时代的“PyTorch”、Stable Diffusion WebUI就是AIGC时代的“TensorFlow”、Diffusers就是AIGC时代的“Caffe”深入浅出完整解析ComfyUI、Diffusers、Stable Diffusion WebUI等主流AIGC创作框架核心基础知识15. 深入浅出完整解析ComfyUI、Diffusers、Stable Diffusion WebUI等主流AIGC创作框架核心基础知识在AIGC时代中如何快速转身入局AIGC产业如何成为AIGC/LLM/AI Agent算法/开发工程师如何在学校中系统性学习AIGC/LLM/AI Agent知识斩获心仪的AIGC/LLM/AI Agent算法/开发offerDon‘t worryRocky为大家总结整理了全面的AIGC/LLM/AI Agent算法/开发工程师成长秘籍为大家答疑解惑希望能给大家带来帮助手把手教你成为AIGC/LLM/AI Agent算法/开发工程师斩获AIGC/LLM/AI Agent算法/开发offer16. AIGC产业的深度思考与分析2023年3月21日微软创始人比尔·盖茨在其博客文章《The Age of AI has begun》中表示自从1980年首次看到图形用户界面graphical user interface以来以OpenAI为代表的科技公司发布的AIGC模型是他所见过的最具革命性的技术进步。Rocky也认为AIGC及其生态会成为AI行业重大变革的主导力量。AIGC会带来一个全新的红利期未来随着AIGC的全面落地和深度商用会深刻改变我们的工作、生活、学习以及交流方式各行各业都将被重新定义过程会非常有趣。那么在此基础上我们该如何更好的审视AIGC的未来我们该如何更好地拥抱AIGC引领的革新Rocky准备从技术、产品、商业模式、长期主义等维度持续分享一些个人的核心思考与观点希望能帮助各位读者对AIGC有一个全面的了解深入浅出全面解析AIGC时代核心价值与发展趋势2025年版17. AI算法工程师的独孤九剑秘籍为了方便大家实习、校招以及社招的面试准备同时帮助大家提升扩展技术基本面Rocky将符合大厂和AI独角兽价值的算法高频面试知识点撰写总结成《三年面试五年模拟》之独孤九剑秘籍:【三年面试五年模拟】AIGC时代的算法工程师的求职面试秘籍持续更新中18. 深入浅出完整解析AIGC时代中GANGenerative Adversarial Network系列模型核心基础知识GAN系列模型作为传统深度学习时代的最热门生成式Al模型在AIGC时代继续繁荣作为Stable Diffusion/FLUX系列大模型的“得力助手”广泛活跃于AlGC图像创作的产品与工作流中深入浅出完整解析AIGC时代中GANGenerative Adversarial Network系列模型核心基础知识 【三年面试五年模拟】2026-08-16_拼多多_笔试题与题解全解析
写在前面欢迎大家关注Rocky的知乎Rocky Ding《三年面试五年模拟》AIGC/LLM/AI Agent算法工程师/开发工程师求职面试秘籍独家资源【三年面试五年模拟】WeThinkIn/AIGC-Interview-Book欢迎大家StarRocky最新撰写的10万字AI AgentAI智能体深入浅出全维度解析文章深入浅出完整解析AI AgentAI智能体的核心基础知识AIGC/LLM/AI Agent算法岗/开发岗求职面试内推学习社群涵盖AIGC、LLM大模型、AI Agent、传统深度学习、自动驾驶、机器学习、计算机视觉、自然语言处理、强化学习、大数据挖掘、具身智能、元宇宙、AGI等AI行业最新面试干货经验与核心知识欢迎大家加入https://t.zsxq.com/33pJ0大家好我是Rocky。编程题1. 编程题求abc方案数题意给定数字n要求统计有多少组(a, b, c)满足1 ≤ a ≤ b ≤ c ≤ n 1 \le a \le b \le c \le n1≤a≤b≤c≤n并且a ⊕ b ⊕ c 0 , a b c a \oplus b \oplus c 0,\qquad abca⊕b⊕c0,abc其中^表示按位异或。题解异或满足结合律并且x ⊕ x 0 x \oplus x0x⊕x0、x ⊕ 0 x x \oplus 0xx⊕0x。由a ⊕ b ⊕ c 0 a \oplus b \oplus c0a⊕b⊕c0可得c a ⊕ b ca \oplus bca⊕b因此不需要枚举三元组只需枚举a和b计算唯一可能的c然后检查大小关系和abc。这已经把朴素的O(n^3)降为O(n^2)。defcount_abc(n:int)-int:ans0forainrange(1,n1):forbinrange(a,n1):ca^bifbcnandabc:ans1returnans这里必须保留b c检查因为ca^b并不保证三元组的非降序关系。abc也不能由异或条件推出必须单独判断。正确性检查对任意合法三元组前两个数(a,b)一定会被枚举异或等式又唯一确定ca^b所以不会漏解也不会因为同一个(a,b)产生多个c。反过来代码只统计同时满足b c n和abc的候选因此每个计数项都满足题面约束。时间复杂度为O(n^2)额外空间复杂度为O(1)。n1或没有满足条件的组合时答案自然为0Python 整数不会溢出但其他语言需要使用足够宽的计数类型。如果题目给出的n上限是约 2500枚举a,b通常已经足够是否需要更复杂的位运算优化必须由真实数据范围和时间限制决定不能仅凭“异或题”就过度优化。2. 编程题栈/队列判断题意给定两个相同长度的字符串S和T。按照S的顺序依次输入一个数据结构判断该数据结构的输出顺序可以是否为T。输出结果可能是栈、队列、两者都可能或者两者都不可能。题解队列是先进先出。所有字符都按照S的顺序进入队列因此它唯一可能的输出就是S本身如果S T队列一定可行如果S ! T队列一定不可行。栈是后进先出但每次入栈后可以选择暂不弹出也可以在合适时机弹出。用一个栈模拟即可遍历S每读入一个字符就压栈只要栈顶等于T[j]就不断弹栈并推进j。最终j len(T)说明存在一种弹栈顺序得到T。defjudge_structure(s:str,t:str)-str:iflen(s)!len(t):returnneitherqueue_okst stack[]j0forchins:stack.append(ch)whilestackandjlen(t)andstack[-1]t[j]:stack.pop()j1stack_okjlen(t)ifqueue_okandstack_ok:returnbothifstack_ok:returnstackifqueue_ok:returnqueuereturnneither例如Sabc、Tacb时队列不可行但可以先压入a并弹出再压入b,c最后按c,b弹出所以结果是stack。如果ST栈可以每次入栈后立即弹出因而结果应为both不能简单地把ST判成queue。为什么贪心弹栈是安全的当栈顶已经等于T[j]时若不弹出就无法让T[j]由栈中更底部的元素先输出弹出它不会改变后续入栈顺序且只会推进一个已经确定的目标字符。因此连续弹出所有匹配的栈顶字符不会丢失可行方案。若遍历结束后j len(T)说明剩余元素的栈顶顺序无法匹配目标栈一定不可行。空字符串若题面允许对栈和队列都可行长度不同则两者都不可行。每个字符最多入栈和出栈一次时间复杂度为O(n)额外空间复杂度为O(n)。实现时要特别注意重复字符不能用字符到位置的单值映射代替栈模拟。3. 编程题任务最大收益题意给定n个任务每个任务有开始和结束时间[s_i,e_i)以及价值v_i。选择一组时间上互不冲突的任务使价值总和最大。半开区间意味着任务i结束于e_i后可以接着执行开始于e_i的任务。题解这是带权区间调度问题。按结束时间升序排序令dp[i]表示排序后前i个任务能够获得的最大价值。对于第i个任务有两种选择不选它收益为dp[i-1]选它找到最后一个满足e_j s_i的任务j收益为dp[j] v_i。于是d p [ i ] max ( d p [ i − 1 ] , d p [ p ( i ) ] v i ) dp[i]\max\bigl(dp[i-1],\ dp[p(i)]v_i\bigr)dp[i]max(dp[i−1],dp[p(i)]vi)其中p(i)是按结束时间排序后、结束时间不晚于s_i的最后一个任务下标。由于结束时间有序p(i)可以二分查找。frombisectimportbisect_rightfromtypingimportList,Tupledefmax_task_value(tasks:List[Tuple[int,int,int]])-int:# 每个任务是 (start, end, value)题目保证 start end。taskssorted(tasks,keylambdaitem:item[1])ends[endfor_,end,_intasks]dp[0]*(len(tasks)1)fori,(start,_,value)inenumerate(tasks,start1):# 在前 i-1 个任务中找最后一个 end start 的任务。compatiblebisect_right(ends,start,0,i-1)takedp[compatible]value skipdp[i-1]dp[i]max(skip,take)returndp[-1]为什么可以只看最后一个兼容任务因为前缀dp[compatible]已经代表所有结束时间不晚于start_i的任务组合的最优值选择其中最后一个下标不会丢失更早任务的最优解。排序耗时O(n log n)每个任务进行一次二分查找耗时O(log n)总时间复杂度为O(n log n)额外空间复杂度为O(n)。如果使用按开始时间排序配合小根堆也可以做到O(n log n)但必须明确堆中维护的是已经完成任务的最优价值仅仅“把任务放进堆”并不能自动保证动态规划转移正确。正确性与边界排序后考虑前i个任务最优解要么不含第i个任务对应dp[i-1]要么包含它后一种情况下其余任务必须来自结束时间不晚于s_i的前缀最优收益正是dp[compatible]。两种情况覆盖且互斥归纳即可得到转移正确。半开区间的兼容条件是end start所以必须使用bisect_right。空任务列表返回0价值为负数时dp[i-1]会自然选择“不接这个任务”除非题目另有“必须选择至少一个任务”的约束。4. 编程题价值最大路径题意给定n个点和m条单向边。每条边按输入顺序给出(a_i,b_i,w_i)表示从a_i到b_i、权重为w_i的边。需要选择一条边序列使得后一条边的起点等于前一条边的终点后一条边的权重严格大于前一条边的权重后一条边必须在输入中晚于前一条边出现但不要求边在输入数组中连续。输出满足条件的最长路径边数。这里的“价值最大”容易造成误读题目真正优化的是路径边数w_i只用于约束严格递增不是让权重总和最大。题解按输入顺序处理边。定义best[v][w]表示已经处理的边中以点v为终点、最后一条边权为w的最长合法路径长度。处理当前边(a,b,w)时前一条边必须已经到达a且其权重严格小于w所以c u r 1 max u w b e s t [ a ] [ u ] cur1\max_{uw}best[a][u]cur1uwmaxbest[a][u]然后把这条边作为新路径的最后一条边更新best[b][w] max(best[b][w], cur)。查询必须先于更新因为当前边不能接在自己后面而且使用严格小于w的前缀查询等权边不能连接。每个点上的权重值域可以离散化并为每个点维护一棵 Fenwick Tree树状数组树状数组支持查询权重排名小于当前权重的最大路径长度更新当前终点和当前权重对应的最大值。frombisectimportbisect_leftfromcollectionsimportdefaultdictfromtypingimportList,TupleclassFenwickMax:def__init__(self,size:int)-None:self.tree[0]*(size1)defupdate(self,index:int,value:int)-None:whileindexlen(self.tree):self.tree[index]max(self.tree[index],value)indexindex-indexdefquery(self,index:int)-int:result0whileindex0:resultmax(result,self.tree[index])index-index-indexreturnresultdeflongest_increasing_path(n:int,edges:List[Tuple[int,int,int]])-int:# 先按终点收集该点可能出现的所有权重建立离散坐标。weightsdefaultdict(list)for_,end,weightinedges:weights[end].append(weight)trees{}forvertex,valuesinweights.items():orderedsorted(set(values))trees[vertex](ordered,FenwickMax(len(ordered)))answer0forstart,end,weightinedges:ordered,treetrees[start]ifstartintreeselse([],None)# 当前边的前驱必须权重严格小于 weight。rankbisect_left(ordered,weight)previoustree.query(rank)iftreeisnotNoneelse0currentprevious1target_ordered,target_treetrees[end]target_rankbisect_left(target_ordered,weight)1target_tree.update(target_rank,current)answermax(answer,current)returnanswer上面代码中树建立在“前一条边的终点”上处理当前边时从trees[start]查询再把结果更新到trees[end]。这正是端点衔接条件的实现。正确性检查按输入顺序处理到第i条边时树中只保存第i-1条及之前的状态因而自动满足“后一条边在输入中更晚”。查询start的权重前缀只取 weight恰好对应端点连续且权重严格递增的所有合法前驱若没有前驱前缀最大值为0当前边单独构成长度1的路径。再将current写入end的当前权重位置就维护了所有以该状态结尾的最优值。对输入顺序归纳可知最终answer是所有合法路径的最大边数。参数n只描述点编号范围算法实际只需读取边列表空边列表会返回0。权重可能相同或为负数离散化和bisect_left仍然成立关键是查询排名严格小于当前权重而更新时使用当前权重的排名。设某个点关联的不同权重总数为k_v则每次查询和更新为O(log k_v)总时间复杂度为O(m log m)离散化和树状数组占用O(m)空间。若所有权重已经是小范围整数也可以直接使用数组或线段树不能把复杂度写成O(m log n)除非题目明确说明权重值域或点数与权重离散规模存在相应约束。推荐阅读1. 深入浅出完整解析AI AgentAI智能体的核心基础知识2025年可以说是AI Agent全面落地应用的元年因此Rocky在持续撰写对AI Agent的全维度解析文章深入浅出完整解析AI AgentAI智能体的核心基础知识2. 深入浅出完整解析扩散模型DDPM、DDIM、Score-Based、SDE、LDM、Classifier/Classifier-Free Guidance、Rectified Flow核心基础知识Rocky对扩散模型的本质原理与和核心基础知识进行了全面系统的深入浅出分析讲解同时不断跟进补充扩散模型的最新技术发展希望能给大家带来帮助深入浅出完整解析扩散模型DDPM、DDIM、Score-Based、SDE、LDM、Classifier/Classifier-Free Guidance、Rectified Flow核心基础知识3. 入浅出完整解析FLUX.2、Seedream即梦、Z-image、GLM-Image核心基础知识Rocky对AIGC时代“中场时刻”之后的主流AIGC创作大模型的核心基础知识进行了全面系统的深入浅出分析讲解力求让大家通俗易懂理解AIGC时代的技术浪潮的本质价值入浅出完整解析FLUX.2、Seedream即梦、Z-image、GLM-Image核心基础知识4. 深入浅出完整解析FLUX.1 Kontext和FLUX.1 Krea核心基础知识Rocky对FLUX.1 Kontext和FLUX.1 Krea的核心基础知识作了全面系统的梳理与解析深入浅出完整解析FLUX.1 Kontext和FLUX.1 Krea核心基础知识5. 深入浅出完整解析DeepSeek系列核心基础知识Rocky对DeepSeek系列模型的核心基础知识作了全面系统的梳理与解析深入浅出完整解析DeepSeek系列核心基础知识6. 深入浅出完整解析Stable Diffusion 3SD 3和FLUX.1系列核心基础知识Rocky对Stable Diffusion 3和FLUX.1的核心基础知识作了全面系统的梳理与解析深入浅出完整解析Stable Diffusion 3SD 3和FLUX.1系列核心基础知识7. 深入浅出完整解析Stable Diffusion XLSDXL核心基础知识Rocky对Stable Diffusion XL的核心基础知识作了全面系统的梳理与解析深入浅出完整解析Stable Diffusion XLSDXL核心基础知识8. 深入浅出完整解析Stable DiffusionSD核心基础知识Rocky对Stable Diffusion 1.x-2.x系列模型的核心基础知识做了全面系统的梳理与解析深入浅出完整解析Stable DiffusionSD核心基础知识9. 深入浅出完整解析Stable Diffusion中U-Net的前世今生与核心知识Rocky对Stable Diffusion中最为关键的U-Net结构进行了深入浅出的全面解析包括其在传统深度学习中的价值和在AIGC中的价值深入浅出完整解析Stable Diffusion中U-Net的前世今生与核心知识10. 深入浅出完整解析LoRALow-Rank Adaptation模型核心基础知识对于AIGC时代中的“ResNet”——LoRA模型Rocky进行了深入浅出的全面讲解深入浅出完整解析LoRALow-Rank Adaptation模型核心基础知识11. 深入浅出完整解析ControlNet核心基础知识AIGC图像创作开源社区已经形成以Stable Difffusion/FLUX为核心ConrtolNet和LoRA作为首要AI辅助工具的变化万千的AIGC图像创作工作流。ControlNet正是让AI图像创作社区无比繁荣的关键一环它让AIGC图像创作过程更加的可控更有助于广泛地将AIGC算法解决方案应用到各行各业中深入浅出完整解析ControlNet核心基础知识12. 深入浅出完整解析Sora、Seedance、keling等AI视频大模型核心基础知识AI绘画和AI视频是两个互相促进、相互交融的领域2024年无疑是AI视频领域的爆发之年Rocky对AI视频领域核心的Sora、Seedance、Keling等大模型进行了全面系统的梳理与解析深入浅出完整解析Sora、Seedance、keling等AI视频大模型核心基础知识13. 深入浅出完整解析AIGC时代Transformer核心基础知识在AIGC时代中Transformer为AI行业带来了深刻的变革。Transformer架构正在一步一步重构所有的AI技术方向成为AI技术架构大一统与多模态整合的关键核心基座大有一统“AI江湖”之势。Rocky也对Transformer模型进行持续的深入浅出梳理与解析深入浅出完整解析AIGC时代Transformer核心基础知识14. 深入浅出完整解析ComfyUI、Diffusers、Stable Diffusion WebUI等主流AIGC创作框架核心基础知识AIGC创作框架正是AIGC算法工作流的运行载体目前主流的AIGC创作框架有ComfyUI、Diffusers、Stable Diffusion WebUI等。在传统深度学习时代PyTorch、TensorFlow以及Caffe是传统深度学习模型的基础运行框架到了AIGC时代Rocky相信ComfyUI就是AIGC时代的“PyTorch”、Stable Diffusion WebUI就是AIGC时代的“TensorFlow”、Diffusers就是AIGC时代的“Caffe”深入浅出完整解析ComfyUI、Diffusers、Stable Diffusion WebUI等主流AIGC创作框架核心基础知识15. 深入浅出完整解析ComfyUI、Diffusers、Stable Diffusion WebUI等主流AIGC创作框架核心基础知识在AIGC时代中如何快速转身入局AIGC产业如何成为AIGC/LLM/AI Agent算法/开发工程师如何在学校中系统性学习AIGC/LLM/AI Agent知识斩获心仪的AIGC/LLM/AI Agent算法/开发offerDon‘t worryRocky为大家总结整理了全面的AIGC/LLM/AI Agent算法/开发工程师成长秘籍为大家答疑解惑希望能给大家带来帮助手把手教你成为AIGC/LLM/AI Agent算法/开发工程师斩获AIGC/LLM/AI Agent算法/开发offer16. AIGC产业的深度思考与分析2023年3月21日微软创始人比尔·盖茨在其博客文章《The Age of AI has begun》中表示自从1980年首次看到图形用户界面graphical user interface以来以OpenAI为代表的科技公司发布的AIGC模型是他所见过的最具革命性的技术进步。Rocky也认为AIGC及其生态会成为AI行业重大变革的主导力量。AIGC会带来一个全新的红利期未来随着AIGC的全面落地和深度商用会深刻改变我们的工作、生活、学习以及交流方式各行各业都将被重新定义过程会非常有趣。那么在此基础上我们该如何更好的审视AIGC的未来我们该如何更好地拥抱AIGC引领的革新Rocky准备从技术、产品、商业模式、长期主义等维度持续分享一些个人的核心思考与观点希望能帮助各位读者对AIGC有一个全面的了解深入浅出全面解析AIGC时代核心价值与发展趋势2025年版17. AI算法工程师的独孤九剑秘籍为了方便大家实习、校招以及社招的面试准备同时帮助大家提升扩展技术基本面Rocky将符合大厂和AI独角兽价值的算法高频面试知识点撰写总结成《三年面试五年模拟》之独孤九剑秘籍:【三年面试五年模拟】AIGC时代的算法工程师的求职面试秘籍持续更新中18. 深入浅出完整解析AIGC时代中GANGenerative Adversarial Network系列模型核心基础知识GAN系列模型作为传统深度学习时代的最热门生成式Al模型在AIGC时代继续繁荣作为Stable Diffusion/FLUX系列大模型的“得力助手”广泛活跃于AlGC图像创作的产品与工作流中深入浅出完整解析AIGC时代中GANGenerative Adversarial Network系列模型核心基础知识