algorithm

使用 Swift 语言实现数据结构与算法之美专栏代码 ，在原有基础上扩增了一些内容，原始代码 https://github.com/wangzheng0822/algo

一、目录结构

源代码在第一级目录所对应的文件夹下，测试工程以及测试代码在 Algorithm 目录下，可以直接使用 Xcode 打开工程文件 Algorithm.xcodeproj，选择对应的 Target 运行测试代码

二、数据结构内容

数组

• 实现一个支持动态扩容的数组
• 实现一个大小固定的有序数组，支持动态增删改操作
• 实现两个有序数组合并为一个有序数组

链表

• 实现单链表、循环链表、双向链表，支持增删操作
• 实现单链表反转
• 实现两个有序的链表合并为一个有序链表
• 实现求链表的中间结点
• 实现求链表的倒数第K个结点（快慢指针）
• 判断链表是否有环
• 链表有环的话，求链表环的入口位置

栈

• 用数组实现一个顺序栈
• 用链表实现一个链式栈
• 编程模拟实现一个浏览器的前进、后退功能

队列

• 用数组实现一个顺序队列
• 用链表实现一个链式队列
• 实现一个循环队列

递归

• 编程实现斐波那契数列求值 f(n) = f(n-1) + f(n-2)
• 编程实现求阶乘 n!
• 编程实现一组数据集合的全排列
• 台阶总共多少走法问题
• 递归常见问题

排序算法

• 冒泡排序、插入排序、希尔排序、选择排序
• 归并排序、快速排序
• 桶排序、计数排序、基数排序
• 堆排序
• 编程实现O(n)时间复杂度内找到一组数据的第K大元素

二分查找

• 实现一个有序数组的二分查找算法
• 实现一个数的平方根求解，要求精确到小数点后六位
• 实现模糊二分查找算法（比如大于等于给定值的第一个元素）
• 实现循环有序数组查找给定值

跳表

• 实现跳表

散列表

• 实现一个基于链表法解决冲突问题的散列表
• 实现一个LRU缓存淘汰算法

二叉树

• 实现一个二叉查找树，并且支持插入、删除、查找操作
• 实现查找二叉查找树中某个结点的后继、前驱结点
• 实现二叉树的前、中、后序以及按层遍历

堆

• 实现一个小顶堆、大顶堆、优先级队列
• 实现堆排序
• 利用优先级队列合并K个有序数组
• 求一组动态数据集合的最大Top K

图

• 实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法
• 实现图的深度优先搜索、广度优先搜索
• 实现图的最小生成树算法（Kruskal、Prime）
• 实现 Dijkstra 算法、A*算法
• 实现拓扑排序的 Kahn 算法、DFS 算法

字符串

• 实现朴素的字符串匹配算法
• 实现BM算法
• 实现KMP算法
• 实现一个字符集，只包含a~z这26个英文字母的Trie树

贪心算法

• 分糖果、钱币找零、区间覆盖
• 霍夫曼编码问题
• 非负整数中，移除K个数字，让剩下的数字值最小
• n个人等待服务问题，如何安排被服务的先后顺序，使 n 个人总的等待时间最短

分治算法

• 求一组数据的逆序对个数

回溯算法

• 利用回溯算法求解八皇后问题
• 利用回溯算法求解0-1背包问题

动态规划

• 0-1背包问题
• 最小路径和
• 编程实现莱文斯坦最短编辑距离
• 编程实现查找两个字符串的最长公共子序列
• 编程实现一个数据序列的最长递增子序列

三、LeetCode练习

数组和链表

• 三数之和
• 求众数
• 求缺失的第一个正数
• 环形链表
• 合并K个排序链表

栈、队列和递归

• 有效的括号
• 最长有效的括号
• 逆波兰表达式求值
• 设计一个双端队列
• 滑动窗口最大值
• 爬楼梯

排序和二分查找

散列表和字符串

二叉树和堆

图

贪心、分治、回溯和动态规划

更多 LeetCode 题解请点击

四、学习资源

1. 可视化工具

• VisuAlgo.net：数据结构与算法动态可视化网站，网站是由 Steven Halim 博士推行建立，初衷是为了帮助新加坡国立大学的学生们，更好的理解数据结构与算法，并进一步强化对各项知识点的吸收；
• 旧金山大学数据结构与算法可视化网站 ：见名知意，旧金山大学为学生提供的数据结构与算法在线可视化网站，可以直接在网页上面查看算法执行效果；

2. Swift 数据结构与算法

• swift-algorithm-club：raywenderlich 网站出品的 swift 数据结构与算法书籍答案，非常全面和具体。学习 iOS 的各位都十分清楚，raywenderlich 网站提供的知识非常靠谱，学起来准没错；
• SwiftAlgorithms：针对 swift-algorithm-club 编写的开源应用程序；

3. LeetCode 相关

• LeetCode-Swift：Swift 编写的 LeetCode 题解，强大；
• LeetCodeAnimation：图解 LeetCode 算法，使用 Java 语言编写；
• LeetCode刷题指南: 完整的刷题计划，帮助大家少走弯路，循序渐进学算法；

4. 其它语言数据结构与算法

• 数据结构与算法博客：使用C、C++、Java 语言实现的常见数据结构与算法博客，原理讲的比较透彻，代码编写的比较经典，学习时可以参考下；
• algorithms：使用 Java 语言编写的 《剑指offer》题解；
• 《编程之法：面试与算法心得》：书籍配套代码，七月在线科技创始人兼 CEO，CSDN 超人气博客"结构之法算法之道"作者 July 编写，质量有保证，可参考学习；