• Swift 算法實(shí)戰(zhàn)一(集合,字典,鏈表,棧,隊(duì)列等算法)
• Swift 算法實(shí)戰(zhàn)二(二叉樹、二分搜索)

前言

用 Swift 也用了小半年了，決定今天開始使用 Swift 來實(shí)現(xiàn)一些基礎(chǔ)的算法。該篇文章就先從簡單的說起，主要內(nèi)容如下：

• 數(shù)組、字符串、集合、字典相關(guān)的基礎(chǔ)算法
• 鏈表
• 棧和隊(duì)列

一、集合和字典相關(guān)算法

對于集合首先要知道集合中的元素都是唯一的，是無序的。關(guān)于集合中的元素是怎樣保證唯一性的，可以參考筆者之前寫過一篇文章哈希算法詳解（附帶 iOS 開發(fā)中實(shí)際應(yīng)用）。集合或字典查找的時(shí)間復(fù)雜度為 O(1)，在實(shí)際的算法問題中，通常會(huì)分別結(jié)合數(shù)組來解決實(shí)際的問題。如下面的兩個(gè)簡單算法問題。

1、已知一個(gè)整形數(shù)組(arr)以及一個(gè)整數(shù)(sum)，判斷數(shù)組中是否存在兩個(gè)數(shù)字之和等于這個(gè)整數(shù)（sum）？
2、求這兩個(gè)數(shù)字在數(shù)組中的下標(biāo) (注意第一問中應(yīng)該是有且只有兩個(gè)數(shù)字等于這個(gè)整數(shù) sum )。

首先來看看如何解決第一個(gè)問題。最直接的方法可能是兩層 for 循環(huán)遍歷數(shù)組，第一層循環(huán)是每次取一個(gè)值 a，第二層循是判斷這個(gè)數(shù)組中是否存在一個(gè)值等于 sum - a，這樣做的時(shí)間復(fù)雜度是 O(n^2)，但是借助集合就能將時(shí)間復(fù)雜度降為 O(n)。實(shí)現(xiàn)思路是: 遍歷數(shù)組的時(shí)候，用集合保存已經(jīng)遍歷過的元素。在下一次遍歷的過程中，如果集合中存在一個(gè)值等于sum減去當(dāng)前遍歷的值，則說明數(shù)組中存在一個(gè)數(shù)等于sum減去當(dāng)前遍歷的數(shù)值。 代碼實(shí)現(xiàn)如下：

func isExist(arr:[Int],sum:Int) -> Bool {
        var set = Set<Int>()
        for num in arr {
            if set.contains(sum - num){
                return true
            }
            set.insert(num)
        }
        return false
    }

關(guān)于第二問，只要在第一個(gè)問題解決方案的基礎(chǔ)上稍稍做下改動(dòng)即可，將 Set 換為 Dict 解決問題即可,因?yàn)槲覀円玫较鄳?yīng)的下標(biāo)。時(shí)間復(fù)雜度同樣是 O(n)。

func getIndex(arr:[Int],sum:Int)->[Int]{
        var dict = [Int:Int]()
        for (i,num) in arr.enumerated(){
            if let idx = dict[sum-num]{
                return [idx,i]
            }else{
                dict[num] = I
            }
        }
        fatalError("沒有滿足條件的下標(biāo)")
    }

二、字符串相關(guān)算法

看一道谷歌的面試題，就是字符串翻轉(zhuǎn)的問題。關(guān)于這道題我們要處理兩個(gè)問題:

