# 用Swift刷LeetCode（一）

• 1.两数之和

// 方法:暴力法
// 运行时间20ms
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for (index, _) in nums.enumerated() {
if nums[index] + nums[index + 1] == target {
return [index, index + 1]
}
}
return Array<Int>()
}
}

// 字典法
// 运行时间16ms
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
guard nums.count > 1 else {
fatalError()
}

var dict = Dictionary<Int, Int>()

for (i, num) in nums.enumerated() {
if let lastIndex = dict[target - num] {
return [lastIndex, i]
} else {
dict[num] = i
}
}

fatalError()
}

• 2.两数相加

/**
* Definition for singly-linked list.
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init(_ val: Int) {
*         self.val = val
*         self.next = nil
*     }
* }
*/
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
guard l1 != nil else {
return l2
}

guard l2 != nil else {
return l1
}

var c1 = l1,c2 = l2
var carry = 0// 进位标识
let resultListNode: ListNode = ListNode.init(0)// 结果链表头指针
var currentListNode = resultListNode// 操作指针

repeat {
var sum: Int = 0// 每次相加的结果

if c1 != nil {
sum += c1!.val
c1 = c1!.next
}
if c2 != nil {
sum += c2!.val
c2 = c2!.next
}
sum += carry //加上一轮的进位符
carry = sum / 10 // 如果超过10，进位标识符为1；否则0

currentListNode.next = ListNode.init(sum % 10)// 写进链表
currentListNode = currentListNode.next! //移动操作指针

} while (c1 != nil) || (c2 != nil)

if (carry == 1) {// 最后可能会进位
currentListNode.next = ListNode.init(1)
}

return resultListNode.next
}

• 3.无重复字符的最长子串

func lengthOfLongestSubstring(_ s: String) -> Int {
guard s.count > 1 else {
return s.count
}

var ans: Int = 0,left_index: Int = 0
// 值记录键上一次的位置
var dict: Dictionary<Character, Int> = Dictionary<Character, Int>()

var right_index: Int = 0

for char in s {
if let max_left = dict[char] {
left_index = (left_index > max_left) ? left_index : max_left
}

ans = (ans > right_index - left_index + 1) ? ans : (right_index - left_index + 1)
dict[char] = right_index + 1
right_index += 1
}

return ans
}

• 4.寻找两个有序数组的中位数

func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
var array1 = nums1, array2 = nums2
var lengthA = array1.count, lengthB = array2.count

if lengthA > lengthB {//保证B的长度大于等于A的长度
let tempLength = lengthA
lengthA = lengthB
lengthB = tempLength
let tempArray = array1
array1 = nums2
array2 = tempArray
}

var iMin = 0, iMax = lengthA, halfLen = (lengthA + lengthB + 1) / 2
while iMin <= iMax {
let i = (iMin + iMax) / 2
let j = halfLen - i
if (i < iMax) && (array2[j-1] > array1[i]) {
iMin += 1
} else if (i > iMin) && (array1[i-1] > array2[j]) {
iMax -= 1
} else {
var maxLeft = 0
if i == 0 {
maxLeft = array2[j-1]
} else if j == 0 {
maxLeft = array1[i-1]
} else {
maxLeft = array1[i-1] >= array2[j-1] ? array1[i-1] : array2[j-1]
}

if (lengthA + lengthB) % 2 == 1 {
return Double(maxLeft)
}

var minRight: Int = 0
if i == lengthA {
minRight = array2[j]
} else if j == lengthB {
minRight = array1[i]
} else {
minRight = array1[i] < array2[j] ? array1[i] : array2[j]
}
return Double(maxLeft + minRight) / 2.0
}
}

return 0.0
}

• 5.最长回文子串

dp[i][j] = {
dp[i-1][j + 1] : s[i] == s[j],
false          : s[i] != s[j]
}

