-
【进阶】8、图（二）
目录 图的实现方案 图的基本接口定义 图的基本接口实现图的实现方案图有2种常见的实现方案 邻接矩阵（Adjacency Matrix） 邻接表（Adjacency List）一、邻接矩阵（Adjacency Matrix）1、邻接矩阵的存储方式一维数组存放顶点信息 二维数组存放边信息邻接矩阵比较适合稠密图不然会比较浪费内存2、邻接矩阵带权图二、邻接表（Adjacency List）1、邻接表存储方式2、邻接表带权图图的基本接口定义@protocol LCGraphProto...…
-
【进阶】7、图
目录 常见数据结构 图(Graph) 图(Graph)的分类常见数据结构线性结构：数组、链表、栈、队列、哈希表树形结构：二叉树、B树、堆、Trie、哈夫曼树、并查集图(Graph)一、介绍图由顶点（vertex）和边（edge）组成，通常表示为 G = (V, E) G:表示一个图，V是顶点集，E是边集 V:顶点集V有穷且非空 E:任意两个顶点之间都可以用边来表示它们之间的关系，边集E可以是空的二、应用举例图结构的应用极其广泛 社交网络 地图导航 ...…
-
【进阶】6、并查集
目录 并查集（Union Find） 并查集（Union Find）实现 并查集（Union Find）优化 总结 关于自定义类型并查集（Union Find）一、需求分析假设有n个村庄，有些村庄之间有连接的路，有些村庄之间并没有连接的路设计一个数据结构，能够快速执行2个操作 查询2个村庄之间是否有连接的路 连接2个村庄数组、链表、平衡二叉树、集合（Set）？查询、连接的时间复杂度都是：O(n)并查集能够办到查询、连接的均摊时间复杂度都是 O(α(n)) ，α(n...…
-
【进阶】5、排序（五）
目录 计数排序（Counting Sort） 基数排序（Radix Sort） 桶排序（Bucket Sort）计数排序（Counting Sort）一、计数排序之前学习的冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序 平均时间复杂度目前最低是 O(nlogn)计数排序、桶排序、基数排序，都不是基于比较的排序 它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比 O nlogn 更低 计数排序于1954年由Harold H. Seward...…
-
【进阶】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 替代...…
