南京iOS培训分享Swift 算法实战之路（二）

　　上次南京万和iOS培训讲解了基本的语法和一些Swift的小技巧。今天我们来看几个最基本的数据结构：数组，字符串，集合和字典。

　　数组

　　数组是最基本的数据结构。Swift中改变了以前Objective-C时代NSMutableArray和NSArray分开的做法，统一到了Array唯一的数据结构。下面是最基本的一些实现。

　　不要小看这些简单的操作：数组可以依靠它们实现更多的数据结构。Swift虽然不像Java中有现成的队列和栈，但我们完全可以用数组配合最简单的操作实现这些数据结构，下面就是用数组实现栈的示例代码。

　　集合和字典

　　这两个数据结构经常使用的原因在于，查找数据的时间复杂度为O(1)。这两个在实战中经常与数组配合使用，请看下面这道题：

　　这道题是传说中经典的2Sum，我们已经有一个数组记为nums，也有一个目标值记为target，最后要返回一个Bool值。

　　最粗暴的方法就是每次选中一个数，然后遍历整个数组，判断是否有另一个数使两者之和为target。这种做法时间复杂度为O(n^2)。  有疑惑？请咨询南京万和iOS培训。

　　采用集合可以优化时间复杂度。在遍历数组的过程中，用集合每次保存当前值。假如集合中已经有了目标值减去当前值，则证明在之前的遍历中一定有一个数与当前值之和等于目标值。这种做法时间复杂度为O(n)，代码如下。

　　如果把题目稍微修改下，变为

　　思路与上题基本类似，但是为了方便拿到序列号，我们采用字典，时间复杂度依然是O(n)。代码如下。

　　字符串

　　字符串在算法实战中极其常见。首先南京万和iOS培训还是列举一下字符串的通常用法。

　　下面是本篇的精华所在，请跟南京万和iOS培训一起来看一道以前的Google面试题。

　　这道题目一看好简单，不就是翻转字符串的翻版吗？这种方法有以下两个问题

　　◎每个单词长度不一样

　　◎空格需要特殊处理

　　这样一来代码写起来会很繁琐而且容易出错。不如我们先实现一个字符串翻转的方法。

　　有了这个方法，我们就可以实行下面两种字符串翻转：更多详细内容，请咨询南京万和iOS培训。

　　整个字符串翻转，”the sky is blue” -> “eulb si yks eht”

　　每个单词作为一个字符串单独翻转，”eulb si yks eht” -> “blue is sky the”

　　整体思路有了，我们就可以解决这道问题了

　　时间复杂度还是O(n)，整体思路和代码简单很多。

　　总结

　　Swift中数组、字符串、集合以及字典是最基本的数据结构，但是围绕这些数据结构的问题层出不穷。幸运的是解决方法也并不是千变万化、高深莫测，大家做好相应的积累即可。下期南京万和iOS培训和大家讲链表、栈、队列这三种数据结构。