func longestPalindrome(_ s: String) -> String {
guard s.count > 1 else {
return s
}

// 其中dp[i][j]表示字符串区间[i, j]是否为回文串
var dp: [[Bool]] = Array()
// 初始化dp
// 当i = j时，只有一个字符，肯定是回文串
for i in 0...s.count - 1 {
var eachRow:[Bool] = Array()
for var j in 0...s.count - 1{
if i == j{
eachRow.append(true);
}else{
eachRow.append(false);
}
}
dp.append(eachRow);
}

var longest: Int = 1
var left: Int = 0 // 当前最长子串的首
var right: Int = 0// 当前最长子串的尾
var i: Int = 0// 遍历的首
var j: Int = 0// 遍历的尾
for character_j in s {
if j == 0 {
j += 1
continue
}
i = 0
for character_i in s {
if character_i == character_j {
dp[i][j] = dp[i + 1][j - 1] || j - i <= 1
if dp[i][j] && j - i + 1 > longest{// 如果当前长度大于最新长度就修改
longest = j - i + 1
left = i
right = j
}
} else {
dp[i][j] = false
}
i += 1;
if i >= j{
break
}
}
j += 1;
}
let leftIndex = s.index(s.startIndex, offsetBy: left)
let rightIndex = s.index(s.startIndex, offsetBy: right)
return String(s[leftIndex...rightIndex])
}

• 6.Z 字形变换

func convert(_ s: String, _ numRows: Int) -> String {
let len: Int = s.count
guard (len > numRows) && (numRows > 1) else {
return s
}

// 两整列之间的公差
let d = 2*numRows - 2
var resultStr: String = ""

// 处理字符串
for i in 0..<numRows {// 从第一行遍历到最后一行
var j = i
while j < len {
// 整列的添加
let char = s[s.index(s.startIndex, offsetBy: j)]
resultStr.append(char)

// 单列的添加
if (i != 0) && (i != numRows - 1) && (j - 2*i + d < len) {
let char = s[s.index(s.startIndex, offsetBy: j - 2*i + d)]
resultStr.append(char)
}

j += d
}
}
return resultStr
}

• 7.整数反转

func reverse(_ x: Int) -> Int {
var string: String
var result: Int

if x >= 0 {
string = String("(x)".reversed())
result = Int(string)!
} else {
string = String("(-x)".reversed())
result = 0 - Int(string)!
}

// 反转后整数溢出那么就返回 0
if result > INT32_MAX - 1 || result < -INT32_MAX - 1 {
return 0
} else {
return result
}
}

• 字符串转换整数（atoi）

func myAtoi(_ str: String) -> Int {
guard !str.isEmpty else {
return 0
}

var index: Int = 0
var flag: Bool = true// 正数还是负数
var res: Int = 0// 结果

// 越过前面的空格
for char in str {
if char == " " {
index += 1
} else {
break
}
}

// 匹配"+"或"-"
if index < str.count && str[str.index(str.startIndex, offsetBy: index)] == "+" {
index += 1
} else if index < str.count && str[str.index(str.startIndex, offsetBy: index)] == "-" {
index += 1
flag = false
}

// 处理数字或非数字
while index < str.count {
if (str[str.index(str.startIndex, offsetBy: index)] >= "0" && str[str.index(str.startIndex, offsetBy: index)] <= "9") {// 如果是数字
let num: String = String(str[str.index(str.startIndex, offsetBy: index)])
res = res * 10 + Int(num)!
if (res > INT32_MAX) {
if flag {
return Int(INT32_MAX)
} else {
return Int(-INT32_MAX - 1)
}
}
} else {// 不是数字
if flag {
return res
} else {
return -res
}
}
index += 1
}

if flag {
return res
} else {
return -res
}
}

• 9.回文数

func isPalindrome(_ x: Int) -> Bool {
var string: String = String()
if x >= 0 {// 正数
string = String(x)
if string == String(string.reversed()) {
return true
} else {
return false
}
} else {// 负数
return false
}
}

• 10.正则表达式匹配

‘.’ 匹配任意单个字符。
‘*’ 匹配零个或多个前面的元素。

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *