干货版《算法导论》12：双向链表优化与拆砖问题双解法

干货版《算法导论》12双向链表优化与拆砖问题双解法前言Bilibili 同步视频一、有序数组 指针优化双向链表移位算法1.1 原始痛点原生双向链表的短板1.2 优化思路有序容器绑定链表节点指针1.3 moveBelow (x,y) 三步走实现逻辑1.4 C 完整实现代码1.5 落地答疑Python 无原生指针如何模拟二、野狼拆砖屋问题剥故事外壳解数组统计内核2.1 题意去魅拨开童话伪装2.2 特殊约束版仅一处非特殊房屋数组两段有序2.3 无特殊约束通用版算法思路三、算法优化思想复盘总结结语前言算法之学穷数据结构之妙探时空复杂度之规。或借链表以序存数据或凭指针以优化寻址或借寓言包装数理剥浮华而露内核。本篇拆解两道经典算法作业真题其一为有序集合绑定指针优化双向链表移位操作其二为披着野狼拆屋外衣的数组统计问题一文尽述二分寻址、双指针滑动两大常用算法思想附原理图文、C 落地源码厘清时空复杂度优化思路。Bilibili 同步视频干货版《算法导论》12双向链表优化与拆砖问题双解法骈句开篇链表存序困于线性遍历之迟索引附针巧取对数寻址之捷。砖屋列阵故事掩数组真意双指同巡线性遍历破繁难。一、有序数组 指针优化双向链表移位算法1.1 原始痛点原生双向链表的短板双向链表天然优势在于节点插入、删除仅需修改邻域指针O (1) 完成局部改链却有致命缺陷若需随机定位指定节点只能从头逐个遍历最坏遍历全表时间复杂度O ( N ) O(N)O(N)。原题需求给定若干文档编号以双向链表有序存储实现moveBelow(x,y)操作将节点 x 从原位置摘除接入 y 节点后方要求单次操作整体复杂度控制在O ( l o g N ) O(logN)O(logN)。若仅依靠裸链表查找 x、y 两个目标节点便耗时O ( N ) O(N)O(N)无法满足题目性能约束。【原生链表结构文本示意图】 裸双向链表 1 - 5 - 3 - 2 -7 无辅助索引查找3从头1→5→3遍历3次 O(N)1.2 优化思路有序容器绑定链表节点指针破局之策有序集合存主键 链表节点指针以空间换时间。有序数组 / 平衡树存储所有文档主键依托二分查找O ( l o g N ) O(logN)O(logN)快速锁定目标键每个键附属一块指针直接指向双向链表内真实节点无需遍历链表寻址。【优化后整体架构文本示意图】 有序索引数组【键指针】 [1(→链表1节点), 2(→链表2节点),3(→链表3节点),5(→链表5节点),7(→链表7节点)] 双向链表1 -5 -3 -2 -7 指针特性删除链表中3节点其余所有索引内指针不受改动永久有效骈文注解键入有序之阵二分寻位须臾针连链表之身定点改链瞬息。删一节点而全索引无恙改一处链路而主键序如常。1.3 moveBelow (x,y) 三步走实现逻辑整项操作拆解为三大步骤分步拆解复杂度步骤 1二分索引找 x、y在有序索引容器二分查找 keyx、keyy取出二者绑定的链表指针O ( l o g N ) O(logN)O(logN)步骤 2链表摘除 x 节点利用双向链表前驱、后继指针断开 x 与前后节点关联局部指针修改O ( 1 ) O(1)O(1)步骤 3x 接入 y 尾部修改 y 与 y 原后继的指针把 x 插入 y 之后局部指针重定向O ( 1 ) O(1)O(1)。总耗时O ( l o g N ) O ( 1 ) O ( 1 ) O ( l o g N ) O(logN)O(1)O(1)O(logN)O(logN)O(1)O(1)O(logN)完美匹配题目性能需求。补充关键细节moveBelow 仅调整链表节点排布顺序所有文档主键无新增、无删减有序索引数组内容完全不需要改动省去索引同步开销。1.4 C 完整实现代码依托 STLvector做有序索引自定义双向链表结构体指针存储链表节点地址#includeiostream#includevector#includealgorithmusingnamespacestd;// 双向链表节点结构体structListNode{intkey;ListNode*prev;ListNode*next;ListNode(intk):key(k),prev(nullptr),next(nullptr){}};// 索引单元存储键对应链表节点指针structIndexItem{intval;ListNode*ptr;// 重载小于号用于二分查找booloperator(constinttarget)const{returnvaltarget;}};vectorIndexItemsortedIndex;// 全局有序索引数组// 二分查找返回对应链表节点指针ListNode*findNode(inttargetKey){autoposlower_bound(sortedIndex.begin(),sortedIndex.end(),targetKey);returnpos-ptr;}// 将x移动至y的后面voidmoveBelow(intx,inty){ListNode*xNodefindNode(x);ListNode*yNodefindNode(y);// 1.摘除x节点ListNode*preXxNode-prev;ListNode*nxtXxNode-next;if(preX)preX-nextnxtX;if(nxtX)nxtX-prevpreX;// 2.x接入y之后ListNode*nxtYyNode-next;yNode-nextxNode;xNode-prevyNode;xNode-nextnxtY;if(nxtY)nxtY-prevxNode;}intmain(){// 初始化链表1-5-3-2-7ListNode*n1newListNode(1),*n5newListNode(5),*n3newListNode(3);ListNode*n2newListNode(2),*n7newListNode(7);n1-nextn5;n5-prevn1;n5-nextn3;n3-prevn5;n3-nextn2;n2-prevn3;n2-nextn7;n7-prevn2;// 构建有序索引sortedIndex{{1,n1},{2,n2},{3,n3},{5,n5},{7,n7}};// 测试把3挪到7后方moveBelow(3,7);coutFinish Move Operationendl;return0;}1.5 落地答疑Python 无原生指针如何模拟C 依托内存指针直接绑定节点地址Python 无显性指针实现思路为自定义对象实例索引内存储对象引用引用等价于指针功能底层原理相通。二、野狼拆砖屋问题剥故事外壳解数组统计内核2.1 题意去魅拨开童话伪装原题以西方野狼、波特兰房屋、西风拆屋构建故事背景本质是纯数组算法统计题给定一维数组a r r arrarr代表自西向东排布房屋的砖块数量选定下标i ii拆房摧毁a r r [ i ] arr[i]arr[i]本身同时摧毁右侧所有 ** 数值小于 arr [i]** 的元素求每个下标对应可摧毁房屋总数生成结果数组 ans。示例数组[34,57,70,19,48,2]逐个演算 i0(34): 右侧3419、2 → 合计3间(自身2间)3 i1(57): 右侧5719、48、2 → 合计4间 i2(70): 右侧全部小于70 → 合计4间骈句野狼呼啸本是童话虚妄砖屋错落实为数组列章。去风物之繁饰留统计之本体。2.2 特殊约束版仅一处非特殊房屋数组两段有序特殊房屋定义①最右侧末尾房屋②右侧紧邻房屋砖块数≥当前房屋。全数组仅有一间非特殊房屋 → 原数组天然被划分为左段单调递增、右段同样单调递增两个有序子数组。例[2,3,4,5,2,3,4]仅下标 3 (5) 为非特殊点位左[2,3,4,5]升序右[2,3,4]升序。数组分段文本图示 [左升序区分割点右升序区] 2 3 4 5 | 分割线 | 2 3 4 左逐个变大右逐个变大方案选型双指针滑动算法Two FingerO ( N ) O(N)O(N)线性复杂度普通暴力双循环统计复杂度O ( N 2 ) O(N^2)O(N2)二分遍历优化O ( N l o g N ) O(NlogN)O(NlogN)依托两段升序特性同向双指针仅遍历一次全数组O ( N ) O(N)O(N)最优解。核心规律左段数值自左向右逐步变大能摧毁的右区间范围只会不断向右扩张右指针j只递增、永不回退。C 双指针实现代码#includeiostream#includevectorusingnamespacestd;vectorintcalcDamage(vectorintarr,intsplitPos){vectorintres(arr.size(),1);// 自身占1间intnarr.size();intjsplitPos;// 右指针起始在分段位置// 遍历左升序区间for(inti0;isplitPos;i){// j不断右移找到首个arr[i]的位置while(jnarr[j]arr[i])j;res[i]j-i;}// 右升序区间每个元素只能拆自身ans全为1for(intisplitPos;in;i)res[i]1;returnres;}intmain(){vectorintarr{2,3,4,5,2,3,4};vectorintanscalcDamage(arr,4);for(autox:ans)coutx ;return0;}运行输出7 6 5 4 1 1 12.3 无特殊约束通用版算法思路若无 “仅一间特殊房屋” 前置条件数组无序无法使用双指针线性解法可依托归并排序的分治思想在归并过程统计右侧小于当前值的元素数量整体复杂度O ( N l o g N ) O(NlogN)O(NlogN)是此类逆序统计类问题的通用范式。三、算法优化思想复盘总结骈文小结其一附针于索引以二分破链表遍历之困对数耗时是空间换速率之典其二双指同巡弋借有序缩区间查找之繁线性遍历是规律破暴力之弊。索引 指针优化链表遇到随机查找 局部增删场景优先思考「辅助索引 实体指针 / 引用」拆分查找与修改的复杂度查找对数、改链常数双指针滑动技巧数组分段有序、单调性明确时优先同向 / 对向双指针规避嵌套循环压至线性复杂度算法剥壳思维工程与习题常以业务、故事包装数理逻辑解题首步剥离无效场景描述提炼纯数学模型是算法入门必备素养。结语算法研习不在记代码之形而在悟优化之理。链表附针明索引优化之方拆砖寻数晓双指针妙用之法。举一反三遇同类题目便可触类旁通于笔试、工程开发皆大有裨益。