《iOS面试之道》算法基础学习(上)

道长和唐巧的面试之道,刚出来第一时间就入手了,也是趁着公司目前不是很忙,能好好静下心来细读这本书.这本书的一大亮点就在第二章的算法基础了,所以想通过笔记的形式来记录算法的学习过程,同时在忘记的时候也能第一时间翻阅查看.

这部分代码都是通过Swift来讲解的,所以对于想学习Swift的初学者来说也是不错的.在本章算法题笔者简单的分析了下,需要看详细的大家可以选择购买原书学习.

1 字典和集合:给出一个整型数组和一个目标值,判断数组中是否有两个数之和等于目标值.

这种题在LeetCode上其实挺多的,书上关于这题swift的代码也是比较简单.

func twoSum (nums: [Int], _ target: Int) -> Bool {
      //初始化集合
      var set = Set<Int>()
      //遍历整型数组
      for num in nums {
          //判断集合中是否包含目标值减去当前值的结果
          if set.contains(target - num) {
              //包含 返回true
              return true
          }
          //不包含 将当前值存进集合 用作下次判断
          set.insert(num)
      }
      //都不包含 返回fasle
      return false
  }
复制代码

这种方法的时间复杂度为 O(n) ,较选中一个数然后遍历整个数组这种复杂度为*O(n^2)*的方法要好很多.

1.2:在这道题的基础上做修改:给定一个整型数组中有且仅有 两个数之和等于目标值,求这两个数在数组中的序号.

书中的方法为了方便得到序列号,使用了字典,看代码

func twoSum (nums: [Int], _ target: Int) -> [Int] {
    //初始化字典
    var dict = [Int: Int]()
    //通过索引i 和对应的num进行判断
    for (i,num) in nums.enumerated() {
        //从dict字典中取出之前保存的索引,判断是否存在索引值
        if let lastIndex = dict[target - num] {
            //返回之前存的索引和当前索引
            return [lastIndex, i]
        }else {
            //保存当前索引,用于后续判断
            dict[num] = i
        }
    }
    //致命错误来中止程序
    fatalError("No valid output!")
}
复制代码

巧妙的用到了字典的特性,用key表示数组的值,通过判断字典中是否含有目标值的key来取出索引.

2 字符串:给出一个字符串,要求将其按照单词顺序进行反转.

eg:如果是"hello world",那么反转后的结果就是"world hello",这个题比较常规了,但是要注意空格的特殊处理.看代码:

fileprivate func _reverse<T>(_ chars: inout[T], _ start: Int, _ end: Int) {
    //接收字符串反转起始,结束位置
    var start = start, end = end
    //判断反转字符串的位置
    while start < end {
        //start end位置 字符互换
        swap(&chars, start, end)
        //往中间位置靠拢
        start += 1
        end -= 1
    }
}

fileprivate func swap<T>(_ chars: inout[T], _ p: Int, _ q: Int){
    //将p,q字符 位置进行互换  这种写法也是swift里的一大亮点
    (chars[p], chars[q]) = (chars[q], chars[p])
}
复制代码

上面方法是实现了字符串的反转,再来看下每个单词的单独反转.需要注意的是单词的反转需要对空格进行判断,来看完整实现代码.

func reverseWords(s: String?) -> String? {
    //判断入参s是否有值
    guard let s = s else {
        return nil
    }
    //将字符串s分割成字符数组
    var chars = Array(s.characters), start = 0
    //反转chars字符数组
    _reverse(&chars, start, chars.count - 1)
   
    for i in 0 ..< chars.count {
        //当i等于 数组最后一位 或者 遇到空格时反转字符串
        if i == chars.count - 1 || chars[i + 1] == " " {
            //将每个单独的单词进行反转
            _reverse(&chars, start, i)
            //更新start位置
            start = i + 2
        }
    }
    return String(chars)
}
复制代码

注解: 1:以输入字符串为"Hello World"为例,首先将该字符串分割成一个个的小字符数组,然后反转成 "dlroW olleH". 2“接着我们通过判断字符数组中的空格位和最后一位字符,对单一的单词进行分段反转,更新start位置. 3:最后输出我们需要的结果"World Hello"

其实字符串反转苹果已经为我们提供了方法来实现这个操作.

func reverseWords(s: String) -> String? {
    //用空格划分字符串
    let chars = s.components(separatedBy:" ")
    //将字符串数组 反转 并通过空格重新组合
    let reverseString = chars.reversed().joined(separator:" ")
    return reverseString
}
复制代码

写法非常的简单,就不赘述了.但是components和joined的时间复杂度是高于上面的写法的,需要注意.

3 链表

笔者理解的链表是一串在存储空间上非连续性、顺序的存储结构.由节点进行头尾依次连接而形成链表.每个结点有包括两个部分:数据域和下个节点的指针域.

接下来看下书中在swift里如何实现一个链表

1:生成节点

class ListNode {
    //数据域
    var val: Int
    //指针域
    var next: ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }     
}
复制代码

2:实现头插法和尾插法 头插法:当前节点插到第一个节点之前， 尾插法:当前节点插入到链表最后一个节点之后。

class List {
    
    var head: ListNode?
    var tail: ListNode?
    
    //头插法
    func appendToHead(_ val: Int) {
        
        if head == nil {
           //创建头节点 
            head = ListNode(val)
            tail = head
        } else {
            let temp = ListNode(val)
           //把当前head地址赋给temp的指针域
            temp.next = head
            head = temp
        }
        
    }
    
    //尾插法实现同上
    func appendToTail(_ val: Int) {
        if tail == nil {
            tail = ListNode(val)
            head = tail
        } else {
            let temp = ListNode(val)
            temp.next = head
            head = temp
        }
    }
}
复制代码

例题: 1 ->3 ->5 ->2 ->4 ->2,当给定x=3时,要求返回 1 ->2 ->2 ->3 ->5 ->4.书上给出的解题思路,将完整的链表通过条件判断(入参x)分割成2个新的链表，然后再将2个新链表拼接成完整的链表,看下代码.

func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
    //创建2个Dummy节点
    let prevDummy = ListNode(0), postDummy = ListNode(0)
    var prev = prevDummy, post = postDummy
    
    var node = head
    //判断是否存在node
    while node != nil {
        //判断数据是否小于x
        if node!.val < x {
            //小于x prev.next指针域指向node
            prev.next = node
            prev = node!
        } else
        {
            //同上 大于x 构建新的链表
            post.next = node
            post = node!
        }
        //判断下个节点
        node = node!.next
    }
    //将尾节点next置为nil,防止构成环
    post.next = nil
    //左右拼接(左边尾节点指向右边头节点)
    prev.next = postDummy.next

    return prevDummy.next
}
复制代码

关于Dummy节点,书中给出了详细介绍.

上面代码引入了Dummy节点，它的作用就是作为一个虚拟的头前结点。我们引入它的原因是我们不知道要返回的新链表的头结点是哪一个，它有可能是原链表的第一个节点，可能在原链表的中间，也可能在最后，甚至可能不存在（nil）。而Dummy节点的引入可以巧妙的涵盖所有以上情况，我们可以用dummy.next方便得返回最终需要的头结点。

注解: 1:首先创建左右两个Dummy节点,然后通过 while 判断node是否存在. 2:若存在再判断节点的数据val和判断条件x的关系,小于x则被链道左边链表上,大于x被链到右边链表. 3:执行完 while ,此时我们已经拿到左右两个新的链表.最后把左边的尾节点指向右边的头节点就完成了完整链表的拼接.

注意:需要将右链表的尾节点置nil,防止构成环. 关于检测链表中是否有环,可以通过 快行指针 来检测,若快指针和慢指针变成相等的了,就代表该链表有环,具体的就不在这里介绍了,比较简单.

4 栈和队列

先来了解下栈和队列的基本概念 栈:先进后出(First In Last Out)的结构,又叫FILO.可以理解为我们小时候完的叠罗汉,最下面的人是第一躺下而最后一个起来的. 队列:先进先出(First In First Out)的结构,又叫(FIFO).这个字面上理解就行，就像排队买票一样,先来的人先买到票.

了解了栈和堆的概念,来看下Swift怎么来写出个栈和队列.

