常见算法

class ListNode {
    var val: Int
    var next: ListNode?
    init() { self.val = 0; self.next = nil; }
    init(_ val: Int) { self.val = val; self.next = nil; }
    init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init() { self.val = 0; self.left = nil; self.right = nil; }
    init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

//两数之和
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    if nums.isEmpty { return [] }
    var dict = [Int: Int]()
    for (index, num) in nums.enumerated() {
        if let _index = dict[target-num] {
            return [_index, index]
        }
        dict[num] = index
    }
    return []
}

//两数相加
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    var l1 = l1, l2 = l2
    if l1 == nil && l2 == nil { return nil }
    var head: ListNode?
    var cur = head
    var c = 0
    while l1 != nil || l2 != nil {
        let a = l1?.val ?? 0
        let b = l2?.val ?? 0
        let val = (a + b + c) % 10
        c = (a + b + c) / 10
        if head == nil {
            head = ListNode(val)
            cur = head
        } else {
            cur?.next = ListNode(val)
            cur = cur?.next
        }
        l1 = l1?.next
        l2 = l2?.next
    }
    if c == 1 {
        cur?.next = ListNode(1)
    }
    return head
}

//字符串反转
func reverse(_ str: String?) -> String? {
    guard let str = str, !str.isEmpty else { return nil }
    var strs = Array(str)
    var i = 0, j = strs.count - 1
    while i < j {
        strs.swapAt(i, j)
        i += 1
        j -= 1
    }
    return String(strs)
}

//输入: s = "abcabcbb"
//输出: 3
func lengthOfLongestSubstring(_ s: String) -> Int {
    var maxLength = 0
    var i = 0
    var dict = [String: Int]()
    
    for (j, c) in s.enumerated() {
        if let index = dict[String(c)] {
            i = max(i, index + 1)
        }
        maxLength = max(maxLength, j - i + 1)
        dict[String(c)] = j
    }
    return maxLength
}

//有效的括号
func isValid(_ s: String) -> Bool {
    if s.count % 2 != 0 { return false }
    let maps = [")": "(", "]": "[", "}": "{"]
    var stacks: [String] = []
    
    for c in s {
        let ss = String(c)
        if let ss_ = maps[ss] {
            if stacks.isEmpty || stacks.last != ss_ {
                return false
            }
            stacks.removeLast()
        } else {
            stacks.append(ss)
        }
    }
    return stacks.isEmpty
}

//合并两个有序链表
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
    guard let list1 = list1 else { return list2 }
    guard let list2 = list2 else { return list1 }
    
    if list1.val < list2.val {
        list1.next = mergeTwoLists(list1.next, list2)
        return list1
    } else {
        list2.next = mergeTwoLists(list2.next, list1)
        return list2
    }
}

//爬楼梯
func climbStairs(_ n: Int) -> Int {
    var p = 0, q = 0, r = 1
    var j = 1
    while j <= n {
        p = q
        q = r
        r = p + q
        
        j += 1
    }
    return r
}

//二叉树的中序遍历
func inorderTraversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    
    var notes: [Int] = []
    if root.left != nil {
        notes.append(contentsOf: inorderTraversal(root.left))
    }
    notes.append(root.val)
    if root.right != nil {
        notes.append(contentsOf: inorderTraversal(root.right))
    }
    return notes
}

//对称二叉树
func isSymmetric(_ root: TreeNode?) -> Bool {
    func check(left: TreeNode?, right: TreeNode?) -> Bool {
        if left == nil && right == nil { return true }
        if left == nil || right == nil { return false }
        
        return left?.val == right?.val &&
               check(left: left?.left, right: right?.right) &&
               check(left: left?.right, right: right?.left)
    }
    return check(left: root, right: root)
}

//二叉树的最大深度
func maxDepth(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    return 1 + max(maxDepth(root.left), maxDepth(root.right))
}

//买卖股票的最佳时机
func maxProfit(_ prices: [Int]) -> Int {
    var minPrice = Int.max
    var maxProfit = 0
    for price in prices {
        if price < minPrice {
            minPrice = price
        }
        maxProfit = max(maxProfit, price-minPrice)
    }
    return maxProfit
}

