算法题目

//
//  Learn.swift
//  AgoraDemo
//
//  Created by kcl on 2021/3/5.
//  Copyright © 2021 kcl. All rights reserved.
//

import UIKit


// LeetCode 算法学习
class Learn: NSObject {

}

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


public class TreeNode {
    
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        
        self.val = val
        self.left = left
        self.right = right
    }
}
 
class Solution {
    
    
    
    //BFS 实现验证树是否对称
    func isSymmetric2 ( _ root: TreeNode?) -> Bool {
      
        if root == nil {
            return true
        }
        
        var queue = [TreeNode?]()
        if root?.left == nil && root?.right == nil {
            return true
        }
        if (root?.left == nil && root?.right != nil) || (root?.right == nil && root?.left != nil) {
            return false
        }
        
        queue.append((root?.left)!)
        queue.append((root?.right)!)
        
        while queue.count != 0 {
            var arr = [Int]()
            for _ in 0 ..< queue.count {
                let node = queue.first!
                if node == nil {
                    arr.append(-1)
                } else {
                    arr.append(node!.val)
                    queue.append(node!.left)
                    queue.append(node!.right)
                }
                queue.removeFirst()
            }
            let count = arr.count
            for i in 0 ..< count/2 {
                if arr[i] != arr[count-i-1] {
                    return false
                }
            }
        }
        return true
    }
    
    // 是否是对称的
    var isSame = true
    func isSymmetric ( _ root: TreeNode?) -> Bool {
            // write code here
        if root == nil {
            return true
        }
       
        let left = root?.left
        let right = root?.right
        
        reverse1(left: left, right: right)
        return isSame
    }
    
    func reverse1(left: TreeNode?, right: TreeNode?) {
        
        if left == nil && right == nil {
            return
        }
        
        if (left == nil && right != nil) || (right == nil && left != nil)  {
            isSame = false
            return
        }
        
        if left!.val != right?.val {
            isSame = false
        }
        if isSame == true {
            reverse1(left: left?.left, right: right?.right)
            reverse1(left: left?.right, right: right?.left)
        }
        
    }
    
    
    
    // 是否是质数
    func isss(n: Int) -> Bool {
        
        for i in 2 ... Int(sqrt(Double(n))) {
            if n % i == 0 {
                return false
            }
        }
        return true
    }
    func getCount(inputNum: Int) -> Int {
        
        var sum = 0
        for i in 0 ... inputNum/2 {
            if isss(n: i) && isss(n: inputNum-i) {
                sum += 1
            }
        }
        return sum
    }
    // 对链表进行插入排序。
    func insertionSortList(_ head: ListNode?) -> ListNode? {
        
        
        if head == nil || head?.next == nil {
            return head
        }
        let result: ListNode = ListNode(0) //指针指向第一个位置
        result.next = head
        var pre: ListNode? = nil // 用于指向前面排序好的链表
        var current:ListNode? = head
        while current?.next != nil {
            
            if current!.val <= (current?.next!.val)! {
                
                current = current?.next
                continue
            }
            
            pre = result // 因为第一个数据是0 所以需要指向下一个
            while pre!.next!.val <= current!.next!.val {
                pre = pre?.next
            }
            
            let cur = current?.next
            current?.next = cur?.next
            cur?.next = pre?.next
            pre?.next = cur
            
            
        }

        return result.next
    }
    // 链表排序（归并排序）
    func sortList(_ head: ListNode?) -> ListNode? {

        guard let head = head else {
            return nil
        }
        if head.next == nil {
            return head
        }
        var l:ListNode? = nil
        var r:ListNode? = nil
        var fast = head.next?.next
        var slow:ListNode? = head
        // 取中
        while fast != nil {
            fast = fast?.next?.next
            slow = slow?.next
        }
        // 先分 后合
        r = sortList(slow?.next)
        slow?.next = nil
        l = sortList(head)
        return merge(l, node2: r)
    }
    // 合并有序链表 1->2->5
        //        3->4->7
    
