《iOS面试之道》两篇总结之二：算法基础篇

《iOS 面试之道》是故胤道长和唐巧 2018 年合著的针对面试一些问题的书，买之后虽有翻阅，但是始终未认真通读。现在想把书中对于我来说有价值的知识点，简短的总结一下。这里分两篇来说，这篇主要是介绍一些算法基础。

《iOS 面试之道》两篇总结之一：开发技能篇

《iOS 面试之道》两篇总结之二：算法基础篇

# 基本的数据结构

# 数组

• ContiguousArray: 效率最高，元素分配在连续的内存地址上。如果数组元素是值类型，Swift 自动调用这种实现。处理大量元素时，推荐这种方式。
• Array: 自动桥接到 Objective-C 的 NSArray 上，如果元素时值类型，与 ContiguousArray 性能无差别。
• ArraySlice: 它不是一个新的数组，而只是一个片段，在内存上与数组享用同一区域。

下面用数组实现一个栈操作：

class Stack {
    var stack: [AnyObject]
    var isEmpty: Bool { return stack.isEmpty }
    var peel: AnyObject? { return stack.last }
    
    init() {
        stack = [AnyObject]()
    }
    
    func push(object: AnyObject) {
        stack.append(object)
    }
    
    func pop() -> AnyObject? {
        if !isEmpty {
            return stack.removeLast()
        } else {
            return nil
        }
    }
}

最后强调一个操作： reserveCapacity() 。用于为原数组预留空间，防止数组数组添加或删除元素时反复申请内存空间或创建新数组。再别在数组创建或者 removeAll() 时，对整段代码起到性能提升的作用。

# 字典和集合

一般字典和集合的 Key 都要遵循 Hashable 协议，自定义的类型作为 Key 实现 Hashable。这里说下集合的一些特点:

let primeNums: Set = [3, 5, 7, 11, 13]
let oddNums: Set = [1, 3, 5, 7, 9]
/// 交集、并集、差集
let primeAndOddNum = primeNums.intersection(oddNums)
var orNums = primeNums
orNums.formUnion(oddNums)
let primeNotOddNum = primeNums.subtracting(oddNums)

这里一个字典的例子非常有意思：

/*
* 用字典和高阶函数计算字符串中每个字符出现的频率。
* 结果为 ["l": 2, "h": 1, "o": 1, "e": 1]
*/ 
Dictionary("hello".map { ($0, 1)}, uniquingKeysWith: +)

算法题： 给出一个整型数组和一个目标值，判断数组中是否有两个数之和等于目标值。

可利用目标减去差值的方式，时间复杂度为 O(n)：

func twoNum(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 twoNum(nums: [Int], _ target: Int) -> [Int] {
    var dic = [Int: Int]()
    
    for (index, value) in nums.enumerated() {
        if let lastIndex = dic[target - value] {
            return [index, lastIndex]
        } else {
            dic[value] = index
        }
    }
}

# 字符串

# 给出一个字符串，要求其按照单词顺序进行反转

override func viewDidLoad() {
    super.viewDidLoad()
    print(reverseWords(s: "the sky     is      blue") ?? "None")
}

/// 按照单词反转字符串
private func reverseWords(s: String?) -> String? {
    guard let s = s else { return nil }
    var chars = s.map { $0 }
    reverse(&chars, 0, chars.count - 1)
    print(chars)
    var start = 0
    for i in 0 ..< chars.count {
        if i == chars.count - 1 || chars[i + 1] == " " {
            reverse(&chars, start, i)
            start = i + 2
        }
    }
    return String(chars)
}

/// 反转一个字符串
private func reverse<T>(_ chars: inout [T], _ start: Int, _ end: Int) {
    var start = start
    var end = end
    while start < end {
        swap(&chars, start, end)
        start += 1
        end -= 1
    }
}

/// 交换两个位置
private func swap<T>(_ chars: inout [T], _ p: Int, _ q: Int) {
    (chars[p], chars[q]) = (chars[q], chars[p])
}

输出：

["e", "u", "l", "b", " ", " ", " ", " ", " ", " ", "s", "i", " ", " ", " ", " ", " ", "y", "k", "s", " ", "e", "h", "t"]
Optional("blue      is     sky the")

# 链表

# 链表的基本概念

这里不再赘述链表基本概念，直接实现链表结点：

/// 链表节点
class ListNode {
    var val: Int
    var next: ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

/// 通过节点，实现链表
class List {
    var head: ListNode?
    var tail: ListNode?
    
    // 尾插发
    func appendToTail(_ val: Int) {
        if tail == nil {
            tail = ListNode(val)
            head = tail
        } else {
            tail?.next = ListNode(val)
            tail = tail?.next
        }
    }
    
    // 头插法
    func appendToHead(_ val: Int) {
        if head == nil {
            head = ListNode(val)
            tail = head
        } else {
            let temp = ListNode(val)
            temp.next = head
            head = temp
        }
    }
}

# Dummy 节点和尾插发

给出一个链表和一个值 x，要求将链表中所有小于 x 的值放左边，所有大于 x 的放右边，并且原始链表的节点顺序不变。

• Dummy 节点作用：它的作用就是作为一个虚拟的头结点。因为我们不知道要返回的新链表的节点是哪一个，甚至不知道是否存在。因为 Dummy 节点可以巧妙涵盖各种情况。可以用 dummy.next 方便的返回最终需要的头节点。

func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
    // 引入 Dummy 节点
    let prevDummy = ListNode(0)
    let 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
}

# 快行指针

快行指针用来检测链表是否有环。可以简单理解为：两个指针同时访问链表，但是移动速度不一样，如果存在环，跑的快的总有机会再次遇到跑的慢的。如果跑的快的到头了，还没见到跑的慢的，则不存在环，就好像操场跑步一样。代码如下：

func hadCycle(_ head: ListNode?) -> Bool {
    var slow = head
    var faster = head
    while faster != nil && faster?.next != nil {
        slow = slow?.next
        faster = faster?.next?.next
        
        if slow === faster {
            return true
        }
    }

    return false
}

注意这里用了三个等号。表示恒等。

下面使用快行指针解决一个问题：

删除链表中倒数第 n 个节点，例如：1 -> 2 -> 3 -> 4 -> 5，n = 2，返回 1 -> 2 -> 3 -> 5。给定 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
}

