本章为算法部分,作为对程序员基本功的考察,算法几乎是所有公司、各种水平的程序员都要面对的必考内容。该部分采用 Swift 语言重新审视了多种数据结构和算法原理,可以说是为 iOS 开发者量身打造的算法解答。
数组是最基本的数据结构。在 Swift 中,以前 Objective-C 时代中将 NSMutableArray 和 NSArray 分开的做法,被统一到了唯一的数据结构 —— Array 。虽然看上去就一种数据结构,其实它的实现有三种:
- ContiguousArray:效率最高,元素分配在连续的内存上。如果数组是值类型(栈上操作),则 Swift 会自动调用 Array 的这种实现;如果注重效率,推荐声明这种类型,尤其是在大量元素是类时,这样做效果会很好。
- Array:会自动桥接到 Objective-C 中的 NSArray 上,如果是值类型,其性能与 ContiguousArray 无差别。
- ArraySlice:它不是一个新的数组,只是一个片段,在内存上与原数组享用同一区域。
下面是数组最基本的一些运用。
// 声明一个不可修改的数组
let nums = [1, 2, 3]
let nums = [Int](repeating: 0, count: 5)
// 声明一个可以修改的数组
var nums = [3, 1, 2]
// 增加一个元素
nums.append(4)
// 对原数组进行升序排序
nums.sort()
// 对原数组进行降序排序
nums.sort(by: >)
// 将原数组除了最后一个以外的所有元素赋值给另一个数组
// 注意:nums[0..<nums.count - 1] 返回的是 ArraySlice,不是 Array
let anotherNums = Array(nums[0 ..< nums.count - 1])
不要小看这些简单的操作:数组可以依靠它们实现更多的数据结构。Swift 虽然不像 Java 中有现成的队列和栈,但我们完全可以用数组配合最简单的操作实现这些数据结构,下面就是用数组实现栈的示例代码。
// 用数组实现栈
struct Stack<Element> {
private var stack: [Element]
var isEmpty: Bool { return stack.isEmpty }
var peek: AnyObject? { return stack.last }
init() {
stack = [Element]()
}
mutating func push(_ element: Element) {
stack.append(object)
}
mutating func pop() -> Element? {
return stack.popLast()
}
}
// 初始化一个栈
let stack = Stack<String>()
最后特别强调一个操作:reserveCapacity()
。它用于为原数组预留空间,防止数组在增加和删除元素时反复申请内存空间或是创建新数组,特别适用于创建和 removeAll() 时候进行调用,为整段代码起到提高性能的作用。
字典和集合(这里专指HashSet)经常被使用的原因在于,查找数据的时间复杂度为 O(1)。 一般字典和集合要求它们的 Key 都必须遵守 Hashable 协议,Cocoa 中的基本数据类型都 满足这一点;自定义的 class 需要实现 Hashable,而又因为 Hashable 是对 Equable 的扩展, 所以还要重载 == 运算符。
下面是关于字典和集合的一些实用操作:
let primeNums: Set = [3, 5, 7, 11, 13]
let oddNums: Set = [1, 3, 5, 7, 9]
// 交集、并集、差集
let primeAndOddNum = primeNums.intersection(oddNums)
let primeOrOddNum = primeNums.union(oddNums)
let oddNotPrimNum = oddNums.subtracting(primeNums)
// 用字典和高阶函数计算字符串中每个字符的出现频率,结果 [“h”:1, “e”:1, “l”:2, “o”:1]
Dictionary("hello".map { ($0, 1) }, uniquingKeysWith: +)
集合和字典在实战中经常与数组配合使用,请看下面这道算法题:
给一个整型数组和一个目标值,判断数组中是否有两个数字之和等于目标值
这道题是传说中经典的 “2Sum”,我们已经有一个数组记为 nums,也有一个目标值记为 target,最后要返回一个 Bool 值。
最粗暴的方法就是每次选中一个数,然后遍历整个数组,判断是否有另一个数使两者之和为 target。这种做法时间复杂度为 O(n^2)。
采用集合可以优化时间复杂度。在遍历数组的过程中,用集合每次保存当前值。假如集合中已经有了目标值减去当前值,则证明在之前的遍历中一定有一个数与当前值之和等于目标值。这种做法时间复杂度为 O(n),代码如下。
func twoSum(nums: [Int], _ target: Int) -> Bool {
var set = Set<Int>()
for num in nums {
if set.contains(target - num) {
return true
}
set.insert(num)
}
return false
}
如果把题目稍微修改下,变为
给定一个整型数组中有且仅有两个数字之和等于目标值,求两个数字在数组中的序号
思路与上题基本类似,但是为了方便拿到序列号,我们采用字典,时间复杂度依然是 O(n)。代码如下。
func twoSum(nums: [Int], _ target: Int) -> [Int] {
var dict = [Int: Int]()
for (i, num) in nums.enumerated() {
if let lastIndex = dict[target - num] {
return [lastIndex, i]
} else {
dict[num] = i
}
}
fatalError("No valid output!")
}
字符串在算法实战中极其常见。在 Swift 中,字符串不同于其他语言(包括 Objective-C),它是值类型而非引用类型,它是多个字符构成的序列(并非数组)。首先还是列举一下字符串的通常用法。
// 字符串和数字之间的转换
let str = "3"
let num = Int(str)
let number = 3
let string = String(num)
// 字符串长度
let len = str.count
// 访问字符串中的单个字符,时间复杂度为O(1)
let char = str[str.index(str.startIndex, offsetBy: n)]
// 修改字符串
str.remove(at: n)
str.append("c")
str += "hello world"
// 检测字符串是否是由数字构成
func isStrNum(str: String) -> Bool {
return Int(str) != nil
}
// 将字符串按字母排序(不考虑大小写)
func sortStr(str: String) -> String {
return String(str.sorted())
}
// 判断字符是否为字母
char.isLetter
// 判断字符是否为数字
char.isNumber
// 得到字符的 ASCII 数值
char.asciiValue
关于字符串,我们来一起看一道以前的 Google 面试题。
给一个字符串,将其按照单词顺序进行反转。比如说 s 是 "the sky is blue", 那么反转就是 "blue is sky the"。
这道题目一看好简单,不就是反转字符串的翻版吗?这种方法有以下两个问题
- 每个单词长度不一样
- 空格需要特殊处理 这样一来代码写起来会很繁琐而且容易出错。不如我们先实现一个字符串翻转的方法。
fileprivate func reverse<T>(_ chars: inout [T], _ start: Int, _ end: Int) {
var start = start, end = end
while start < end {
swap(&chars, start, end)
start += 1
end -= 1
}
}
fileprivate func swap<T>(_ chars: inout [T], _ p: Int, _ q: Int) {
(chars[p], chars[q]) = (chars[q], chars[p])
}
有了这个方法,我们就可以实行下面两种字符串翻转:
- 整个字符串翻转,"the sky is blue" -> "eulb si yks eht"
- 每个单词作为一个字符串单独翻转,"eulb si yks eht" -> "blue is sky the" 整体思路有了,我们就可以解决这道问题了
func reverseWords(s: String?) -> String? {
guard let s = s else {
return nil
}
var chars = Array(s), start = 0
reverse(&chars, 0, chars.count - 1)
for i in 0 ..< chars.count {
if i == chars.count - 1 || chars[i + 1] == " " {
reverse(&chars, start, i)
start = i + 2
}
}
return String(chars)
}
时间复杂度还是 O(n),整体思路和代码简单很多。
在 Swift 中,数组、字符串、集合以及字典是最基本的数据结构,但是围绕这些数据结构的问题层出不穷。而在日常开发中,它们使用起来也非常高效(栈上运行)和安全(无需顾虑线程问题),因为他们都是值类型。
本节我们一起来探讨用 Swift 如何实现链表以及链表相关的技巧。
对于链表的概念,实在是基本概念太多,这里不做赘述。我们直接来实现链表节点。
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
}
}
有了节点,就可以实现链表了。
class LinkedList {
var head: ListNode?
var tail: ListNode?
// 头插法
func appendToHead(_ val: Int) {
let node = ListNode(val)
if let _ = head {
node.next = head
} else {
tail = node
}
head = node
}
// 头插法
func appendToTail(_ val: Int) {
let node = ListNode(val)
if let _ = tail {
tail!.next = node
} else {
head = node
}
tail = node
}
}
有了上面的基本操作,我们来看如何解决复杂的问题。
话不多说,我们直接先来看下面一道题目。
给一个链表和一个值 x,要求将链表中所有小于 x 的值放到左边,所有大于等于 x 的值放到右边。原链表的节点顺序不能变。
例:1->5->3->2->4->2,给定x = 3。则我们要返回1->2->2->5->3->4
直觉告诉我们,这题要先处理左边(比 x 小的节点),然后再处理右边(比 x 大的节点),最后再把左右两边拼起来。
思路有了,再把题目抽象一下,就是要实现这样一个函数:
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {}
即我们有给定链表的头节点,有给定的x值,要求返回新链表的头结点。接下来我们要想:怎么处理左边?怎么处理右边?处理完后怎么拼接?
先来看怎么处理左边。我们不妨把这个题目先变简单一点:
给一个链表和一个值 x,要求只保留链表中所有小于 x 的值,原链表的节点顺序不能变。
例:1->5->3->2->4->2,给定x = 3。则我们要返回 1->2->2
我们只要采用尾插法,遍历链表,将小于 x 值的节点接入新的链表即可。代码如下:
func getLeftList(_ head: ListNode?, _ x: Int) -> ListNode? {
let dummy = ListNode(0)
var pre = dummy, node = head
while node != nil {
if node!.val < x {
pre.next = node
pre = node!
}
node = node!.next
}
// 防止构成环
pre.next = nil
return dummy.next
}
注意,上面的代码我们引入了 Dummy 节点,它的作用就是作为一个虚拟的头前结点。我们引入它的原因是我们不知道要返回的新链表的头结点是哪一个,它有可能是原链表的第一个节点,可能在原链表的中间,也可能在最后,甚至可能不存在(nil)。而 Dummy 节点的引入可以巧妙的涵盖所有以上情况,我们可以用
dummy.next
方便得返回最终需要的头结点。
现在我们解决了左边,右边也是同样处理。接着只要让左边的尾节点指向右边的头结点即可。全部代码如下:
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
// 引入Dummy节点
let prevDummy = ListNode(0), postDummy = ListNode(0)
var prev = prevDummy, post = postDummy
var node = head
// 用尾插法处理左边和右边
while node != nil {
if node!.val < x {
prev.next = node
prev = node!
} else {
post.next = node
post = node!
}
node = node!.next
}
// 防止构成环
post.next = nil
// 左右拼接
prev.next = postDummy.next
return prevDummy.next
}
注意这句 post.next = nil
,这是为了防止链表循环指向构成环,是必须的但是很容易忽略的一步。
刚才我们提到了环,那么怎么检测链表中是否有环存在呢?
笔者理解快行指针,就是两个指针访问链表,一个在前一个在后,或者一个移动快另一个移动慢,这就是快行指针。来看一道简单的面试题:
如何检测一个链表中是否有环?
答案是用两个指针同时访问链表,其中一个的速度是另一个的 2 倍,如果他们相等了,那么这个链表就有环了,这就是快行指针的实际使用。代码如下:
func hasCycle(_ head: ListNode?) -> Bool {
var slow = head
var fast = head
while fast != nil && fast!.next != nil {
slow = slow!.next
fast = fast!.next!.next
if slow === fast {
return true
}
}
return false
}
再举一个快行指针一前一后的例子,看下面这道题。
删除链表中倒数第 n 个节点。例:1->2->3->4->5,n = 2。返回1->2->3->5。 注意:给定 n 的长度小于等于链表的长度。
解题思路依然是快行指针,这次两个指针移动速度相同。但是一开始,第一个指针(指向头结点之前)就落后第二个指针 n 个节点。接着两者同时移动,当第二个移动到尾节点时,第一个节点的下一个节点就是我们要删除的节点。代码如下:
func removeNthFromEnd(head: ListNode?, _ n: Int) -> ListNode? {
guard let head = head else {
return nil
}
let dummy = ListNode(0)
dummy.next = head
var prev: ListNode? = dummy
var post: ListNode? = dummy
// 设置后一个节点初始位置
for _ in 0 ..< n {
if post == nil {
break
}
post = post!.next
}
// 同时移动前后节点
while post != nil && post!.next != nil {
prev = prev!.next
post = post!.next
}
// 删除节点
prev!.next = prev!.next!.next
return dummy.next
}
这里还用到了 Dummy 节点,因为有可能我们要删除的是头结点。
这次我们用 Swift 实现了链表的基本结构,并且实战了链表的几个技巧。在结尾处,我还想强调一下 Swift 处理链表问题的两个细节问题:
- 一定要注意头结点可能就是 nil。所以给定链表,我们要看清楚 head 是不是 optional,在判断是不是要处理这种边界条件。
- 注意每个节点的 next 可能是 nil。如果不为 nil,请用"!"修饰变量。在赋值的时候,也请注意"!"将 optional 节点传给非 optional 节点的情况。
这期我们来讨论一下栈和队列。在 Swift 中,没有内设的栈和队列,很多扩展库中使用 Generic Type 来实现栈或是队列。正规的做法使用链表来实现,这样可以保证加入和删除的时间复杂度是 O(1)。然而笔者觉得最实用的实现方法是使用数组,因为 Swift 没有现成的链表,而数组又有很多的 API 可以直接使用,非常方便。
对于栈来说,我们需要了解以下几点:
- 栈是后进先出的结构。你可以理解成有好几个盘子要垒成一叠,哪个盘子最后叠上去,下次使用的时候它就最先被抽出去。
- 在 iOS 开发中,如果你要在你的 App 中添加撤销操作(比如删除图片,恢复删除图片),那么栈是首选数据结构
- 无论在面试还是写 App 中,只关注栈的这几个基本操作:push, pop, isEmpty, peek, size。
protocol Stack {
/// 持有的元素类型
associatedtype Element
/// 是否为空
var isEmpty: Bool { get }
/// 栈的大小
var size: Int { get }
/// 栈顶元素
var peek: Element? { get }
/// 进栈
mutating func push(_ newElement: Element)
/// 出栈
mutating func pop() -> Element?
}
struct IntegerStack: Stack {
typealias Element = Int
var isEmpty: Bool { return stack.isEmpty }
var size: Int { return stack.count }
var peek: Element? { return stack.last }
private var stack = [Element]()
mutating func push(_ newElement: Element) {
stack.append(newElement)
}
mutating func pop() -> Element? {
return stack.popLast()
}
}
对于队列来说,我们需要了解以下几点:
- 队列是先进先出的结构。这个正好就像现实生活中排队买票,谁先来排队,谁先买到票。
- iOS 开发中多线程的 GCD 和 NSOperationQueue 就是基于队列实现的。
- 关于队列我们只关注这几个操作:enqueue, dequeue, isEmpty, peek, size。
protocol Queue {
/// 持有的元素类型
associatedtype Element
/// 是否为空
var isEmpty: Bool { get }
/// 队列的大小
var size: Int { get }
/// 队首元素
var peek: Element? { get }
/// 入队
mutating func enqueue(_ newElement: Element)
/// 出队
mutating func dequeue() -> Element?
}
struct IntegerQueue: Queue {
typealias Element = Int
var isEmpty: Bool { return left.isEmpty && right.isEmpty }
var size: Int { return left.count + right.count }
var peek: Element? { return left.isEmpty ? right.first : left.last }
private var left = [Element]()
private var right = [Element]()
mutating func enqueue(_ newElement: Element) {
right.append(newElement)
}
mutating func dequeue() -> Element? {
if left.isEmpty {
left = right.reversed()
right.removeAll()
}
return left.popLast()
}
}
处理栈和队列问题,最经典的一个思路就是使用两个栈/队列来解决问题。也就是说在原栈/队列的基础上,我们用一个协助栈/队列来帮助我们简化算法,这是一种空间换时间的思路。下面是示例代码:
// 用栈实现队列
struct MyQueue {
var stackA: Stack
var stackB: Stack
var isEmpty: Bool {
return stackA.isEmpty
}
var peek: Any? {
get {
shift()
return stackB.peek
}
}
var size: Int {
get {
return stackA.size + stackB.size
}
}
init() {
stackA = Stack()
stackB = Stack()
}
func enqueue(object: Any) {
stackA.push(object);
}
func dequeue() -> Any? {
shift()
return stackB.pop();
}
fileprivate func shift() {
if stackB.isEmpty {
while !stackA.isEmpty {
stackB.push(stackA.pop()!);
}
}
}
}
// 用队列实现栈
struct MyStack {
var queueA: Queue
var queueB: Queue
init() {
queueA = Queue()
queueB = Queue()
}
var isEmpty: Bool {
return queueA.isEmpty
}
var peek: Any? {
get {
if isEmpty {
return nil
}
shift()
let peekObj = queueA.peek
queueB.enqueue(queueA.dequeue()!)
swap()
return peekObj
}
}
var size: Int {
return queueA.size
}
func push(object: Any) {
queueA.enqueue(object)
}
func pop() -> Any? {
if isEmpty {
return nil
}
shift()
let popObject = queueA.dequeue()
swap()
return popObject
}
private func shift() {
while queueA.size > 1 {
queueB.enqueue(queueA.dequeue()!)
}
}
private func swap() {
(queueA, queueB) = (queueB, queueA)
}
}
上面两种实现方法都是使用两个相同的数据结构,然后将元素由其中一个转向另一个,从而形成一种完全不同的数据。
给一个文件的绝对路径,将其简化。举个例子,路径是 "/home/",简化后为 "/home";路径是"/a/./b/../../c/",简化后为 "/c"。
这是一道 Facebook 的面试题。这道题目其实就是平常在终端里面敲的 cd、pwd 等基本命令所得到的路径。
根据常识,我们知道以下规则:
- “. ” 代表当前路径。比如 “ /a/. ” 实际上就是 “/a”,无论输入多少个 “ . ” 都返回当前目录
- “..”代表上一级目录。比如 “/a/b/.. ” 实际上就是 “ /a”,也就是说先进入 “a” 目录,再进入其下的 “b” 目录,再返回 “b” 目录的上一层,也就是 “a” 目录。
然后针对以上信息,我们可以得出以下思路:
- 首先输入是个 String,代表路径。输出要求也是 String, 同样代表路径;
- 我们可以把 input 根据 “/” 符号去拆分,比如 "/a/b/./../d/" 就拆成了一个String数组["a", "b", ".", "..", "d"];
- 创立一个栈然后遍历拆分后的 String 数组,对于一般 String ,直接加入到栈中,对于 ".." 那我们就对栈做 pop 操作,其他情况不错处理。
思路有了,代码也就有了
func simplifyPath(path: String) -> String {
// 用数组来实现栈的功能
var pathStack = [String]()
// 拆分原路径
let paths = path.split(separatedBy: "/")
for path in paths {
// 对于 "." 我们直接跳过
guard path != "." else {
continue
}
// 对于 ".." 我们使用pop操作
if path == ".." {
if (!pathStack.isEmpty) {
pathStack.removeLast()
}
// 对于太注意空数组的特殊情况
} else if path != "" {
pathStack.append(path)
}
}
// 将栈中的内容转化为优化后的新路径
return "/" + pathStack.joined(separator: "/")
}
上面代码除了完成了基本思路,还考虑了大量的特殊情况、异常情况。这也是硅谷面试考察的一个方面:面试者思路的严谨,对边界条件的充分考虑,以及代码的风格规范。
在 Swift 中,栈和队列是比较特殊的数据结构,笔者认为最实用的实现和运用方法是利用数组。虽然它们本身比较抽象,却是很多复杂数据结构和 iOS 开发中的功能模块的基础。这也是一个工程师进阶之路理应熟练掌握的两种数据结构。
如果你想一起进阶,不妨添加一下交流群931 542 608