-
【进阶】4、排序（四）
目录 快速排序（Quick Sort） 希尔排序（Shell Sort）快速排序（Quick Sort）快速排序（Quick Sort） 1960年由查尔斯·安东尼·理查德·霍尔（Charles Antony Richard Hoare，缩写为C. A. R. Hoare）提出 昵称为东尼·霍尔（Tony Hoare）一、快速排序 – 执行流程① 从序列中选择一个轴点元素（pivot） ✓ 假设每次选择 0 位置的元素为轴点元素② 利用 pivot 将序列分割成 2 个...…
-
【进阶】3、排序（三）
目录 归并排序（Merge Sort） 归并排序原理 归并排序实现 复杂度分析归并排序（Merge Sort）1945年由约翰·冯·诺伊曼（John von Neumann）首次提出执行流程divide ① 不断地将当前序列平均分割成2个子序列 ✓ 直到不能再分割（序列中只剩1个元素）merge ② 不断地将2个子序列合并成一个有序序列 ✓ 直到最终只剩下1个有序序列归并排序原理一、divide实现-(void)sort{ [self sortWithBegin:0 en...…
-
【进阶】2、排序（二）
目录 插入排序（Insertion Sort） 二分搜索（Binary Search） 插入排序优化插入排序（Insertion Sort）一、插入排序原理插入排序非常类似于扑克牌的排序执行流程 ① 在执行过程中，插入排序会将序列分为2部分 ✓ 头部是已经排好序的，尾部是待排序的 ② 从头开始扫描每一个元素 ✓ 每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序二、代码实现//时间复杂度:最好O(n)、最坏O(n^2)、平均O(n^2)//空间复杂度O(...…
-
【进阶】1、排序
目录 初识排序 冒泡排序（Bubble Sort） 选择排序（Selection Sort） 堆排序（Heap Sort）初识排序一、什么叫排序？排序前：3,1,6,9,2,5,8,4,7 排序后：1,2,3,4,5,6,7,8,9（升序） 或者 9,8,7,6,5,4,3,2,1（降序）排序的应用无处不在二、十大排序算法 名称 时间复杂度(最好) 时间复杂度(最坏) 时间复杂度((平均) 空间复杂度 In-...…
-
【基础】20、速览(数据结构与算法一)
目录 【基础】1、复杂度 【基础】2、动态数组 【基础】3、链表（一） 【基础】4、链表（二） 【基础】5、链表（三） 【基础】链表相关算法 【基础】6、栈与队列 【基础】栈与队列相关算法 【基础】7、二叉树（一） 【基础】8、二叉树（二） 【基础】9、二叉树（三） 【基础】10、AVL树 【基础】11、B树 【基础】12、红黑树 【基础】13、集合与映射 【基础】14、哈希表（一） 【基础】15、哈希表（二） 【基础】16、二叉堆 【基础】17、优先...…
-
【基础】19、Trie
目录 Trie 接口设计与实现 总结TrieTrie 特里结构；单词查找树 Trie 也叫做字典树、前缀树（Prefix Tree）、单词查找树 Trie 搜索字符串的效率主要跟字符串的长度有关 假设使用 Trie 存储 cat、dog、doggy、does、cast、add 六个单词接口设计与实现接口设计@interface LCTrie : NSObject/// 元素数量（key or value 的数量）-(int)size;/// 是否为空-(BOOL)isEmpt...…
-
【基础】18、哈夫曼编码
目录 哈夫曼编码(Huffman Coding) 哈弗曼树 构建哈夫曼编码哈夫曼编码(Huffman Coding)哈夫曼编码，又称为霍夫曼编码，它是现代压缩算法的基础 假设要把字符串【ABBBCCCCCCCCDDDDDDEE】转成二进制编码进行传输 可以转成ASCII编码（65~69，1000001~1000101），但是有点冗长，如果希望编码更短呢？可以先约定5个字母对应的二进制 A B C D E ...…
-
【基础】17、优先级队列
目录 优先级队列 优先级队列场景举例 优先队列的底层实现优先级队列优先级队列也是个队列，因此也是提供以下接口@interface LCPriorityQueue : NSObject/// 创建一个优先级队列+(instancetype)priorityQueue;/// 创建一个优先级队列/// @param comparator 自定义比较器+(instancetype)priorityQueueWithComparator:(nullable LCCompareBlock)co...…
-
【基础】16、二叉堆
目录 思考 堆 二叉堆 批量建堆 Top K 问题思考一、设计一种数据结构设计一种数据结构，用来存放整数，要求提供 3 个接口 添加元素 获取最大值 删除最大值 获取最大值 删除最大值 添加元素 动态数组\双向链表 O(n) O(n) O(1) 有序动态数组\双向链表 O(1) O(1) ...…
-
【基础】15、哈希表（二）
目录 TreeMap vs HashMap LinkHashMapTreeMap vs HashMap何时选择TreeMap？ 元素具备可比较性且要求升序遍历（按照元素从小到大）何时选择HashMap？ 无序遍历LinkHashMap在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的一、添加节点我们在添加节点的时候，同时再维护一个双向链表来记录节点的添加顺序。假设添加顺序是 37、21、31、41、97、95、52、42、83二、删除节点1、删除叶子...…
-
【基础】14、哈希表（一）
目录 TreeMap分析 哈希表 哈希函数 哈希值 哈希表内的红黑树 哈希表的扩容TreeMap分析◼ 时间复杂度（平均） 添加、删除、搜索：O(logn)◼ 特点 Key 必须具备可比较性 元素的分布是有顺序的◼ 在实际应用中，很多时候的需求 Map 中存储的元素不需要讲究顺序 Map 中的 Key 不需要具备可比较性◼ 不考虑顺序、不考虑 Key 的可比较性，Map 有更好的实现方案，平均时间复杂度可以达到 O(1) 那就是采取哈希表来实现 Map哈希表一...…
-
【基础】13、集合与映射
目录 集合 映射 Map 与 Set集合◼ 集合的特点 不存放重复的元素 常用于去重 ✓ 存放新增 IP，统计新增 IP 量 ✓ 存放词汇，统计词汇量 ✓ ……◼ 思考：集合的内部实现能否直接利用以前学过的数据结构？ 动态数组 链表 二叉搜索树（AVL树、红黑树）集合的接口设计@protocol LCSetProtocol <NSObject>/// 清除所有元素-(void)clear;/// 元素的数量-(int)size;/// 是...…
-
【基础】12、红黑树
目录 红黑树介绍 添加 删除 红黑树总结红黑树介绍一、红黑树的性质红黑树也是一种自平衡的二叉搜索树 以前也叫做平衡二叉B树（Symmetric Binary B-tree）红黑树必须满足以下 5 条性质 节点是 RED 或者 BLACK 根节点是 BLACK 叶子节点（外部节点，空节点）都是 BLACK RED 节点的子节点都是 BLACK ✓ RED 节点的 parent 都是 BLACK ✓ 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点 从任...…
-
【基础】11、B树
目录 B树介绍 m阶B树性质 B树 VS 二叉搜索树 搜索 添加 删除 4阶B树B树介绍◼ B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现◼ 仔细观察B树，有什么眼前一亮的特点？ 1个节点可以存储超过2个元素、可以拥有超过2个子节点 拥有二叉搜索树的一些性质 平衡，每个节点的所有子树高度一致 比较矮m阶B树性质一、节点的元素个数1 ≤ 根节点元素个数 ≤ m − 1 ┌ m/2 ┐ − 1 ≤ 非根节点元素个数 ≤ m − 1二、节点的子节点个数如...…
-
【基础】10、AVL树
目录 AVL树 添加导致的失衡 删除导致的失衡 总结AVL树一、简介AVL树是最早发明的自平衡二叉搜索树之一AVL 取名于两位发明者的名字 G. M. Adelson-Velsky 和 E. M. Landis（来自苏联的科学家）二、特点◼ 平衡因子（Balance Factor）：某结点的左右子树的高度差◼ AVL树的特点 每个节点的平衡因子只可能是 1、0、-1（绝对值 ≤ 1，如果超过 1，称之为“失衡”） 每个节点的左右子树高度差不超过 1 搜索、...…
-
【基础】9、二叉树（三）
目录 二叉搜索树删除 平衡二叉搜索树二叉树删除一、删除叶子节点◼ 直接删除 node == node.parent.left ✓ node.parent.left = nullnode == node.parent.right ✓ node.parent.right = nullnode.parent == null ✓ root = null二、删除度为1的节点child 是 node.left 或者 child 是 node.right 用 child 替代...…
-
【基础】8、二叉树（二）
目录 二叉树遍历 二叉树遍历应用 根据遍历结果重构二叉树 遍历相关练习 前驱与后继节点二叉树遍历遍历是数据结构中的常见操作,把所有元素都访问一遍线性数据结构的遍历比较简单 正序遍历 逆序遍历根据节点访问顺序的不同，二叉树的常见遍历方式有4种 前序遍历（Preorder Traversal） 中序遍历（Inorder Traversal） 后序遍历（Postorder Traversal） 层序遍历（Level Order Traversal）一、前序遍历访...…
-
【基础】7、二叉树（一）
目录 树形结构 二叉树 二叉搜索树树形结构生活中的树形结构使用树形结构可以大大提高效率一、树的基本概念1、节点按节点位置：根节点、父节点、子节点、兄弟节点按节点的度：叶子节点（度为0的节点）、非叶子节点（度不为0的节点）节点的度（degree）：子树的个数节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数2、树子树、左子树、右子树空树：没有任何节点的树有序树：树中任意节点的子节点之间有顺序关系无序树...…
-
【基础】6、栈与队列
目录 栈 队列 栈与队列的相互实现栈一、简介栈是一种特殊的线性表，只能在一端进行操作往栈中添加元素的操作，一般叫做 push，入栈从栈中移除元素的操作，一般叫做 pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）后进先出的原则，Last In First Out，LIFO注意：这里说的“栈”与内存中的“栈空间”是两个不同的概念二、栈的接口设计与实现1、接口设计/// 获取栈中元素的数量-(int)size;/// 是否为空-(BOOL)isEmpty;/// 入栈/// @par...…
-
【基础】5、链表（三）
目录 单向循环链表 双向循环链表 约瑟夫问题 静态链表单向循环链表一、单向循环链表示例图多节点单节点二、单向循环链表节点的添加与删除- (void)add:(int)index element:(nonnull id)element { [self rangeCheckForAdd:index]; /** 需要考虑多种情况下的适用性问题： 1、中间位置 2、头、尾位置 3、首次添加 */ /...…