# 栈和队列

# 栈的基本概念

• 栈是后进先出的结构，即 FILO，first in last out。
• 如果 iOS 项目需要添加撤销操作，栈是首选的数据结构。使用数组实现更加方便。
• 无论面试还是写 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 IntergerStack: Stack {
    typealias Element = Int
    
    var isEmpty: Bool { return stacks.isEmpty }
    var size: Int { return stacks.count }
    var peek: Int? { return stacks.last }
    
    private var stacks = [Element]()
    
    mutating func push(_ newElement: Int) {
        stacks.append(newElement)
    }
    
    mutating func pop() -> Int? {
        return stacks.popLast()
    }
}

# 队列的基本概念

• 队列是先进先出的结构，即 FIFO，first in first out。
• iOS 开发中的多线程 GCD 以及 NSOperation 都是基于队列实现的。
• 关于队列只需要关注 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: Int? { return left.isEmpty ? right.first : left.last }
    
    private var left = [Element]()
    private var right = [Element]()
    
    mutating func enqueue(_ newElement: Int) {
        right.append(newElement)
    }
    
    mutating func dequeue() -> Int? {
        if left.isEmpty {
            left = right.reversed()
            right.removeAll()
        }
        return left.popLast()
    }
    
}

# 栈和队列实战面试题

给出一个文件的绝对路径，要求将其简化。如：

• 路径是 “/home/”，简化后为 “/home”。
• 路径是 “/a/./…/…/c”，简化后为 “/c”。

根据常识，有以下规则：

• “.” 代表当前路径。比如 “/a/.” 实际上就是 “/a”，无论输入多少个 “.”(除了 2 个)，都返回当前目录。
• “…” 代表上一级目录，比如 “a/b/…” 实际就是 “/a”。

实现代码如下：

func simplifyPath(path: String) -> String {
    // 用数组来实现栈的功能
    var pathStack = [String]()
    // 拆分原路径
    let paths = path.components(separatedBy: "/")
    
    for path in paths {
        print("path = \(path)")
        guard path != "." else {
            continue
        }
        
        // 对 .. 使用 pop 操作
        if path == ".." {
            if pathStack.count > 0 {
                pathStack.removeLast()
            } else {
                // 数组为空，上来就是 .. 则不操作
            }
        } else if path != "" {
            pathStack.append(path)
        } else {
            // 空路径，不用处理
        }
        

    }
    
    print("stacks = \(pathStack)")
    /// 将栈中的内容转化为优化后的新路径
    let res = pathStack.reduce("") { totol, dir in
        "\(totol)/\(dir)"}
    
    // 注意空路径的结果是 /
    return res.isEmpty ? "/" : res
}

# 二叉树