    func merge(_ node1: ListNode?, node2: ListNode?) -> ListNode? {
        
        let re = ListNode(0)
        var temp:ListNode? = re
        var f1:ListNode? = nil
        var f2:ListNode? = nil
        f1 = node1
        f2 = node2
        
        while f1 != nil && f2 != nil {
            
            if f1!.val <= f2!.val {
                temp?.next = f1
                f1 = f1!.next
            } else {
                temp?.next = f2
                f2 = f2!.next
            }
            temp = temp!.next
        }
        
        temp!.next = f1 == nil ? f2:f1
        return re.next
    }
    // 指定位置翻转链表
//    func reverseKGroup ( _ head: ListNode?,  _ k: Int) -> ListNode? {
//
//        // write code here
//        guard let head = head else {
//            return nil
//        }
//        if k <= 1 {
//            return head
//        }
//        var current = head
//        var next = current.next
//        var pre :ListNode? = ListNode(0)
//        var index = 1
//        while index <= k {
//
//            next?.next = current
//            pre?.next = next
//            current = current.next
//
//            index += 1
//        }
//        return temp
//    }
    
    // 前序遍历序列{1,2,4,7,3,5,6,8} 和
    // 中序遍历序列{4,7,2,1,5,3,8,6}
    func reConstructBinaryTree ( _ pre: [Int],  _ vin: [Int]) -> TreeNode? {
            // write code here
//        let x = pre[0 ..< 2]
        if pre.count <= 0 || vin.count <= 0 {
            return nil
        }
        let treeNode = TreeNode(pre[0])
        for i in 0 ..< vin.count {

            if pre[0] == vin[i] {
                treeNode.left = reConstructBinaryTree(Array(pre[1 ..< i+1]), Array(vin[0 ..< i]))
                treeNode.right = reConstructBinaryTree(Array(pre[i+1 ..< pre.count]), Array(vin[i+1 ..< vin.count]))
            }
        }
        return treeNode
    }
    
    // 1, 2, 21, 9, 12, 3, 4, 7, 6
    // 希尔排序
    func shellSort(_ list: inout [Int]) {
        
        var gap = list.count
        while gap > 0 {
            
            for i in gap ..< list.count {
                
                let temp = list[i]
                var j = i
                
                while j >= gap && temp < list[j-gap] {
                    list[j] = list[j-gap]
                    j -= gap
                }
                list[j] = temp
            }
            gap /= 2
        }
    }
    // 快速排序
    
    func quickSort(_ list: inout [Int]) {
        
        let i = 0
        let j = list.count - 1
        
        quickSort2(&list, startIndex: i, endIndex: j)
    }
    
    func quickSort2(_ list: inout [Int], startIndex: Int, endIndex: Int) {
        
       
        var i = startIndex
        var j = endIndex
        if i >= j {
            return
        }
        let temp = list[i]
        while i < j {
            
            while temp <= list[j] && i < j {
                j -= 1
            }
            list[i] = list[j]
            list[j] = temp

            while temp >= list[i] && i < j {
                i += 1
            }
            list[j] = list[i]
            list[i] = temp
        }
        
        quickSort2(&list, startIndex: startIndex, endIndex: i-1)
        quickSort2(&list, startIndex: i+1, endIndex: endIndex)
    }
    
    
    
    // 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
    
//    叶子节点 是指没有子节点的节点。
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/path-sum
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//    func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
//
//        guard let root = root else {
//            return false
//        }
//
//        if targetSum == root.val && root.left == nil && root.right == nil {
//            return true
//        }
//
//        return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val)
//    }
    
    var hasSum = false
    // DFS
    func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
        
        guard let root = root else {
            return false
        }
        dfsHasPathSum(root, targetSum)
        return hasSum
    }
    
    
    func dfsHasPathSum(_ node: TreeNode?, _ targetSum: Int) {
        
        
        if node == nil {
            return
        }
        if node?.left == nil && node?.right == nil {
            if targetSum == node?.val {
                hasSum = true
            }
        }
        dfsHasPathSum(node?.left, targetSum-node!.val)
        dfsHasPathSum(node?.right, targetSum-node!.val)
    }
    
 
    // 输入：1->2->4, 1->3->4