• 整個(gè)句子的翻轉(zhuǎn)
• 句子中的每個(gè)單詞的翻轉(zhuǎn)

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?
實(shí)現(xiàn)代碼如下：

 func reverseWords(s: String?) -> String? {
        guard let s = s else {
            return nil
        }
        var chars = Array(s.characters)
        var start = 0
        //從頭到尾置整個(gè)字符串，此步得到的結(jié)果為：eulb si yks eht
        reverseWord(&chars, 0, chars.count - 1)
        //找到每一個(gè)單詞對用的首尾index,然后翻轉(zhuǎn)每一個(gè)單詞
        for i in 0 ..< chars.count {
            print(chars[I])
            if i == chars.count - 1 || chars[i + 1] == " " {
                print(i)
                print(start)
                reverseWord(&chars, start, i)
                start = i + 2
            }
        }
        return String(chars)
    }
    
    //從頭到尾置換數(shù)組中的元素
    fileprivate func reverseWord<T>(_ chars: inout [T], _ start: Int, _ end: Int) {
        var start = start, end = end
        while start < end {
            swapCharacter(&chars, start, end)
            start += 1
            end -= 1
        }
    }
    
    //交換數(shù)組中的兩個(gè)元素
    fileprivate func swapCharacter<T>(_ chars: inout [T], _ p: Int, _ q: Int) {
        (chars[p], chars[q]) = (chars[q], chars[p])
    }

調(diào)用如下:

 var s = "the sky is blue"
 print(reverseWords(s: s))

三、鏈表

基本概念

先說一些鏈表的基本概念知識。數(shù)組的內(nèi)存是連續(xù)的，每個(gè)元素都有指定的索引index指向內(nèi)存地址，因此查詢對時(shí)候，可根據(jù)index快速找到對應(yīng)地址存儲(chǔ)的信息，此為查詢快。但要數(shù)組進(jìn)行增刪的時(shí)候，就必須將目標(biāo)位置后的所有元素都整體移動(dòng)，因此就比較耗時(shí)，此為增刪慢。

鏈表的內(nèi)存不是連續(xù)的。通過指針將各個(gè)內(nèi)存單元鏈接在一起，不是環(huán)形的鏈表會(huì)有一個(gè)或者二個(gè)節(jié)點(diǎn)的指針指向NULL（單向一個(gè)，雙向兩個(gè)）。鏈表不需要提前指定長度，也不會(huì)出現(xiàn)長度不夠的問題，當(dāng)需要存儲(chǔ)數(shù)據(jù)的時(shí)候分配一塊內(nèi)存并將這塊內(nèi)存插入鏈表中即可，故此為增刪快。由于沒有像數(shù)組那樣的索引，因此，查詢的時(shí)候需要遍歷整個(gè)鏈表所有元素的內(nèi)存地址，然后才能確定目標(biāo)元素，此為查詢慢。如下圖是鏈表的三種形式(單鏈表、雙向鏈表、循環(huán)鏈表)。

基本實(shí)現(xiàn)

鏈表基本結(jié)構(gòu)。

class ListNode {
    var value:Int
    var next:ListNode?
    
    init(value:Int) {
        self.value = value
        self.next = nil
    }
}

創(chuàng)建鏈表。

class List {
    var head:ListNode?
    var tail:ListNode?
    
    // 頭插法
    func appendToHead(val: Int) {
        if head == nil {
            head = ListNode(value:val)
            tail = head
        } else {
            let temp = ListNode(value:val)
            temp.next = head
            head = temp
        }
    }
    
    // 尾插法
    func appendToTail(val: Int) {
        if tail == nil {
            tail = ListNode(value:val)
            head = tail
        } else {
            tail!.next = ListNode(value:val)
            tail = tail!.next
        }
    }
}

調(diào)用形式。(這里使用尾插法)

let list = List()
list.appendToTail(val: 1)
list.appendToTail(val: 2)
list.appendToTail(val: 3)
print(list.head?.next?.next?.val)//結(jié)果為:Optional(3)

四、棧和隊(duì)列(包含數(shù)組)

基本概念

棧是后進(jìn)先出的。你可以理解成有好幾個(gè)盤子要壘成一疊，哪個(gè)盤子最后疊上去，下次使用的時(shí)候它就最先被抽出去。實(shí)際開發(fā)中如果涉及到撤銷操作,首先要考慮到用棧來實(shí)現(xiàn)。

隊(duì)列是先進(jìn)先出?？梢岳斫鉃榕抨?duì)現(xiàn)象，誰先來誰就先走。實(shí)際開發(fā)中的 GCD 和 NSOperationQueue d就是基于隊(duì)列實(shí)現(xiàn)的。

