-
【进阶】17、动态规划
目录 动态规划（Dynamic Programming） 找零钱动态规划（Dynamic Programming）动态规划，简称DP 是求解最优化问题的一种常用策略 通常的使用套路（一步一步优化） ① 暴力递归（自顶向下，出现了重叠子问题） ② 记忆化搜索（自顶向下） ③ 递推（自底向上）找零钱假设有25分、20分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少？ 此前用贪心策略得到的并非是最优解（贪心得到的解是 5 枚硬币）假...…
-
【进阶】16、贪心、分治
目录 贪心(Greedy) 分治(Divide And Conquer) 大数乘法贪心(Greedy)一、贪心贪心策略，也称为贪婪策略 每一步都采取当前状态下最优的选择（局部最优解），从而希望推导出全局最优解贪心的应用 哈夫曼树 最小生成树算法：Prim、Kruskal 最短路径算法：Dijkstra二、最优装载问题（加勒比海盗）在北美洲东南部，有一片神秘的海域，是海盗最活跃的加勒比海 有一天，海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一旦打碎就失...…
-
【进阶】15、回溯(Back Tracking)
目录 回溯 八皇后问题(Eight Queens) 八皇后问题代码实现回溯回溯可以理解为：通过选择不同的岔路口来通往目的地（找到想要的结果） 每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试 树、图的深度优先搜索（DFS）、八皇后、走迷宫都是典型的回溯应用不难看出来，回溯很适合使用递归八皇后问题(Eight Queens)一、问题八皇后问题是一个古老而著名的问题 在8x8格的国际象棋上摆放八个皇后，使其不能互相攻击：任意两个皇后都不能处于同一行、同...…
-
【进阶】14、递归(二 Recursion)
目录 上楼梯 汉诺塔（Hanoi） 递归转非递归 尾调用上楼梯楼梯有 n 阶台阶，上楼可以一步上 1 阶，也可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法？假设 n 阶台阶有 f(n) 种走法，第 1 步有 2 种走法 ✓ 如果上 1 阶，那就还剩 n – 1 阶，共 f(n – 1) 种走法 ✓ 如果上 2 阶，那就还剩 n – 2 阶，共 f(n – 2) 种走法所以 f(n) = f(n – 1) + f(n – 2)/// 上n阶楼梯有多少种走法/// @para...…
-
【进阶】13、递归(Recursion)
目录 递归介绍 递归思想 斐波那契数列递归介绍一、递归现象从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？【从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？『从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……』】GNU 是 GNU is Not Unix 的缩写 GNU → GNU is Not Unix → GNU is Not Unix is Not Unix → GNU is Not ...…
-
【进阶】12、图（六）
目录 Bellman-Ford FloydBellman-Ford一、算法原理Bellman-Ford 也属于单源最短路径算法，支持负权边，还能检测出是否有负权环 算法原理：对所有的边进行 V – 1 次松弛操作（ V 是节点数量），得到所有可能的最短路径 时间复杂度：O(EV) ，E 是边数量，V 是节点数量下图的最好情况是恰好从左到右的顺序对边进行松弛操作 对所有边仅需进行 1 次松弛操作就能计算出A到达其他所有顶点的最短路径最坏情况是恰好每次都从右到左的顺序对...…
-
【进阶】11、图（五）
目录 最短路径（Shortest Path） Dijkstra（迪杰斯特拉算法）最短路径（Shortest Path）一、有权图最短路径是指两顶点之间权值之和最小的路径（有向图、无向图均适用，不能有负权环）二、无权图无权图相当于是全部边权值为1的有权图三、负权边有负权边，但没有负权环时，存在最短路径A到E的最短路径是：A → B → E四、负权环有负权环时，不存在最短路径通过负权环， A到E的路径可以无限短 A → E → D → F → E → D → F →E → D → F ...…
-
【进阶】10、图（四）
目录 生成树（Spanning Tree） 切分定理 Prim算法 Kruskal算法生成树（Spanning Tree）一、生成树（Spanning Tree），也称为支撑树连通图的极小连通子图，它含有图中全部的 n 个顶点，恰好只有 n – 1 条边二、最小生成树（Minimum Spanning Tree）最小生成树（Minimum Spanning Tree，简称MST） 也称为最小权重生成树（Minimum Weight Spanning Tree）、最小支撑树 是所...…
-
【进阶】9、图（三）
目录 遍历 广度优先搜索BFS（Breadth First Search） 深度优先搜索DFS（Depth First Search） AOV网（Activity On Vertex Network） 拓扑排序（Topological Sort）遍历图的遍历从图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次图有2种常见的遍历方式（有向图、无向图都适用）广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索深度优先搜索（Dept...…
-
【进阶】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 ...…
