算法题目

时间:2021-7-20 作者:qvyue
//
//  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 .. 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  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  ListNode? {
//
//        // write code here
//        guard let head = head else {
//            return nil
//        }
//        if k  TreeNode? {
            // write code here
//        let x = pre[0 .. 0 {
            
            for i in gap ..= gap && temp = j {
            return
        }
        let temp = list[i]
        while i = list[i] && i  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  [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  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 .. [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  Int {
        
        if level  Int {
        
        var count = level
        if level  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 .. Int {
        
        var sum:Int = x
        var result:Int = 0
        while sum != 0 {
        
            result = result*10 + sum % 10
            sum /= 10
        }
      
        return result > INT32_MAX || result  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 .. 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 [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 .. 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
}


声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。