难度中等,两题均属于"先把过程抽象清楚再去实现"的类型,考察方向一是字符串DP状态设计,二是整数图建模+BFS,基本功扎实可以稳拿。📌
T1核心洞察是:每次只处理最前面三个字符,压缩顺序固定无任何分支。状态只需记录"当前前缀压成哪个字符",共26种,每轮枚举26×26个字符对做转移,初值全为1,共(n-1)/2轮。坑点有两处:答案可能天文数字须上大整数;n≤1e5导致DP轮数达5万,Python逐步累加需注意常数,预处理trans矩阵避免重复枚举规则。🔥
T2本质是整数图最短路。x→2x、x→⌊x/2⌋、x+1三种操作建边,BFS距离即步数。建模关键:两人各自走到会合点t的步数之和恰好是总步数,因此从a和b分别跑一次BFS,枚举所有点取da[t]+db[t]最小值即可。上界LIM=200000覆盖最优会合点范围,数据规模极小,暴力无压力。💡
备考建议:T1"固定压缩顺序→26维DP"这类降维思路在大厂中频繁变体出现,核心是先判断操作顺序有无分支;T2"枚举会合点=双源BFS"是图论建模必背套路。T1大整数你踩坑了吗?评论区聊聊👇
#京东笔试 #算法笔试 #春招备考 #字符串DP #BFS最短路
#2026春招 #京东 #暑期实习