王道程序员求职宝典（九）基本算法及链表
2022-04-24 本文已影响0人
Die时而动
分治法，动态规划与贪心算法
- 分治法
- 特征
- 分解
- 解决
- 合并
- 递归：自顶向下
- 特征
- 动态规划
- 要素
- 最优子结构
- 重叠子问题
- 递推：自底向上
- 步骤
- 描述最优解结构
- 递归定义最优解的值
- 递推自底向上计算最优解的值
- 从结果构造出最优解的值
- 经典问题
- LCS最长公共子序列
- 求字符串编辑距离
- 要素
- 贪心算法
- 局部最优选择
- 经典应用
- 最小生成树
- 哈夫曼树
- 单源最短路径
- 经典问题
- 背包问题
- 01背包动态规划
- 部分背包贪心算法
- 背包问题
链表
- 单链表
- 建立，插入，删除
- 和顺序表的比较
- 快慢指针
- 概念
- 基本问题
- 判断单链表有无环
- 定位循环链表入口
- 有序链表寻找中位数
- 寻找倒数第k个节点
- 判断链表是否相交
- 两个有无环
- 都无环
- 一个有：不可能相交
- 两个有：是否同一个环
- 两个有无环
- 判断单链表有无环
- 双链表
- 双链表插入删除
- 变形双链表
- 一个next，一个任意指向
- 链表克隆（关键在于第二个指针如何赋值）
- 暴力法
- 利用一个哈希表
- 克隆节点插入原节点后方，分配指针，再拆分
- 循环单/双链表
