用Swift刷LeetCode（一）

• 1.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的 两个 整数。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

思路：哈希表记录遍历过的数字和下标。

// 方法:暴力法
// 运行时间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.两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思路：利用进位标识。

/**
 * 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.无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

思路：可以使用HashMap来建立字符和其出现位置之间的映射 滑动窗口

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.寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。

太难了，参考了篇文章。

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.最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

思路：动态规划。

参考 最长连续回文串Swift实现 。

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 字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

思路：找出数字之间的规律，逐行添加。

规律：两整列之间方差：d = 2 * numRows - 2 非整列的数字公式：j - 2*i + d

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.整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

思路：转化为字符串后反转，再转回整数。

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）

请你来实现一个 atoi 函数，使其能将字符串转换成整数。 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。 该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。 在任何情况下，若函数不能进行有效的转换时，请返回 0。

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，qing返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

思路：因为不能进行有效的转换时，返回0，所以可以设置初始化结果为0。设置个正负标识符。然后越过前面的空格，检测第一个非空格字符是不是正负号，改变正负标识符。最后遍历后面的数字，处理超数值范围。如果没有问题，最后输出转化的数字。

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) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。

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

匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

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

笔者自己想得方法有漏洞，网上的答案没看懂。