數(shù)組

數(shù)組是最基本的數(shù)據(jù)結(jié)構(gòu)。在Swift 中，以前Obiective-C時(shí)代中將NSMutableArtay 和NSArray分開(kāi)的做法，被統(tǒng)到了唯一 的數(shù)據(jù)結(jié)構(gòu)Array. 雖然看上去就一種數(shù)據(jù)結(jié)構(gòu)，其實(shí)它的實(shí)現(xiàn)有三種:

• ContiguousArray<Element>:效率最高，元素分配在連續(xù)的元素上。如果數(shù)組是值類型(棧上操作)，則Swift會(huì)自動(dòng)調(diào)用Array的這種實(shí)現(xiàn)，如果注重效率，那么推薦聲明這種類型，尤其是在大量元素是類時(shí)，這樣做效果會(huì)很好。

• Array<Element>: 會(huì)自動(dòng)橋接到Objective-C 中的NSArray上，如果是值類型，則其性能與ContiguousArray無(wú)差別。

• ArraySlice<Element>: 它不是一一個(gè)新的數(shù)組，只是一一個(gè)片段，在內(nèi)存上與原數(shù)組享用同一區(qū)域。

下面是數(shù)組一些最基本的運(yùn)用。
聲明一個(gè)不可修改的數(shù)組

let nums = [1, 2, 3]
let nums = [Int](repeating: 0，count: 5)

//聲明一個(gè)可以修改的數(shù)組var nums=[3,1,2]//增加一個(gè)元素
nums.append(4) 

//對(duì)原數(shù)組進(jìn)行升序排序
nums.sort()

//對(duì)原數(shù)組進(jìn)行降序排序
nums.sort(by: >)

//將原數(shù)組除最后一個(gè)外的所有元素賦值給另一-個(gè)數(shù)組
let anotherNums = Array(nums[0 ..< nums. count - 1])

不要小看這些簡(jiǎn)單的操作:數(shù)組可以依靠它們實(shí)現(xiàn)更多的數(shù)據(jù)結(jié)構(gòu)。Swift 雖然不像Java；有現(xiàn)成的隊(duì)列和棧，但完全可以用數(shù)組配合最簡(jiǎn)單的操作實(shí)現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)，下面就是用數(shù)組實(shí)現(xiàn)棧的示例代碼。
//用數(shù)組實(shí)現(xiàn)棧

class Stack {

  var stack: [AnyObject]

  var isEmpty: Bool { return stack. isEmpty }

  var peek: AnyObject? {  return stack.last }

  init() {
      stack = [AnyObject]()
  }

  func push(object: AnyObject) {
      stack. append(object)
  }

  func pop() -> Any0bject? {
      if (!isEmpty) {
           return stack. removeLast()
        } else {
             return nil
        }
      }
}

最后要特別強(qiáng)調(diào)一個(gè)操作: reserveCapacity()。 它用于為原數(shù)組預(yù)留空間，防止數(shù)組在出加或刪除元素時(shí)反復(fù)申請(qǐng)內(nèi)存空間或是創(chuàng)建新數(shù)組，特別適用于創(chuàng)建和removeAll()時(shí)進(jìn)行調(diào)用，對(duì)于整段代碼可以起到提高性能的作用。

字典和集合

字典和集合(這里專指HashSet)經(jīng)常被使用的原因在于，查找數(shù)據(jù)的時(shí)間復(fù)雜度為0(1)。一般字典和集合要求它們的Key都必須遵守Hashable 協(xié)議，Cocoa中的基本數(shù)據(jù)類型都滿足這一點(diǎn):自定義的class需要實(shí)現(xiàn)Hashable，而又因?yàn)镠ashable是對(duì)Equable的擴(kuò)展，所以還要重載==運(yùn)算符。
下面是關(guān)于字典和集合的一此實(shí)用操作:

let primeNums: Set = [3, 5, 7，11, 13]
let oddNums: Set = [1, 3, 5, 7, 9]

交集、并集、差集

let primeAndOddNum = primeNums. intersection( oddNums)
let prime0r0ddNum = primeNums.formUnion( oddNums )
let oddNotPrimNum = oddNums.subtracting(primeNums )

用字典和高階函數(shù)計(jì)算字符串中每個(gè)字符的出現(xiàn)頻率，結(jié)果為["h":1, "e":1, "l":2, "o":1]

let dict =  Dictionary("hello".map { ($0,1) }, uniquingKeysWith: +)

集合和字典在實(shí)際中經(jīng)常與數(shù)組配合使用，請(qǐng)看下面這道算法題:

給出一個(gè)整型數(shù)組和一個(gè)目標(biāo)值，判斷數(shù)組中是否有兩個(gè)數(shù)之和等于目標(biāo)值。

