QuickSort BinaryTree`s deep LeetCode~ListNode
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 }