【数据结构与算法】系列三十 - 图(广度/深度优先搜索)
邻接矩阵实现起来特别繁琐,而且没有通用性(适合稠密图),所以本章节以类似邻接表的方式(不是完全的邻接表,但比邻接表灵活)实现图(有向图可以表示无向图)。
【数据结构与算法】系列二十八 - 并查集
假设有n个村庄,有些村庄之间有连接的路,有些村庄之间并没有连接的路。
如下图,村庄6和村庄7与其他村庄都没有连接:
设计一个数据结构,能够快速执行2个操作:
- 查询2个村庄之间是否有连接的路
- 连接2个村庄(比如连接1和9,左边和右边的村庄都有路了)
使用数组、链表、平衡二叉树、集合可以执行上面的操作么?当然可以,只是效率会比较低(哈希集合可能效率会高一点,但是有点杀鸡用牛刀)。查询、连接的时间复杂度都是O(n)
。并查集能够办到查询、连接的均摊时间复杂度都是O(α(n)) ,α(n) < 5
,并查集非常适合解决这类“连接”相关的问题。
【iOS】Swift系列三十四 - 响应式编程(RxSwift的使用)
响应式编程(Reactive Programming,简称RP)也是一种编程范式,于1997年提出,可以简化异步编程,提供更优雅的数据绑定。
【CocoaPods】CDN trunk URL couldn’t be downloaded:https://raw.githubusercontent.com/CocoaPods/
首次遇到Pods的CDN
问题,后来才知道是1.8版本后CocoaPods
为了开发者更快速的体验,进行了CDN
加速处理,同时也让Podfile
更加规范了。
【数据结构与算法】系列二十七 - 计数/基数/桶排序
之前章节的冒泡、选择、插入、归并、快速、希尔、堆排序,都是基于比较的排序。平均时间复杂度目前最低是O(nlogn)
。
计数排序、桶排序、基数排序,都不是基于比较的排序。它们是典型的用空间换时间,在某些时候,平均时间复杂度可以比O(nlogn)
更低。
【iOS】Swift系列三十三 - 面向协议编程
面向协议编程(Protocol Oriented Programming,简称POP)是Swift的一种编程范式,Apple于2015年WWDC提出。在Swift的标准库中,能见到大量POP的影子。