//    输出：1->1->2->3->4->4
    // 链表合并
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        
        var L1: ListNode? = l1
        var L2: ListNode? = l2
        let tempNode: ListNode? = ListNode(0)
        var listNode = tempNode
        while L1 != nil && L2 != nil {
            
            if (L1!.val <= L2!.val) {
                listNode?.next = L1
                listNode = listNode?.next
                L1 = L1?.next
            } else {
                listNode?.next = L2
                listNode = listNode?.next
                L2 = L2?.next
            }
        }
        if L1 == nil { listNode?.next = L2 }
        if L2 == nil { listNode?.next = L1 }
        return tempNode?.next
    }
    // 反向打印链表
    func reversePrint(_ head: ListNode?) -> [Int] {
        var list = [Int]()
        
        var current:ListNode? = head
        if current != nil {
            list.append(current!.val)
        }
        
        while current?.next != nil {
            current = current?.next
            list.append(current!.val)
        }
        
        return list.reversed()
    }
    //    输入: 1->2->3->4->5->NULL
    //    输出: 5->4->3->2->1->NULL
    // 链表反转
    func reverseList(_ head: ListNode?) -> ListNode? {
        var prev:ListNode? = nil
        var current:ListNode? = head
        
        while (current != nil) {
            let temp = current?.next
            current?.next = prev
            prev = current
            current = temp
        }
    
        return prev
    }
    
    // 两个数相加 44567 + 978
    func stringAdd(_ num1: String, num2: String) -> String {
        
        let dit = ["0": 0,
                   "1": 1,
                   "2": 2,
                   "3": 3,
                   "4": 4,
                   "5": 5,
                   "6": 6,
                   "7": 7,
                   "8": 8,
                   "9": 9]
      
        
        for (index, value) in Array(num1).enumerated() {
            
        }
        
        for (index, value) in Array(num2).enumerated() {
            
        }
        return ""
    }
    
    // DFS 查找
    // 递归
    func DFSmaxDepth(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        var level = 0
        dfs(tree: root, level: &level, count: 0)
        return level
    }
    
    func dfs(tree: TreeNode?, level: inout Int, count: Int) {
       
    
        if level < count + 1 {
            level = count + 1
        }
        if tree?.left != nil {
            dfs(tree: tree?.left!, level: &level, count: level)
        }
        
        if tree?.right != nil {
            dfs(tree: tree?.right!, level: &level, count: level)
        }
    }
    
    // BFS 查找
    func maxDepth(_ root: TreeNode?) -> Int {
        
        if root == nil {
            return 0
        }
        var level = 0
        var queue = [TreeNode]()
        queue.append(root!)
        while queue.count != 0 {
            let size = queue.count
            level += 1
            for _ in 0 ..< size {
                let tree = queue[0]
                
                if tree.left != nil {
                    queue.append(tree.left!)
                }
                if tree.right != nil {
                    queue.append(tree.right!)
                }
                queue.removeFirst()
            }
            
        }
        return level
    }
    

    // 递归 前序遍历  根左右
    func firstOrder(_ root: TreeNode?) -> [Int] {
        
        var list = [Int]()
        guard let root = root else {
            return list
        }
        loadTree(root, list: &list)
        
        return list
    }
    
    func loadTree(_ node: TreeNode, list: inout [Int]) {
        
        list.append(node.val)
        if node.left != nil {
            loadTree(node.left!, list: &list)
        }
        
        if node.right != nil {
            loadTree(node.right!, list: &list)
        }
    }
    
    // 跳台阶 递归
    func jumpTable(_ level: Int) -> Int {
        
        if level <= 2 { return level }
        return jumpTableRe(level)
    }
    
    func jumpTableRe(_ level: Int) -> Int {
        
        if level <= 2 {
            return level
        }
        
        return jumpTableRe(level-1) + jumpTableRe(level-2)
    }
    
    // 跳台阶
    func jumpTable2(_ level: Int) -> Int {
        
        var count = level
        if level <= 2 {
            return level
        }
        var a = 2
        var b = 1
        while count > 2 {
            
            a = a+b
            b = a-b
            count -= 1
        }
        return a
    }
    
    
    // 层序遍历二叉树
    func levelOrder(_ root: TreeNode?) -> [[Int]] {

        guard let root = root else {
            return []
        }
        var result = [[Int]]()
//        result.append([root.val])
        var queue = [TreeNode]()
        queue.append(root)
        var reverse = true
        while queue.count != 0 {
            var v = [Int]()
            
            
            for _ in 0 ..< queue.count {
                let tree = queue[0]
                v.append(tree.val)
                if reverse == true{
                    if tree.right != nil {
                        
                        queue.append(tree.right!)
                    }
                    if tree.left != nil {
                   
                        queue.append(tree.left!)
                    }
                } else {
                    if tree.left != nil {
                        
                        queue.append(tree.left!)
                    }
                    if tree.right != nil {
                   
                        queue.append(tree.right!)
                    }
                }
                
                queue.removeFirst()
            }
            reverse = !reverse
            result.append(v)
        }
        
        return result
        
    }
    // [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
    // 矩阵翻转90度
    func rotate(_ matrix: inout [[Int]]) {
        
        // 循环次数
        var rel = 0
        while rel < matrix.count/2 {
            //
            print("rel =", rel)
            let range = matrix.count-rel*2-1
            for i in 0 ..< range {
                
                for j in 0 ..< 4 {
                    
                }
//                let s = rel+i
//                let a = matrix[s][
//                var a = matrix[rel+i][]
//                print(s)
//                var b = matrix[i+rel-1][matrix.count-1-i+rel-1]
//                var c = matrix[matrix.count-1-i+rel-1][matrix.count-1-i+rel-1]
//                var d = matrix[matrix.count-1-i+rel-1][rel-1]
//                let x = a+b+c+d
//                d = c; c=b; b = a; a = x-d-c-b
            }
            
            rel += 1
        }
        print(matrix)
        
    }
