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 threeSum(_ nums: [Int], _ target: Int) -> [[Int]] {
    var res = [[Int]]()
    var sorted = nums
    sorted.sort()
    for i in 0 ..< sorted.count {
        if sorted[i] > target {
            return res
        }
        if i > 0 && sorted[i] == sorted[i - 1] {
            continue
        }
        var left = i + 1
        var right = sorted.count - 1
        while left < right {
            let sum = sorted[i] + sorted[left] + sorted[right]
            if sum < target {
                left += 1
            } else if sum > target {
                right -= 1
            } else {
                res.append([sorted[i], sorted[left], sorted[right]])
                
                while left < right && sorted[left] == sorted[left + 1] {
                    left += 1
                }
                while left < right && sorted[right] == sorted[right - 1] {
                    right -= 1
                }
                
                left += 1
                right -= 1
            }
        }
    }
    return res
}

//两数相加
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 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 minDepth(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    let m1 = minDepth(root.left)
    let m2 = minDepth(root.right)
    return root.left == nil || root.right == nil ? 1 + m1 + m2 : 1 + min(m1, m2)
}

//给定一个二叉树，找出其最大深度。
func maxDepth(_ root: TreeNode?) -> Int {
      guard let root = root else { return 0 }
      return 1 + max(maxDepth(root.left), maxDepth(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
}

//func hash(into hasher: inout Hasher)
//static func == (lhs: Self, rhs: Self) -> Bool
extension Array where Element: Hashable {
    func removingDuplicates() -> [Element] {
        var addedDict = [Element: Bool]()

        return filter {
            addedDict.updateValue(true, forKey: $0) == nil
        }
    }

    mutating func removeDuplicates() {
        self = self.removingDuplicates()
    }
}

// 快排
func quickSort<T: Comparable>(list: inout [T], start: Int, end: Int) {
    if start >= end { return }
    
    let index = partition(list: &list, start: start, end: end)
    
    quickSort(list: &list, start: start, end: index-1)
    quickSort(list: &list, start: index+1, end: end)
}
func partition<T: Comparable>(list: inout [T], start: Int, end: Int) -> Int {
    var left = start, right = end
    let temp = list[start]
    while left != right {
        while list[right] >= temp, left < right {
            right -= 1
        }
        while list[left] <= temp, left < right {
            left += 1
        }
        if left < right {
            list.swapAt(left, right)
        }
    }
    list.swapAt(left, start)
    return left
}

//二分插入法排序
func binarySort<T: Comparable>(array: inout [T]) {
    if array.count <= 1 { return }
        
    var low, mid, high: Int
    var base: T
    
    for i in 1...array.count - 1 {
        low = 0
        high = i - 1
        base = array[i]

        while low <= high {
            mid = (low + high) / 2
            if base <= array[mid] { // 升序
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
        
        var j = i - 1
        while j >= high + 1 {
            array[j + 1] = array[j]
            j -= 1
        }
        
        array[high + 1] = base;
    }
}

// 冒泡
func bubblingSort(list: inout [Int]) {
    let count = list.count
    if list.count <= 1 { return }
    for i in 0..<count - 1 {
        for j in 0..<count - 1 - i {
            if list[j] > list[j+1] {
                list.swapAt(j, j+1)
            }
        }
    }
}

///【双指针】删除重复项
func removeDuplicates(_ nums: inout [Int]) -> Int {
    let count = nums.count
    if count <= 1 { return count }
    var p = 0, q = 1
    while q < count {
        if nums[p] == nums[q] {
            q += 1
        } else {
            nums[p+1] = nums[q]
            p += 1
            q += 1
        }
    }
    return p + 1
}
//链表操作的两种方式：
//1. 直接使用原来的链表来进行操作。
//2. 设置一个虚拟头结点在进行操作。
//删除链表元素
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
    let dummyNode = ListNode()
    dummyNode.next = head
    var currentNode = dummyNode
    while let curNext = currentNode.next {
        if curNext.val == val {
            currentNode.next = curNext.next
        } else {
            currentNode = curNext
        }
    }
    return dummyNode.next
}

//两两交换链表中的节点
func swapPairs(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil {
        return head
    }
    let dummyHead: ListNode = ListNode(-1, head)
    var current: ListNode? = dummyHead
    while current?.next != nil && current?.next?.next != nil {
        let temp1 = current?.next
        let temp2 = current?.next?.next?.next
        
        current?.next = current?.next?.next
        current?.next?.next = temp1
        current?.next?.next?.next = temp2
        
        current = current?.next?.next
    }
    return dummyHead.next
}

//二叉树的最近公共祖先
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        guard let root = root else { return nil }
        if root === p || root === q { return root }
    
        let left  = lowestCommonAncestor(root.left,  p, q)
        let right = lowestCommonAncestor(root.right, p, q)

        if left != nil, right != nil { return root }

        return left ?? right
}

//多读单写
https://www.jianshu.com/p/711859ed2ef3