Swift 算法實戰之路（一）
Swift是蘋果新推出的編程語言，也是蘋果首個開源語言。相比于原來的Objective-C，Swift要更輕便和靈活。筆者最近使用Swift實踐了大量的算法（絕大部分是硅谷各大公司的面試題），將心得體會總結于下。此文并不是純粹討論Swift如何實現某一個具體的算法或者數據結構，如冒泡排序、深度優先遍歷，或是樹和棧，而是總結歸納一些Swift常用的語法和技巧，以便大家在解決面試題中使用。
基本語法
先來看下面一段代碼
func swap(chars:[Character], p: Int, q: Int) {
var temp = chars[p]
chars[p] = chars[q]
chars[q] = temp
}
// Assume array is a character array and it has enough elements
swap(array, p: 0, q: 1)
上面代碼實現了一個非常簡單的功能，就是交換一個數組中的兩個值。乍一看非常正確，實際上存在以下幾個問題。
- 在第一個參數前應該加上 inout 關鍵字。因為在Swift中，struct都是按值傳遞，class是按引用傳遞；數組和字典都是struct。所以要改變原來的chars數組，在其前部加入inout關鍵字，表示是按引用傳遞。
- p 和 q 之前應該加入下劃線。Swift默認函數的第一個參數是局部（local）變量，而后續參數都是外部（external）變量，外部變量必須聲明。如果在p和q前加上下劃線，則在調用函數時無需聲明外部變量，這樣調用起來更簡便。
- temp前的var應該改為 let 。let用于聲明常量（constant），var用于聲明變量（variable）。swap函數中，temp并未進行修改，所以應當視為常量，用let來聲明。
修改過后的代碼為
func swap(inout chars:[Character], _ p: Int, _ q: Int) {
let temp = chars[p]
chars[p] = chars[q]
chars[q] = temp
}
// Assume array is a character array and it has enough elements
swap(&array, 0, 1)
再來看一段代碼
func toZero(x: Int) -> Int {
while x > 0 {
x -= 1
}
return x
}
這里在 x -= 1 處會報錯。原因是函數中所有的參數是常量（let），是不可以修改的。解決的方法是在函數中寫上 var x = x ，之后就可以對 x 進行修改了
循環
Swift循環分為for和while兩種，注意他們的結構跟傳統的 Java, C/C++有很大區別，筆者將其總結如下
// Assume names is an array holds enough Strings
// for loop
for name in names { }
for i in 0 ... names.count - 1 { }
for i in 0 ..<names.count { }
for _ in 0 ..< names.count { }
for name in names.reverse() { }
for i in stride(from: 0, to: names.count - 1, by: 2) { }
// while loop
var i = 0
while i < names.count { }
repeat { } while i < names.count
以上代碼非常簡單。需要說明的有兩個，一個是 for _ in 0 ..< names.count { } 。當我們不需要數組中每一個具體的元素值時，我們就可以用下劃線來代表序號。
另一個是是 repeat { } while i < names.count 。這個相當于我們熟悉（java）的 do { } while (i < names.length) 。
排序
swift排序效率很高，寫法也很簡潔。筆者將其總結如下
// Sort an Int array，ascending
nums.sortInPlace({$0 < $1})
// Sort an Int array without mutating the original one, ascending
var sortedNums = nums.sort({$0 < $1})
// Sort an array with custom-defined objects, ascending
timeIntervals.sortInPlace({$0.startTime < $1.startTime})
// Sort keys in a dictionary according to its value, ascending
let keys = Array(dict.keys)
var sortedKeys = keys.sort() {
let value0 = dict[$0]
let value1 = dict[$1]
return value0 < value1
}
活用Guard語句
使用Guard語句可以讓邏輯變得非常清楚，尤其是在處理算法問題的時候，請看下面的代碼
// Returns the index of the first occurrence of needle in haystack,
// or -1 if needle is not part of haystack
func strStr(haystack: String, _ needle: String) -> Int {
var hChars = [Character](haystack.characters)
var nChars = [Character](needle.characters)
if hChars.count < nChars.count {
return -1
}
if hChars.count == 0 {
return -1
}
for i in 0 ... hChars.count - nChars.count {
if hChars[i] == nChars[0] {
for j in 0 ..< nChars.count {
if hChars[i + j] != nChars[j] {
break
} else {
if j == nChars.count - 1 {
return i
}
}
}
}
}
return -1
}
上面這段代碼是求字符串needle在字符串haystack里首次出現的位置。我們發現for循環中的嵌套非常繁瑣，但是如果使用Guard語句代碼會變得清晰很多：
func strStr(haystack: String, _ needle: String) -> Int {
var hChars = [Character](haystack.characters)
var nChars = [Character](needle.characters)
guard hChars.count >= nChars.count else {
return -1
}
if nChars.count == 0 {
return 0
}
for i in 0 ... hChars.count - nChars.count {
guard hChars[i] == nChars[0] else {
continue
}
for j in 0 ..< nChars.count {
guard hChars[i + j] == nChars[j] else {
break
}
if j == nChars.count - 1 {
return i
}
}
}
return -1
}
Guard語句的好處是判斷條件永遠是我們希望的條件而不是特殊情況，且成功避免了大量的if嵌套。Guard語句詳解請移步此文《Swift的Guard語句》
另外在上面代碼中，為何要將字符串轉化成數組進行處理？因為Swift中沒有方法能夠以O(1)的時間復雜度取得字符串中的字符，我們常用的 string.startIndex.advancedBy(n) 方法，其時間復雜度為O(n)。所以筆者在這里以空間換時間的方法進行了優化。
總結
Swift是一門獨特的語言，本文對其基本知識和語法進行了適當歸納，文中提到的都是基本細節。下期我們會討論更加進階的內容。
來自： http://www.jianshu.com/p/ee16bcf50a59