QuickSort BinaryTree`s deep LeetCode~ListNode

快排

func QuickSort<T: Comparable>(dest:[T])->[T]{ guard dest.count > 1 else { return dest } let middle = dest[dest.count/2] let bigger = dest.filter { (t:T) -> Bool in return t > middle } let equal = dest.filter { (t:T) -> Bool in return t == middle } let less = dest.filter { (t:T) -> Bool in return t < middle } let finally = QuickSort(dest: less) + equal + QuickSort(dest: bigger) return finally } var test1 = [1,2,-1,34,3434,3434,3,2,4,3,243,23,34,3434,32,-2,0,0,343443,54,25] print(QuickSort(dest: test1))

二叉树系列

1 二叉树深度

typealias Node = BinaryTree

class BinaryTree<T: Comparable>{

var value:T

var left: Node<T>?

var right: Node<T>?

init(_ value:T, leftNode: Node<T>?, rightNode: Node<T>? ) {

self.value = value

self.left = leftNode

self.right = rightNode

}

}

extension BinaryTree: CustomDebugStringConvertible, CustomStringConvertible{

var description: String{

return "\(value) \(String(describing: left)) \(String(describing: right))\t"

}

var debugDescription: String{

return "\(description)"

}

}

extension BinaryTree{

func add(leftNode left: Node<T>) -> Void {

self.left = left

}

func add(rightNode right: Node<T>) -> Void {

self.right = right

}

}

extension BinaryTree{

func leftDeep<T: Comparable>(_ root: BinaryTree<T>?) -> Int {

let deep = 0

if root == nil {

return deep

}

var left = 0

var right = 0

if root?.left != nil {

left = leftDeep(root?.left) + 1

}

if root?.right != nil{

right = leftDeep(root?.right) + 1

}

return max(max(left, right),1) // 根节点算是一个层级

}

func rightDeep<T: Comparable>(_ root: BinaryTree<T>?)->Int{

return leftDeep(root)

}

func binaryDeep<T: Comparable>(_ root: BinaryTree<T>?)-> Int{

if root == nil{

return 0

}

let left = leftDeep(root?.left)

let right = rightDeep(root?.right)

return max(left, right) + 1

}

}

extension BinaryTree{

var leftDeep: Int{

return self.leftDeep(self.left)

}

var rightDeep: Int{

return self.rightDeep(self.right)

}

var deep: Int{

return binaryDeep(self)

}

}

链表ListNode

辅助定义

public class ListNode { public var val: Int public var next: ListNode? public init(_ val: Int) { self.val = val self.next = nil } } extension ListNode: CustomDebugStringConvertible, CustomStringConvertible{ public var description: String{ var items:[Int] = [Int]() var tmp: ListNode? = self while tmp != nil { items.append(tmp!.val) tmp = tmp!.next } return "\(items)" } public var debugDescription: String{ return "debug:\(description)" } } extension Array { var listNode: ListNode?{ var node: ListNode? var tmp: ListNode? for item in self as! [Int] { if node == nil { node = ListNode.init(item) tmp = node }else{ tmp!.next = ListNode.init(item) tmp = tmp?.next } } return node } }

leetcode:合并链表

func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? { var tmp1 = l1 var tmp2 = l2 var stepper = 0 var destListNode: ListNode? while tmp1 != nil || tmp2 != nil { var dest = 0 if(tmp1 != nil){ dest = dest + tmp1!.val tmp1 = tmp1?.next } if(tmp2 != nil){ dest = dest + tmp2!.val tmp2 = tmp2?.next } dest = dest + stepper print(dest) stepper = Int(dest / 10) if(destListNode == nil){ destListNode = ListNode.init(dest%10) if tmp1 == nil && tmp2 == nil { //没有后续x且需要进位 if stepper != 0 { destListNode!.next = ListNode.init(stepper) } } }else{ var tmp = destListNode while tmp?.next != nil { tmp = tmp?.next } tmp?.next = ListNode.init(Int(dest%10)) if tmp1 == nil && tmp2 == nil { //没有后续x且需要进位 if stepper != 0 { tmp?.next?.next = ListNode.init(stepper) } } } } return destListNode }

leetcode: 链表翻转

func reverseListNode(_ listNode: ListNode?)->ListNode?{ let tmpListNode = listNode if tmpListNode == nil { return listNode }else{ var currentNode = tmpListNode var nextNode = tmpListNode?.next currentNode?.next = nil while nextNode != nil { let tmp = nextNode?.next nextNode?.next = currentNode currentNode = nextNode nextNode = tmp } return currentNode } }

leetcode: 删除链表第k个节点

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? { var pre = head var current = head var index = n while index > 0 { pre = pre?.next index = index - 1 if pre == nil && index > 0 {//没有那么长 return head } if pre == nil{//刚好到头 current = current?.next return current } } while pre?.next != nil { current = current?.next pre = pre?.next } current?.next = current?.next?.next return head }

原文发布于微信公众号 - 大话swift(gh_ca2266b7cab0)

原文发表时间:2019-01-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券