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

前言

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

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

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

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

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

首先來看看如何解決第一個問題付魔。最直接的方法可能是兩層 for 循環(huán)遍歷數(shù)組，第一層循環(huán)是每次取一個值 a飞蹂，第二層循是判斷這個數(shù)組中是否存在一個值等于 sum - a几苍，這樣做的時間復(fù)雜度是 O(n^2)，但是借助集合就能將時間復(fù)雜度降為 O(n)晤柄。實現(xiàn)思路是: 遍歷數(shù)組的時候擦剑，用集合保存已經(jīng)遍歷過的元素。在下一次遍歷的過程中芥颈，如果集合中存在一個值等于sum減去當(dāng)前遍歷的值惠勒，則說明數(shù)組中存在一個數(shù)等于sum減去當(dāng)前遍歷的數(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)于第二問爬坑，只要在第一個問題解決方案的基礎(chǔ)上稍稍做下改動即可纠屋，將 Set 換為 Dict 解決問題即可,因為我們要拿到相應(yīng)的下標(biāo)。時間復(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)于這道題我們要處理兩個問題:

• 整個句子的翻轉(zhuǎn)
• 句子中的每個單詞的翻轉(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?
實現(xiàn)代碼如下：

 func reverseWords(s: String?) -> String? {
        guard let s = s else {
            return nil
        }
        var chars = Array(s.characters)
        var start = 0
        //從頭到尾置整個字符串族铆，此步得到的結(jié)果為：eulb si yks eht
        reverseWord(&chars, 0, chars.count - 1)
        //找到每一個單詞對用的首尾index,然后翻轉(zhuǎn)每一個單詞
        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ù)組中的兩個元素
    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ù)的哥攘，每個元素都有指定的索引index指向內(nèi)存地址，因此查詢對時候材鹦，可根據(jù)index快速找到對應(yīng)地址存儲的信息逝淹，此為查詢快。但要數(shù)組進(jìn)行增刪的時候桶唐，就必須將目標(biāo)位置后的所有元素都整體移動栅葡，因此就比較耗時，此為增刪慢尤泽。

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

基本實現(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)

四尚猿、棧和隊列(包含數(shù)組)

基本概念

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

隊列是先進(jìn)先出庄萎。可以理解為排隊現(xiàn)象塘安，誰先來誰就先走糠涛。實際開發(fā)中的 GCD 和 NSOperationQueue d就是基于隊列實現(xiàn)的。

棧和隊列的實現(xiàn)

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

棧的實現(xiàn)。

class Stack {
    //儲存棧上的元素
    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)

隊列的實現(xiàn)帆竹。

class Queue {
    //儲存隊列上的元素
    var arr:[Any]
    
    init() {
        arr = [Any]()
    }
    
    //判斷隊列是否為空
    var isEmpty:Bool{
        return arr.isEmpty
    }
    //獲取隊列首元素
    var firstObj:Any?{
        return arr.last
    }
    /// 加入新元素
    public func enqueue(obj: Any) {
        arr.append(obj)
    }
    /// 推出隊列元素
    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 實戰(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/. 實際上就是 /test，無論輸入多少個. 都返回當(dāng)前目錄栽连。..表示上級目錄险领，如cd ../命令表示是進(jìn)入上級目錄侨舆。

有了對文件路徑的簡單了解，解答上面這道題就簡單了绢陌，完全可以把這道題當(dāng)做是一個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