棧和隊(duì)列的實(shí)現(xiàn)

正規(guī)的做法使用鏈表來實(shí)現(xiàn)，這樣可以保證加入和刪除的時(shí)間復(fù)雜度是O(1)。但是 Swift 中數(shù)組有很多現(xiàn)成可以直接使用的 API，所以這里可以通過借助 Swift 中的數(shù)組實(shí)現(xiàn)棧和隊(duì)列。

棧的實(shí)現(xiàn)。

class Stack {
    //儲(chǔ)存棧上的元素
    var arr:[Any]
    init() {
        arr = [Any]()
    }
    //判斷棧是否為空
    var isEmpty:Bool{
        return arr.isEmpty
    }
    //獲取棧頂元素
    var peek:Any?{
        return arr.last
    }
    //push操作
    func push(obj:Any) {
        arr.append(obj)
    }
    //pop操作
    func pop() -> Any? {
        if self.isEmpty{
            return nil
        }else{
            //注意removeLast()返回值為移除的對象
            return arr.removeLast()
        }
    }
}

//調(diào)用形式
let stack = Stack()
stack.push(obj: 1)
stack.push(obj: 2)
stack.push(obj: 3)
print(stack.pop())//打印結(jié)果為:Optional(3)

隊(duì)列的實(shí)現(xiàn)。

class Queue {
    //儲(chǔ)存隊(duì)列上的元素
    var arr:[Any]
    
    init() {
        arr = [Any]()
    }
    
    //判斷隊(duì)列是否為空
    var isEmpty:Bool{
        return arr.isEmpty
    }
    //獲取隊(duì)列首元素
    var firstObj:Any?{
        return arr.last
    }
    /// 加入新元素
    public func enqueue(obj: Any) {
        arr.append(obj)
    }
    /// 推出隊(duì)列元素
    public func dequeue() -> Any? {
        if isEmpty {
            return nil
        } else {
            return arr.removeFirst()
        }
    }
}

//調(diào)用形式
let queue = Queue()
queue.enqueue(obj: 1)
queue.enqueue(obj: 2)
queue.enqueue(obj: 3)
print(queue.dequeue())//打印結(jié)果為:Optional(1)

一道 Facebook 實(shí)戰(zhàn)面試題

Given an absolute path for a file (Unix-style), simplify it.For example,
path = "/home/", => "/home" 
path = "/a/./b/../../c/", => "/c"

首先要知道.表示當(dāng)前目錄。如比如 /test/. 實(shí)際上就是 /test，無論輸入多少個(gè). 都返回當(dāng)前目錄。..表示上級目錄，如cd ../命令表示是進(jìn)入上級目錄。

有了對文件路徑的簡單了解，解答上面這道題就簡單了，完全可以把這道題當(dāng)做是一個(gè)pop 的操作。如果出現(xiàn)..就執(zhí)行pop操作。

    func finalPath(pathStr:String) -> String {
        let pathStack = Stack()
        let paths = pathStr.components(separatedBy: "/")
        for path in paths{
            // 對于 "." 我們直接跳過
            guard path != "." else {
                continue
            }
            // 對于 ".." 執(zhí)行pop操作
            if path == ".."  {
                if pathStack.isEmpty == false {
                    pathStack.pop()
                }
            }else if path != "" {// 對于空數(shù)組的特殊情況
                pathStack.push(obj: path)
            }
        }
        //print(pathStack.arr)
        // 將棧中的內(nèi)容轉(zhuǎn)化為優(yōu)化后的新路徑
        let result = pathStack.arr.reduce("") { total, dir in "\(total)/\(dir)" }
        // 注意空路徑的結(jié)果是 "/"
        return result.isEmpty ? "/" : result
    }

//調(diào)用形式
print(finalPath(pathStr: "/a/./b/c/../../d/"))//打印結(jié)果為:/a/d
print(finalPath(pathStr: "/a/./b/../../c/"))//打印結(jié)果為:/c