protocol Stack {
   //associatedtype:关联类型 相当于范型 在调用的时候可以根据associatedtype指定的Element来设置类型
   associatedtype Element
   //判断栈是否为空
   var isEmpty: Bool {get}
   //栈的大小
   var size: Int {get}
   //栈顶元素
   var peek: Element? {get}
  //mutating:当需要在协议(结构体,枚举)的实例方法中,修改协议(结构体,枚举)的实例属性,需要用到mutating对实例方法进行修饰,不然会报错.
  //进栈
  mutating func push(_ newElement: Element)
  //出栈
  mutating func pop() -> Element?
}
复制代码

实现协议方法

struct IntegerStack: Stack {
//typealias:类型别名 指定协议关联类型的具体类型 和associatedtype成对出现的
typealias Element  = Int

var isEmpty: Bool {return stack.isEmpty}

var size: Int {return stack.count}
//取出stack栈顶元素
var peek: Element? {return stack.last}

private var stack = [Element]()
//push 加入stack数组中
mutating func push(_ newElement: Element) {
   return stack.append(newElement)
}
//pop 删除stack中最后一个元素
mutating func pop() -> Element? {
   return stack.popLast()
  }
}
复制代码

注解:利用协议申明了栈的属性和方法,并在结构体中声明数组stack,对数组数据进行append和poplLast操作,完成入栈出栈操作,比较简单.

再来看下队列的实现:

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}

  //声明左右2个数组
  private var left = [Element]()
  private var right = [Element]()

 //在right数组中添加新元素
  mutating func enqueue(_ newElement: Int) {
      right.append(newElement)
  }

 //出队列时 首先判断left是否为空 
  mutating func dequeue() -> Int? {
      if !left.isEmpty {
       //reversed: 倒序遍历数组
          left = right.reversed()
       //删除right数组
          right.removeAll()
      }
      //删除left数组的最后一个元素
      return left.popLast()
  }
}
复制代码

注解:上面代码里面分别用两个数组分别完成入队列和出队列的操作,用right存储入队列的元素.当出队列时会先判断left是否为空,如果为空left数组指向倒序后的right数组,这时执行popLast,即实现了出队列的操作.size peek isEmpty属性也是充分通过左右两个数组来进行判断. 关于书上用left right两个数组来形成一个队列的写法笔者自己也不是很清楚,希望有知道的同学可以给小弟指点一下.

之后书上提到了 栈和队列互相转换 ,这块部分因为篇幅原因就不介绍了,不过大致思路是通过两个栈/队列,配合生成所对应的结构,是一种用空间复杂度换时间复杂度的写法.有兴趣的同学可以购买原书细读.

例题:给出路径 /a/./b/../b/c/,简化成/c首先分析一下这道题,输入字符串x,输出字符串y.然后我们通过**'/' 将输入的字符串进行分割,分割成字符串数组,然后遍历数组中字符的具体情况（" . "表示当前目录，" ..**"表示上一级目录）就可以了,看下代码.

func simplifyPath(path: String) -> String {
    //初始化存储路径的数组
    var pathStack = [String]()
    //通过"/"分割入参path
    let paths = path.components(separatedBy: "/")
    //遍历paths
    for path in paths {
       // 当path为"."时,表示当前目录,所以不做处理
        guard path != "." else {
           //跳过循环
            continue
        }
        //当path等于".."时,表示返回上级目录
        if path == ".." {
            //这里边界情况一定要考虑,这也是个容易出错的地方
            if (pathStack.count > 0){
               //pathStack有数据,删除last元素
                pathStack.removeLast()
            }
        } else if path != "" {
           //判断path不等于""的边界情况,添加路径
            pathStack.append(path)
        }
    }
    //将pathStack进行遍历拼接,获得最终结果res
    let res = pathStack.reduce(""){
        total, dir in "\(total)/\(dir)"
    }
    //如果是空路径 返回 "/"
    return res.isEmpty ? "/" : res
}
复制代码

上面的例题并不是很难,但是想完整写好却不是十分容易.需要注意的边界条件非常的多,如果在面试的时候只是顺着解决问题的方向走而忽视了这些边界问题,那么给面试官的印象也会大打折扣.

5 二叉树

概念:二叉树中,每个节点最多有两个子节点,一般称为左子节点和右子节点,并且节点的顺序不能任意颠倒.第一层的节点称之为根节点,我们从根节点开始计算,到节点的最大层次为二叉树的深度. 首先看下书中节点实现的代码:

//public:不同于OC的public swift中不能在override和继承的extension中访问
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int){
        self.val = val
    }
}
复制代码

