-
【基础】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、首次添加 */ /...…
-
【基础】4、链表（二）
目录 虚拟头节点 动态数组的缩容 双向链表 复杂度分析虚拟头节点有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点（不存储数据）增加虚拟头结点后需要改动的方法 //初始化时创建虚拟头结点-(instancetype)init{ self = [super init]; if (self) { _first = [LCNode nodeWithElement:nil next:nil]; } return self...…
-
【基础】3、链表（一）
目录 链表 链表实现动态数组 算法训练链表一、简介动态数组有个明显的缺点 可能会造成内存空间的大量浪费 能否用到多少就申请多少内存？链表可以办到这一点 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的二、链表的设计链表实现动态数组LCLinkArray.h文件#import <Foundation/Foundation.h>#import "LCArray.h"NS_ASSUME_NONNULL_BEGIN@interface LCLinkArray : ...…
-
【基础】2、动态数组
目录 什么是数据结构 线性表 自实现动态数组什么是数据结构数据结构是计算机存储、组织数据的方式在实际应用中，根据使用场景来选择最合适的数据结构一、线性结构线性表（数组、链表、栈、队列、哈希表）二、树形结构二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集三、图形结构邻接矩阵、邻接表线性表线性表是具有 n 个相同类型元素的有限序列（ n ≥ 0 ）a1 是首节点（首元素）， an 是尾结点（尾元素）a1 是 a2 的前驱， a2 是 a1 的后继常见的线性表有 数组 链...…
-
【基础】1、复杂度
目录 什么是算法 斐波那契数列 大O表示法 fib函数复杂度分析 算法的优化方向什么是算法算法是用于解决特定问题的一系列的执行步骤比如：//计算a跟b的和-(int)plustWithA:(int)a b:(int)b{ return a+b;}//计算 1+2+3+...n的和-(int)sumWithN:(int)n{ int result = 0; for (int i=1; i<=n; i++) { result += i; }...…
-
Git常用操作
目录 tag相关操作 远程仓库(未初始化)关联本地仓库 远程仓库(已初始化)关联本地仓库tag相关操作 操作 命令 说明 创建标签 git tag <tag_name> <commit_hash> 创建一个轻量标签（无附加信息），指向指定的commit。 查看所有标签 git tag 列出所有本地标签（按字母顺序）。 ...…
-
场景
目录 合并冲突 回滚场景合并冲突有一个共有的开发分支dev 有一个自己的业务分支lxy_develop平时我们自己的业务在自己的业务分支进行开发，如果有需要可以随时将dev的分支合并到lxy_develop 这样做的好处是： 1、实时保证自己的代码具有最新的功能，比如同事添加的好用的工具类 2、可以随时解决可能得冲突，而不至于等到最后集中到一块解决，容易产生错误在最后将lxy_develop合并到dev之前，做一次dev合并到lxy_develop的操作，目的是解决最后可能得...…
-
SSH配置
参考：Generating a new SSH key and adding it to the ssh-agent目录 SSH配置 如果有多个github账号怎么配置 错误收集目前github已经不允许使用账号密码的方式来拉取和提交代码了。可以使用下面两种方式：一种方式是使用SSH的方式来拉取和获取一种方式是可以使用令牌来拉取和获取SSH配置第一步：在本地创建一对公私钥ssh-keygen -t rsa -b 4096 -C "your_email@example.com"创建完成...…
