Swift 语言应对面试中的算法难题

Swift面试算法难题解析与代码实战

在Swift面试中，算法题是考察应聘者逻辑思维、编程能力和解决问题的关键环节。本文将围绕Swift语言，针对面试中常见的算法难题进行解析，并提供相应的代码实战示例，帮助读者在面试中游刃有余。

一、排序算法

排序算法是面试中经常出现的问题，以下将介绍几种常见的排序算法及其Swift实现。

1. 冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

swift func bubbleSort(_ array: [Int]) -> [Int] { var array = array let n = array.count for i in 0..<#n { for j in 0.. array[j + 1] { array.swapAt(j, j + 1) } } } return array }

2. 选择排序

选择排序是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

swift func selectionSort(_ array: [Int]) -> [Int] { var array = array let n = array.count for i in 0..<#n { var minIndex = i for j in i+1..<#n { if array[j] < array[minIndex] { minIndex = j } } array.swapAt(i, minIndex) } return array }

3. 快速排序

快速排序是一种分而治之的排序算法。它将原始数组分为两个子数组，一个包含比基准值小的元素，另一个包含比基准值大的元素，然后递归地对这两个子数组进行快速排序。

swift func quickSort(_ array: [Int]) -> [Int] { guard array.count > 1 else { return array } let pivot = array[array.count / 2] let less = array.filter { $0 pivot } return quickSort(less) + equal + quickSort(greater) }

二、查找算法

查找算法是面试中另一个常见的题型，以下介绍几种常见的查找算法及其Swift实现。

1. 线性查找

线性查找是最简单的一种查找算法，它逐个检查数组中的元素，直到找到目标值或遍历完整个数组。

swift func linearSearch(_ array: [Int], target: Int) -> Int? { for (index, value) in array.enumerated() { if value == target { return index } } return nil }

2. 二分查找

二分查找是一种高效的查找算法，它适用于有序数组。二分查找的基本思想是将待查找的值与数组的中间值进行比较，然后根据比较结果缩小查找范围。

swift func binarySearch(_ array: [Int], target: Int) -> Int? { var low = 0 var high = array.count - 1 while low <= high { let mid = (low + high) / 2 if array[mid] == target { return mid } else if array[mid] < target { low = mid + 1 } else { high = mid - 1 } } return nil }

三、动态规划

动态规划是一种解决复杂问题的算法思想，它将问题分解为更小的子问题，并存储子问题的解以避免重复计算。

1. 斐波那契数列

斐波那契数列是动态规划的经典问题之一。

swift func fibonacci(_ n: Int) -> Int { var fib = [0, 1] for i in 2...n { fib.append(fib[i - 1] + fib[i - 2]) } return fib[n] }

2. 最长公共子序列

最长公共子序列（LCS）问题是动态规划中的另一个经典问题。

swift func lcs(_ x: String, _ y: String) -> String { let m = x.count let n = y.count var dp = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1) for i in 1...m { for j in 1...n { if x[x.index(x.startIndex, offsetBy: i - 1)] == y[y.index(y.startIndex, offsetBy: j - 1)] { dp[i][j] = dp[i - 1][j - 1] + 1 } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) } } } return String(repeating: x[x.index(x.startIndex, offsetBy: m - dp[m][n])], count: dp[m][n]) }