Swift 算法实战之路(二)

 

上次讲解了基本的语法和一些Swift的小技巧。今天我们来看几个最基本的数据结构:数组,字符串,集合和字典。

数组

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

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

集合和字典

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

给一个整型数组和一个目标值,判断数组中是否有两个数字之和等于目标值

这道题是传说中经典的2Sum,我们已经有一个数组记为nums,也有一个目标值记为target,最后要返回一个Bool值。
最粗暴的方法就是每次选中一个数,然后遍历整个数组,判断是否有另一个数使两者之和为target。这种做法时间复杂度为O(n^2)。
采用集合可以优化时间复杂度。在遍历数组的过程中,用集合每次保存当前值。假如集合中已经有了目标值减去当前值,则证明在之前的遍历中一定有一个数与当前值之和等于目标值。这种做法时间复杂度为O(n),代码如下。

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

给定一个整型数组中有且仅有两个数字之和等于目标值,求两个数字在数组中的序号

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

字符串

字符串在算法实战中极其常见。首先还是列举一下字符串的通常用法。

下面是本篇的精华所在,我们来一起看一道以前的Google面试题。

Given an input string, reverse the string word by word.
A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = “the sky is blue”,
return “blue is sky the”.
Could you do it in-place without allocating extra space?

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

  • 每个单词长度不一样
  • 空格需要特殊处理

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

有了这个方法,我们就可以实行下面两种字符串翻转:

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

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

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

总结

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

1 1 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部