//    675321  转换成 123576
    func reverse(_ x: Int) -> Int {
        
        var sum:Int = x
        var result:Int = 0
        while sum != 0 {
        
            result = result*10 + sum % 10
            sum /= 10
        }
      
        return result > INT32_MAX || result < -INT32_MAX ? 0: result
    }
//    https://leetcode-cn.com/problems/roman-to-integer/
    
    // 最长公共前缀
//    输入：strs = ["flower","flow","flight"]
//    输出："fl"
    func longestCommonPrefix(_ strs: [String]) -> String {
        
        return ""
    }
    // 删除重复元素
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        
        var dict = [Int: Int]()
        for (i, num) in nums.enumerated().reversed() {
            if dict.values.contains(num) {
                nums.remove(at: i)
                continue
            } else {
                dict[num] = num
            }
        }
        return nums.count
    }
    // 罗马数字转Int
    func romanToInt(_ s: String) -> Int {

        let hashMap = ["I": 1,
                       "V": 5,
                       "X": 10,
                       "L": 50,
                       "C": 100,
                       "D": 500,
                       "M": 1000]
        var result = 0
        
        let arr = Array(s)
        // MCMXCIV IV
        
        for i in 0 ..< arr.count {
            
            if i <  arr.count - 1 && hashMap["\(arr[i])"]! < hashMap["\(arr[i+1])"]!  {
                result -= hashMap["\(arr[i])"]!
            } else {
                result += hashMap["\(arr[i])"]!
            }

        }
        return result
        
//        var hashArr = [String]()
        //            if hashArr.count > 0 {
        //
        //                let str = hashArr.first!
        //                // V > I
        //                if hashMap[ss]! > hashMap[str]! {
        //                    result = hashMap[ss]! + result - 2*hashMap[str]!
        //                    hashArr.removeAll()
        //                } else {
        //                    hashArr.removeAll()
        //                    result += hashMap[ss]!
        //                    hashArr.append(ss)
        //                }
        //            } else {
        //                result += hashMap[ss]!
        //                hashArr.append(ss)
        //            }
        
        
    }
    // 回响数字
    func isPalindrome(_ x: Int) -> Bool {

        if x<0 { return false }
        var rem = 0
        var y = 0
        var quo = x
        while quo != 0 {
            rem=quo%10;
            y=y*10+rem;
            quo=quo/10;
        }
        return y == x
    }

    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
           
        var hashMap = [Int:Int]()
        
        for (index, num) in nums.enumerated() {
            
            let value = target - num
            if hashMap.keys.contains(value) {
                return [hashMap[value]!, index]
            }
            
            hashMap[num] = index
        }
        
        return []
        
    }
    // 异或 获取只出现一次的数字 重复出现的数字是偶数
    func singleNumber(_ nums: [Int]) -> Int {

        var num:Int = 0
        for i in 0 ..< nums.count {
            num = num^nums[i]
        }
        return num
    }
     
    //摩尔投票 众数+1， 非众数-1
    func majorityElement(_ nums: [Int]) -> Int {
        
        var count = 0
        var res = nums[0]
        for num in nums {
            if num == res {
                count += 1
            } else {
                count -= 1
                
                if count == 0 {
                    res = num
                    count += 1
                }
            }
        }
        
        return res
    }
    

}

class CPet:NSObject {
    var name: String?
    var kind: String?
    init(name: String, kind: String) {
        self.kind = kind
        self.name = name
    }
}
//struct SParentPet {
//    var name: String?
//    var kind: String?
//}
struct SPet {
    var name: String?
    var kind: String?
}

class Node {
    
    var neighbors = [Node]()
    var visited:Bool = true
}