注册

iOS 面试策略之算法基础1-3节

1. 基本数据结构


数组


数组是最基本的数据结构。在 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 中，数组、字符串、集合以及字典是最基本的数据结构，但是围绕这些数据结构的问题层出不穷。而在日常开发中，它们使用起来也非常高效（栈上运行）和安全（无需顾虑线程问题），因为他们都是值类型。


2. 链表


本节我们一起来探讨用 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

  }

}


有了上面的基本操作，我们来看如何解决复杂的问题。


Dummy 节点和尾插法


话不多说，我们直接先来看下面一道题目。


给一个链表和一个值 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 节点的情况。


3. 栈和队列


这期我们来讨论一下栈和队列。在 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” 目录。


然后针对以上信息，我们可以得出以下思路：


  1. 首先输入是个 String，代表路径。输出要求也是 String, 同样代表路径；
  2. 我们可以把 input 根据 “/” 符号去拆分，比如 "/a/b/./../d/" 就拆成了一个String数组["a", "b", ".", "..", "d"]；
  1. 创立一个栈然后遍历拆分后的 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 开发中的功能模块的基础。这也是一个工程师进阶之路理应熟练掌握的两种数据结构。

0
分享
2021-11-24

0 个评论

要回复文章请先登录或注册

一个开放、互助、协作、创意的社区

关于imGeek
关于专职工程师值守
社区财富榜
赞助商
友情链接
热门标签
京ICP备2023000793号