一个完整的二叉树节点包含数据val,左子节点和右子节点.

有了节点我们再看下如何求二叉树的深度

func treeMaxDepth(root: TreeNode?) -> Int {
    
    guard let root = root else {
        return 0;//root不存在返回0
    }
    //max函数:比较两个入参的大小取最大值
    return max(treeMaxDepth(root:root.left), treeMaxDepth(root: root.right)) + 1 
}
复制代码

注解: 1:首先判断入参二叉树节点是否为nil,若不存在的话返回0,若存在递归子节点取最大值. 2:二叉树的深度是从根节点开始计算,这也是为什么在最后我们需要对取到的max值做+1操作.

二叉查找树

在二叉树中有类特别的二叉树叫做 二叉查找树 (Binary Sort Tree),满足所有左子节点的值都小于它的根节点的值,所有右字节点都大于它的根子节点的值,那么问题来了我们怎么判断一颗二叉树是否为二叉查找树呢.来看代码:

func isValidBST(root: TreeNode?) -> Bool {
    return _helper(node: root, nil, nil)
}

private func _helper(node: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
    //node不存在 则到了最底层 递归结束.这个要注意的是第一次传入的node不能为nil
    guard let node = node else {
        return true
    }
    //右子树的值都必须大于它的根节点的值
    if let min = min, node.val <= min {
        return false
    }
    //左子树的值都必须小于它的根节点的值
    if let max = max, node.val >= max {
        return false
    }
    //左右子树同时递归
    return _helper(node: node.left, min, node.val) && _helper(node: node.right, node.val, max)
}
复制代码

注解: 1:这个地方会首先判断当前节点是否存在,若不存在即代表已经递归到最后一层,返回true. 2:然后判断右子树和左子树的val是否满足判断条件,若都满足条件进行下一层的递归. 3:左右同时进行递归操作.

知道了二叉树的基本概念和swift的写法外,再来看下如何实现 二叉树的遍历 操作.常见的二叉树遍历有前序、中序、后序和层级遍历(广度优先遍历).

给出几种遍历方法的规则:

前序遍历规则:1:访问根节点 2:前序遍历左子树 3:前序遍历右子树

中序遍历规则:1:中序遍历左子树 2:访问根节点 3:中序遍历右子树

后序遍历规则：1:后序遍历左子树 2:后序遍历右子树 3:访问根节点

**层级遍历规则:**以层为顺序,将某一层上的节点全部遍历完成后,才向下一层进行遍历,依次类推,至到最后一层.

如果还是不理解可以看下这篇关于二叉树遍历的介绍,讲的比较直白易懂.

关于遍历部分内容因为比较多,笔者摘录书上队列实现树来介绍下实现逻辑,看以下代码:

func levelOrder(root: TreeNode?) -> [[Int]] {
    //初始化 遍历后返回的res数组
    var res = [[Int]]()
    //队列数组
    var queue = [TreeNode]()
    
    if let root = root {
        //存储入参root节点
        queue.append(root)
    }
    
    while queue.count > 0 {
        //获取层级个数
        let size = queue.count
        //每一层 数据存储数组
        var level = [Int]()
        
        for _ in 0 ..< size {
            //removeFirst:删除第一个元素 并返回被删除的元素
            let node = queue.removeFirst()
            //添加数据
            level.append(node.val)
            //判断是否存在 左右子节点 并添加到队列 顺序从左至右
            if let left = node.left {
                queue.append(left)
            }
            if let right = node.right {
                queue.append(right)
            }  
        }
        //存储level数据数组
        res.append(level)
    }
    return res
}
复制代码

注解: 1:首先我们声明数组res,用来存储每一层的val数组,并声明队列数组,方便后面判断. 2:判断入参root是否存在,若存在存储root节点到queue数组中. 3: while 判断queue是否有数据,若有数据则取到queue的第一个数据,并在queue中删除.然后判断下一层的数据,并再次循环遍历. 4:最后把节点的val数据保存到level中,添加到res.

总结

关于本书中算法部分的基本数据结构就介绍的差不多了,后面会对具体的算法实战部分进行介绍.笔者总体感觉这本书更适合初级->中级的同学,对于想要提高自己的初中级开发人员这本书绝对是不错的选择.