這道題是經(jīng)典的“2Sum”，即已經(jīng)有一個(gè)數(shù)組記為nums，也有一個(gè)目標(biāo)值記為 target,最后要返回一個(gè)Bool值。
最粗暴的方法就是每次選中一個(gè)數(shù)，然后遍歷整個(gè)數(shù)組，判斷是否有另一個(gè)數(shù)使兩者之和為target。這種方法的時(shí)間復(fù)雜度為0(n2)。

采用集合可以優(yōu)化時(shí)間復(fù)雜度，即在遍歷數(shù)組的過(guò)程中，用集合每次保存當(dāng)前值。假如集合中已經(jīng)有了一個(gè)數(shù)等于目標(biāo)值減去當(dāng)前值，則證明在之前的遍歷中一定有一個(gè)數(shù)與當(dāng)前值之和等于目標(biāo)值。這種方法的時(shí)間復(fù)雜度為0(n)，代碼如下。

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

如果把這道題目稍微修改一下，則變?yōu)?

給定一個(gè)整型數(shù)組中有且僅有兩個(gè)數(shù)之和等于目標(biāo)值，求這兩個(gè)數(shù)在數(shù)組中的序號(hào)。

解決思路與上道題基本類似，但是為了方便得到序列號(hào)，這里使用字典，而此方法的時(shí)間復(fù)雜度依然是0(n)。代碼如下。

func twoSumDict(nums : [Int],target : Int) -> [Int]
    {
        var dict = [Int:Int]()
        
        for (index,num) in nums.enumerated() {
            
            if let lastIndex = dict[target - num]
            {
                return [lastIndex,index]
            }else{
                dict[num] = index
            }
        }
        fatalError("輸入nums錯(cuò)誤")
    }

字符串

字符串在算法實(shí)戰(zhàn)中極其常見(jiàn)。在Swift中，字符串不同于其他語(yǔ)言(包括Objctive-C)，它是值類型，而非引用類型。首先列舉一下字符串的通常用法。
字符串和數(shù)字之間的轉(zhuǎn)換

let str= "3" 
let num = Int(str)
let number = 3

字符串長(zhǎng)度

let len = str.count

訪問(wèn)字符串中的單個(gè)字符，時(shí)間復(fù)雜度為0(1)

let char = str[str.index(str.startIndex, offsetBy: n)]

修改字符串

str.remove(at: n)
str.append("c")
str += "hello world"

檢測(cè)字符串是否是由數(shù)字構(gòu)成

func isStrNum(str: String) -> Bool 
{
  return Int(str) != nil
}

將字符串按字母排序(不考慮大小寫(xiě))

func sortStr(str: String) -> String {
    return String(str.sorted())
}

關(guān)于字符串，下面先看一道以前的Google面試題目。
給出個(gè)字符串， 要求將其按照單詞順序進(jìn)行反轉(zhuǎn)
比如，如果是"the sky is blue"，那么反轉(zhuǎn)后的結(jié)果就是"blue is sky the".

這道題目乍一看很簡(jiǎn)單， 不就是類似反轉(zhuǎn)字符串嗎?但是這里存在以下兩個(gè)問(wèn)題:

• 每個(gè)單詞長(zhǎng)度不一樣。
• 空格需要特殊處理。

這樣一來(lái)代碼寫(xiě)起來(lái)會(huì)很煩瑣，而且容易出錯(cuò)。不如下面先實(shí)現(xiàn)一個(gè)字符串反轉(zhuǎn)的方法。

fileprivate func _reverse<T>(_ chars : inout [T] , _ start : Int, _ end : Int)
    {
        var start = start, end = end
        
        while start < end {
            swap(&chars, start, end)
            start = start + 1
            end = end - 1
        }
    }
    
    
fileprivate func swap<T>(_ chars : inout [T] , _ p : Int, _ q : Int)
 {
      (chars[q],chars[p]) = (chars[p],chars[q])
  }

有了這個(gè)方法，就可以實(shí)行下面兩種字符串的反轉(zhuǎn):

整個(gè)字符串反轉(zhuǎn)， "the sky is blue”一“eulb si yks eht”。

每個(gè)單詞作為一個(gè)字符串單獨(dú)反轉(zhuǎn)，“ eulb si yks eht"” ， blue is sky the” 。

整體思路有了，然后就可以解決這道題了。

func reverseWords(s : String?) -> String?
    {
        
        guard let s = s else {
            return nil
        }
        var chars = Array(s.characters)
        _reverse(&chars, 0, chars.count-1)
        var start : Int = 0
        for i  in 0..<chars.count {
            
            if i == chars.count - 1 || chars[i+1] == " "
            {
                _reverse(&chars, start, i)
                start = i + 2
            }
        }
        let resultStr = String(chars)
        return resultStr
    }