//只出现一次的数字
//给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
func singleNumber(_ nums: [Int]) -> Int {
    var dict: [Int: Int] = [:]
    for num in nums {
        if let res = dict[num] {
            dict[num] = res + 1
        } else {
            dict[num] = 1
        }
    }
    return dict.sorted { $0.value < $1.value }.first?.key ?? 0
    
//    var res = 0
//    for num in nums {
//        res ^= num
//    }
//    return res
}

//链表是否有环
func hasCycle(_ head: ListNode?) -> Bool {
    if head == nil || head?.next == nil {
        return false
    }
    
    
    var slow = head, fast = head?.next
    while slow !== fast {
        if fast == nil || fast?.next == nil {
            return false
        }
        slow = slow?.next
        fast = fast?.next?.next
    }
    return true
}

//相交链表
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
    var pA = headA, pB = headB
    if pA == nil || pB == nil { return nil }
    while pA !== pB {
        pA = pA == nil ? headB : pA?.next
        pB = pB == nil ? headA : pB?.next
    }
    return pA
}

//反转链表
func reverseList(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil { return head }
    var head = head
    var p1: ListNode? = nil
    var p2 = head
    while head != nil {
        p2 = p2?.next
        head?.next = p1
        p1 = head
        head = p2
    }
    return p1
}

//翻转二叉树
func invertTree(_ root: TreeNode?) -> TreeNode? {
    if root == nil { return nil }
    let right = root?.right
    let left = root?.left
    root?.left = invertTree(right)
    root?.right = invertTree(left)
    return root
}

//合并二叉树
func mergeTrees(_ root1: TreeNode?, _ root2: TreeNode?) -> TreeNode? {
    guard let root1 = root1 else { return root2 }
    guard let root2 = root2 else { return root1 }
    let root = TreeNode(root1.val + root2.val)
    root.left = mergeTrees(root1.left, root2.left)
    root.right = mergeTrees(root1.right, root2.right)
    return root
}

//二叉树的直径
//给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点
//思路： 把每一个结点当成根节点 得到其 左子树深度+右子树深度+1， 然后取这些值的最大值 就是二叉树的直径
func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
    var res = 0
    
    func maxDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        return 1 + max(maxDepth(root.left), maxDepth(root.right))
    }
    
    func maxNotes(_ root: TreeNode?) {
        guard let root = root else { return }
        let l = maxDepth(root.left)
        let r = maxDepth(root.right)
        res = max(res, l + r)
        maxNotes(root.left)
        maxNotes(root.right)
    }
    
    maxNotes(root)
    return res
}

//删除链表的倒数第 N 个结点
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    if n <= 0 { return head }
    let preHead: ListNode? = ListNode(0, head)
    var p = preHead, q = head
    for _ in 0..<n {
        q = q?.next
    }
    while q != nil {
        p = p?.next
        q = q?.next
    }
    p?.next = p?.next?.next
    return preHead?.next
}

//二叉树展开为链表(按照前序遍历顺序)
func flatten(_ root: TreeNode?) {
    if root == nil { return }
    var p = root
    if p?.left != nil {
        p = p?.left
        while p?.right != nil {
            p = p?.right
        }
        p?.right = root?.right
        root?.right = root?.left
        root?.left = nil
    }
    flatten(root?.right)
}

//二叉树的层序遍历
func levelOrder(_ root: TreeNode?) -> [[Int]] {
    if root == nil { return [] }
    var res: [[Int]] = []
    var arr: [TreeNode?] = [root]
    while !arr.isEmpty {
        let count = arr.count
        var temps: [Int] = []
        for _ in 0..<count {
            let node = arr.removeFirst()
            temps.append(node!.val)
            
            if node?.left != nil {
                arr.append(node?.left)
            }
            if node?.right != nil {
                arr.append(node?.right)
            }
        }
        res.append(temps)
    }
    return res
}

//验证二叉搜索树
func isValidBST(_ root: TreeNode?) -> Bool {
    func isValidBST(_ note: TreeNode?, min: Int, max: Int) -> Bool {
        if note == nil { return true }
        let value = note!.val
        if value <= min || value >= max {
            return false
        }
        return isValidBST(note?.left, min: min, max: value) &&
               isValidBST(note?.right, min: value, max: max)
    }
    return isValidBST(root, min: Int.min, max: Int.max)
}

// 斐波那契数列
func fib(_ n: Int) -> Int {
    if n < 2 { return n }
    var p = 0, q = 0, r = 1
    for _ in 2...n {
        p = q
        q = r
        r = (p + q) % 1_000_000_007
    }
    return r
}