【转载】Swift算法 - 基本语法与技巧

发表于   |   分类于   |  

Swift 是苹果新推出的编程语言，也是苹果首个开源语言。相比于原来的 Objective-C，Swift 要更轻便和灵活。笔者最近使用 Swift 实践了大量的算法（绝大部分是硅谷各大公司的面试题），将心得体会总结于下。此文并不是纯粹讨论 Swift 如何实现某一个具体的算法或者数据结构，如冒泡排序、深度优先遍历，或是树和栈，而是总结归纳一些 Swift 常用的语法和技巧，以便大家在解决面试题中使用。

基本语法

1
2
3
4
5
6
7
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)

上面代码实现了一个非常简单的功能，就是交换一个数组中的两个值。乍一看非常正确，实际上存在以下几个问题。

  1. 在第一个参数前应该加上 inout 关键字。因为在 Swift 中，struct 都是按值传递，class 是按引用传递；数组和字典都是 struct。所以要改变原来的 chars 数组，在其前部加入 inout 关键字，表示是按引用传递。
  2. p 和 q 之前应该加入下划线。Swift 默认函数的第一个参数是局部（local）变量，而后续参数都是外部（external）变量，外部变量必须声明。如果在 p 和 q 前加上下划线，则在调用函数时无需声明外部变量，这样调用起来更简便。
  3. temp 前的 var 应该改为 let。let 用于声明常量（constant），var 用于声明变量（variable）。swap 函数中，temp 并未进行修改，所以应当视为常量，用let来声明。

除原作者以上写出的 3 点问题之外，在我编译时，也有几个方面值得记录下来：

swap 是自带的方法，API 文档描述如下：

1
2
3
4
5
/**我的笔记*/
/// Exchange the values of `a` and `b`.
///
/// - Precondition: `a` and `b` do not alias each other.
public func swap<T>(_ a: inout T, _ b: inout T)

系统提供的 swap 方法和我们自定义的方法使用略有不同，可以说更加简洁一些：

1
2
/**我的笔记*/
swap(&chars[0], &chars[1])

在我看到自定义 swap 方法时，最先想到的是在方法内部修改传入参数，需要使用 var 进行描述，而在 Swift 3 中，var 关键字被取消，强制要求我们使用 inout 关键字，当然我们也可以在方法内部创建一个新的变量：

1
2
3
4
5
6
7
8
/**我的笔记*/
func swap(chars: [String], _ p: Int, _ q: Int) -> [String] {
    var chars = chars
    let temp = chars[p]
    chars[p] = chars[q]
    chars[q] = temp
    return chars
}

但这样处理是交换新的变量，而传入的 chars 是不会被修改的，因此在我们需要一份新的拷贝时，也可以使用这种方式。

修改后的代码为：

1
2
3
4
5
6
7
8
9
func swap(chars: inout [String], _ p: Int, _ q: Int) {
    let temp = chars[p]
    chars[p] = chars[q]
    chars[q] = temp
}
var chars = ["a","b"]
swap(chars: &chars, 0, 1)
chars   //["b", "a"]

再来看一段代码：

1
2
3
4
5
6
func toZero(x: Int) -> Int {
  while x > 0 {
    x -= 1
  }
  return x
}

这里在 x -= 1 处会报错。原因是函数中所有的参数是常量（let），是不可以修改的。解决的方法是在函数中写上 var x = x，之后就可以对 x 进行修改了。

这里所犯的错误和上面类似，同样，如果我们需要对原值进行修改，使用 inout，如果需要得到一份拷贝，就使用 var。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**我的笔记*/
func toZero(x: Int) -> Int {
    var x = x
    while x > 0 {
        x -= 1
    }
    return x
}
func toZero(x: inout Int) -> Int {
    while x > 0 {
        x -= 1
    }
    return x
}
var num = 10
var x = toZero(x: num)  //0
num                     //10
x = toZero(x: &num)     //0
num                     //0

循环

Swift 循环分为 for 和 while 两种，注意他们的结构跟传统的 Java, C / C++ 有很大区别，笔者将其总结如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 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 0.stride(through: names.count - 1, by 2) { }
for i in 0.stride(to: names.count, 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)。
注意，在循环中，i是let变量，是不可以修改的。

在这里，因为 stride 方法语法变更的问题，在 Swift 3 下的写法应为：

1
2
3
/**我的笔记*/
for i in stride(from: 0, to: names.count, by: 2) {}
for i in stride(from: 0, through: names.count - 1, by: 2) {}

排序

Swift 排序效率很高，写法也很简洁。笔者将其总结如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 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
}

同样由于版本问题，我将原作者的代码重新写了一遍，并添加了一部分代码：

1
2
3
4
5
6
/**我的笔记*/
var nums = [8,7,9,2,10]
// Sort an Int array，ascending
nums.sort(by: {$0 < $1})
// Sort an Int array without mutating the original one, ascending
var sortedNums = nums.sorted(by: {$0 < $1})

上面是对原数组进行排序和创建原数组的 Copy 并进行排序，下面是对象数组的排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**我的笔记*/
struct model {
    var startTime: Float
    let productName: String
    var timestamp: Date
}
var a = model(startTime: 1, productName: "a", timestamp: Date.init(timeIntervalSince1970: 5000))
var b = model(startTime: 2, productName: "b", timestamp: Date.init(timeIntervalSince1970: 2000))
var models = [a, b]
// Sort an array with custom-defined objects, ascending
models.sort(by: {$0.startTime < $1.startTime})
models.sort(by: {$0.timestamp < $1.timestamp})
models.sort(by: {$0.productName < $1.productName})

