算法练习 目录 十个常用数据结构 数组 按照下表快速访问数组中的元素 数组中插入和删除操作 链表 实现单链表 在单链表中实现查找、插入、删除、查找第 k 个元素 实现双向链表 在单、双链表中实现删除“值等于给定值”的节点,删除给定指针指向的节点 如何基于链表实现 LRU 缓存淘汰算法? 单链表反转 链表中环的检测 两个有序的链表合并 删除链表倒数第 k 个节点 寻找链表的中间节点 栈 基于数组实现的顺序栈 队列 实现顺序队列,即基于数组来实现 实现链式队列,即基于链表来实现 实现循环队列 如何用队列实现栈 如何用栈实现队列 哈希表 Word 软件中的单词拼写检查功能是如何实现的? 假设有 10 万条 URL 访问日志,如何按照访问次数给 URL 排序? 有两个字符串数组,每个数组大约有 10 万个字符串,如何快速找出两个数组中相同的字符串? 利用哈希表优化 LRU 缓存淘汰算法? 二叉树 基于链表实现二叉树 基于数组实现二叉树 实现二叉树遍历:前序遍历、中序遍历、后序遍历 如何实现按层遍历? 二叉查找树的查找、插入和删除操作 堆 实现堆及其插入、查询、删除操作 堆的应用1: 优先级队列 堆的应用2: 求 TopK 堆的应用3: 求中位数和百分位数 堆的应用: 如何快速获取 Top 热门搜索关键词 跳表 跳表的概念 图 使用邻接矩阵的存储方法实现图 使用邻接表的存储方法实现图 微博、微信等社交网络中的好友关系是如何存储的? Trie 树 如何实现搜索引擎的搜索关键词提示功能? 十个常用算法 递归 计算台阶的 n 种走法 排序算法 冒泡排序 插入排序 选择排序 归并排序 快速排序 桶排序 计数排序 基数排序 二分查找算法 二分查找的递归与非递归实现 如何编程实现“求一个数的平方根”(要求精度到小数点后 6 位) 变体1: 查找第一个值等于给定值的元素 变体2: 查找最后一个值等于给定值的元素 变体3: 查找第一个值大于或等于给定值的元素 变体4: 查找最后一个值小于或等于给定值的元素 变体: 如何快速定位 IP 地址对应的归属地 变体: 如果有序数组是一个循环有序数组,如 [4,5,6,1,2,3],那么,针对这种情况如何实现一个求“值等于给定值”的二分查找算法呢? 搜索算法 广度优先搜索 深度优先搜索 哈希算法 哈希算法的原理和应用 贪心算法 贪心算法解决问题的步骤 分治算法 理解分治算法 回溯算法 理解回溯算法 动态规划 理解动态规划 字符串匹配算法 BF 算法 RK 算法 BM 算法