算法题目
2021-03-04 本文已影响0人
獨荹儛臨
//
// 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
}