可以看出 Swift 提供的排序还是很强大的，提供了多种数据类型的支持。除此之外，我们可以对字典的 key 进行排序：

1
2
3
4
5
6
7
8
9
10
/**我的笔记*/
var dict = ["3":"3", "2":"2", "1":"1"]
let keys = Array(dict.keys)
var sortedKeys = keys.sorted() {
    let value0 = dict[$0]
    let value1 = dict[$1]
    return value0! < value1!
}
print(sortedKeys)	//["1", "2", "3"]

为什么没有对字典的排序呢？我想是因为字典并不是按位置取值，而是按 key 来取值的。当然，如果要实现的话，也并不困难，我们可以这样将字典的 value 进行排序：

1
2
3
4
5
/**我的笔记*/
var dict = ["3":"3", "2":"2", "1":"1"]
let values = Array(dict.values)
var sortedValues = values.sorted(by: {$0 < $1})
print(sortedValues)		//["1", "2", "3"]

也可以像下面这样，将整个字典进行排序，得到一个字典数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**我的笔记*/
var dict = ["4":"4", "3":"3", "2":"2", "1":"1"]
enum SortOption {
    case KEY
    case VALUE
}
func DictWithOption(dict : [String : String],option : SortOption) ->[(String, String)] {
    var sortResult = [(String,String)]()
    switch option {
    case .KEY:
        sortResult = dict.sorted { $0.0 < $1.0 }
    case .VALUE:
        sortResult = dict.sorted { $0.1 < $1.1 }
    }
    return sortResult
}
var sortedDict = DictWithOption(dict: dict, option: .VALUE)
//[("1", "1"), ("2", "2"), ("3", "3"), ("4", "4")]

活用Guard语句

在原文中，原作者并未对代码进行注释，我为了更好的理解两种控制流，擅自在代码中添加了解释，如果显得杂乱的话，可以在文末找到原文的链接。

使用 Guard 语句可以让逻辑变得非常清楚，尤其是在处理算法问题的时候，请看下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func strStr(haystack: String, _ needle: String) -> Int {
    //字符串转为字符数组
    var hChars = [Character](haystack.characters)
    var nChars = [Character](needle.characters)
    //如果haystack的长度小于needle，说明haystack不包含needle。
    if hChars.count < nChars.count {
        return -1
    }
    //如果haystack的长度等于0，说明haystack不包含needle。
    if hChars.count == 0 {
        return -1
    }
    
    for i in 0 ... hChars.count - nChars.count {
        //如果从hChars中找到nChars的首字母
        if hChars[i] == nChars[0] {
            //进入nChars循环
            for j in 0 ..< nChars.count {
                //如果hChars的下一位不等于nChars的下一位，中断nChars循环，再次进入hChars循环查找首字母。
                if hChars[i + j] != nChars[j] {
                    break
                }
                //如果nChars循环一直相等，且到达nChars尾节点，说明已全部匹配，输出i。
                else {
                    //如果达到尾节点，输出最后一次首字母相等时的i
                    if j == nChars.count - 1 {
                        return i
                    }
                }
            }
        }
    }
    return -1
}

上面这段代码是求字符串 needle 在字符串 haystack 里首次出现的位置。我们发现 for 循环中的嵌套非常繁琐，但是如果使用 guard 语句代码会变得清晰很多：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func strStr(haystack: String, _ needle: String) -> Int {
    //字符串转为字符数组
    var hChars = [Character](haystack.characters)
    var nChars = [Character](needle.characters)
    
    //保证hChars的长度大于nChars的长度，如不满足则说hChars不包含nChars。
    guard hChars.count >= nChars.count else {
        return -1
    }
    //如果nChars的长度等于0，说明nChars是空字符串。
    if nChars.count == 0 {
        return 0
    }
    
    for i in 0 ... hChars.count - nChars.count {
        //保证找到nChars的首字母时，才能进入nChars的循环，如不满足则继续查找首字母。
        guard hChars[i] == nChars[0] else {
            continue
        }
        
        for j in 0 ..< nChars.count {
            //保证hChars的下一位等于nChars的下一位，如不满足则中断nChars循环，再次进入hChars循环查找首字母。
            guard hChars[i+j] == nChars[j] else {
                break
            }
            //如果nChars循环一直相等，且到达nChars尾节点，说明已全部匹配，输出i。
            if j == nChars.count - 1 {
                return 1
            }
        }
    }
    
    return -1
}

guard 语句的好处是判断条件永远是我们希望的条件而不是特殊情况，且成功避免了大量的 if 嵌套。

另外在上面代码中，为何要将字符串转化成数组进行处理？因为 Swift 中没有方法能够以 O(1) 的时间复杂度取得字符串中的字符，我们常用的string.startIndex.advancedBy(n)方法，其时间复杂度为O(n)。所以笔者在这里以空间换时间的方法进行了优化。

总结

Swift 是一门独特的语言，本文对其基本知识和语法进行了适当归纳，文中提到的都是基本细节。下期我们会讨论更加进阶的内容。

原文链接

Swift 算法实战之路：基本语法与技巧 - 故胤道长