//
// 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个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。
点击咨询 