算法基础（二）数据结构

实习准备

字数统计: 2.2k阅读时长: 10 min

 2020/06/10 

算法基础（二）数据结构

链表

链表是由数据项组成的一个序列，其中每个数据项被称为节点。
链表有两种主要类型：

单链表 每一个节点只包含一个指向链表中下一个节点的指针（引用）。
双链表 每个节点包含两个指针（引用），一个指向前一个节点，一个指向后一个节点。

通常我们用head和tail指针来记录链表的头和尾。

代码实现

单链表

class ListNode {
    var value: Int
    var next: ListNode?
    
    init(_ value: Int) {
        self.value = value
        self.next = nil
    }
}

class List {
    var head: ListNode?
    var tail: ListNode?
    
    //尾插法
    func appendToTail(_ value: Int) {
        if tail == nil {
            tail = ListNode(value)
            head = tail
        } else {
            tail?.next = ListNode(value)
            tail = tail?.next
        }
    }
    
    //头插法
    func appendToHead(_ value: Int) {
        if head == nil {
            head = ListNode(value)
            tail = head
        } else {
            let temp = ListNode(value)
            temp.next = head
            head = temp
        }
    }
}

双链表

class DoubleNode {
    var value : Int
    var previous :DoubleNode?
    var next:DoubleNode?
    init(_ value :Int) {
        self.value = value
        self.previous = nil
        self.next = nil
    }
}

class DoubleNodeList{
    var head:DoubleNode?
    var tail:DoubleNode?
    
    func appendToTail(_ val:Int){
        if tail == nil {
            tail = DoubleNode(val)
            head = tail
        }else{
            let temp = DoubleNode(val)
            tail?.next = temp
            temp.previous = tail
            tail = temp
        }
    }
    
    func appendToHead(_ val:Int){
        if head == nil {
            head = DoubleNode(val)
            tail = head
        }else{
            let temp = DoubleNode(val)
            temp.next = head
            head?.previous = temp
            head = temp
        }
    }
}

题目练习

给出一个链表和一个值想，要求链表中小于x的值放在左边，大于等于x的放在右边，不改变原有链表
ex：1→5→3→2→4→2 x=3 结果 1→2→2→5→3→4

思路是：一个链表遍历时，小于x的放在一个链表，大于等于x的放在另一个链表，最后拼接。

func partition(head: ListNode?,_ x: Int) -> ListNode? {
    
    let prevDummy = ListNode(0)
    let postDummy = ListNode(0)
    var prev = prevDummy
    var post = postDummy
    var node = head
    
    while node != nil {
        if node!.value < x {
            prev.next = node
            prev = node!
        } else {
            post.next = node
            post = node!
        }
        node = node!.next
    }
    
    post.next = nil
    prev.next = postDummy.next
    
    return prevDummy.next
}

我们通常传入的参数是ListNode来代表单链表，处理室也能体现出优势，但是需要作出防止生成环的操作。

检测环的方法

这里使用一种方法叫快行指针，就是两个指针访问链表，一前一后。
这里其中的一个的速度是另外一个的两倍，当速度相等时，就说明链表有环了。

代码如下：

func isCycle(head: ListNode?) -> Bool {
    var slow = head
    var fast = head
    
    while fast != nil && fast?.next != nil {
        slow = slow?.next!
        fast = fast?.next!.next
        
        if slow == fast {
            return true
        }
    }
    return false
}

这里需要注意==的运算符，这需要ListNode遵循Equatable协议，那么我们让两个节点比较是否一样呢（不能是比较value），这里通过比较两个节点的内存地址是否相同，我更希望将比较做在ListNode中，让类实现协议并且在==函数中比较。

class ListNode: Equatable {
    
    static func == (lhs: ListNode, rhs: ListNode) -> Bool {
        
        if Unmanaged.passUnretained(lhs as AnyObject).toOpaque() == Unmanaged.passUnretained(rhs as AnyObject).toOpaque() {
            return true
        } else {
            return false
        }
    }
    
    var value: Int
    var next: ListNode?
    
    init(_ value: Int) {
        self.value = value
        self.next = nil
    }
}

例题分析（使用快行指针）

删除链表中倒数第n个节点。1→2→3 →4 →5 n=2 1→2→3 →5

思路：使用快行指针，但是这里速度不变，一个指在第一个节点，另一个指在第n个节点，这个指针指到最后时，前面一个指针则是要删除的节点。

代码如下：

func removeNode(head: ListNode?,backwards: Int) -> ListNode? {

    guard backwards > 0 else {
        return head
    }
    
    let dummy = ListNode(0)
    dummy.next = head
    var node1:ListNode? = dummy
    var node2:ListNode? = dummy
    //node2位移
    for _ in 0..<backwards {
        if node2 == nil {
            break
        }
        node2 = node2?.next
    }
    while node2?.next != nil && node2 != nil {
        node2 = node2?.next
        node1 = node1?.next
    }
    
    node1?.next = node1?.next?.next
    return dummy.next
}

这里使用到Dummy节点的概念，他的作用是作为一个虚拟的头前节点。可以避免处理头节点为空的边界问题。
前一个比较大小的题目我们也是用Dummy节点来优化代码。

栈和队列

在Swift中，没有内设的栈和队列，很多扩展库中使用Generic Type来实现栈和队列。正确的做法是用链表实现，这样可以保证加入或删除的时间复杂度是O(1)。这里推荐使用数组，因为Swift中有提供很多的数组的API可以直接使用。

这里对于栈和队列的概念不再介绍了，因为理解上没有什么突出的。我可以举几个在开发中的例子，APP中的添加撤销操作，栈是首选的数据结构

protocol Stack {
    associatedtype Element
	  //关联类型作为协议实现泛型的一种方式
    
    var isEmpty: Bool {get}
    var size: Int {get}
    var peek: Element? {get}
	  //栈顶元素
    
    mutating func push(_ newElement: Element)
    mutating func pop() -> Element?
    
}

struct IntegerStack: Stack {
    typealias Element = Int
    //可以用来对已有的类型进行重命名,这里便用于指明Element的类型

    var isEmpty: Bool
    
    var size: Int
    
    var peek: Int?
    
    private var stack = [Element]()
    
    mutating func push(_ newElement: Int) {
        stack.append(newElement)
    }
    
    mutating func pop() -> Int? {
        return stack.popLast()
    }
    
}

这里使用Protocol来制定出通用的栈结构，然后对于IntegerStack实现该协议，他在一定程度上优于继承机制，更具抽象化。

队列

队列是先进先出的结构，在iOS中，GCD和NSOperationQueue就是基于队列实现的。

protocol Queue {
    associatedtype Element
    
    var isEmpty: Bool {get}
    var size: Int {get}
    var peek: Element? {get}
    
    mutating func enqueque(_ newElement: Element)
    mutating func dequeque() -> Element?
}

struct IntegerQueue: Queue {
    typealias Element = Int
    
    var isEmpty: Bool {
        return left.isEmpty && right.isEmpty
    }
    
    var size: Int {
        return left.count + right.count
    }
    
    var peek: Element? {
        return left.isEmpty ? right.first: left.last
    }
    private var left = [Element]()
    
    private var right = [Element]()
    
    
    mutating func enqueque(_ newElement: Int) {
        right.append(newElement)
    }
    
    mutating func dequeque() -> Int? {
        if left.isEmpty {
            left = right.reversed()
            right.removeAll()
        }
        return left.popLast()
    }
    
}

例题分析

给出一个文件的绝对路径，要求进行简化，比如”/home/”，简化为”/home”，
“/a/./b/../c/”，简化为”/c”，也就是平常执行cd、pwd命令所得到的路径.

“.”代表当前路径，
“..”代表上一级目录。
这看上去没什么难度的，但是重视边界问题与异常情况。
这里的思路是根据”/”符号进行拆分，生成数组，用栈遍历数组，对于.忽略，对于..进行pop操作。
代码如下：

struct StringStack: Stack {
    var isEmpty: Bool = true
    
    var size: Int = 0 {
        didSet {
            if size == 0 {
                isEmpty = true
                peek = nil
            } else {
                isEmpty = false
                peek = stack.last
            }
        }
    }
    var peek: String? = nil
    
    private(set) var stack = [Element]()
    
    mutating func push(_ newElement: String) {
        stack.append(newElement)
        size = size+1
    }
    
    mutating func pop() -> String? {
        return stack.popLast()
        size = size-1
    }
    
    typealias Element = String
}


func simplifyPath(_ path: String) -> String {
    var pathStack = StringStack()
    let paths = path.components(separatedBy: "/")
    
    for path in paths {
        guard path != "." else {
            continue
        }
        if path == ".." {
            if pathStack.size > 0 {
                pathStack.pop()
            }
        } else if path != "" {
            pathStack.push(path)
        }
    }
    let result = pathStack.stack.reduce("") { (total, dir) in
        "\(total)/\(dir)"
    }
    return result.isEmpty ? "/" : result
}

二叉树

二叉树中，每个节点最多有两个子节点，一般称为左子节点和右子节点，并且二叉树有左右之分，次序不能颠倒
数据结构的代码如下：

class TreeNode {
    var value: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ value: Int) {
        self.value = value
    }
}

计算树的最大深度

在二叉树中，节点的层次从根开始定义，根为第一层，节点的最大层次为树的深度。

func maxDepth(root: TreeNode?) -> Int {
    guard let root = root else {
        return 0
    }
    return max(maxDepth(root: root.left), maxDepth(root: root.right))+1
}

使用递归算法在代码上最简洁，但是需要避免二叉树成环导致循环程序奔溃。

判断是否为二叉查找树

二叉查找树的特点在于左子树节点的值都小于根节点的值，右子树节点的值都大于根节点的值。

func isValidBST(root:TreeNode?) -> Bool {
    return checkBST(node: root, min: nil, max: nil)
}

private func checkBST(node: TreeNode?, min: Int?, max: Int?) -> Bool {
    guard let node = node else {
        return true
    }
    
    if let min = min,node.value <= min {
        return false
    }
    if let max = max,node.value >= max {
        return false
    }
    
    return checkBST(node: node.left, min: min, max: node.value) && checkBST(node: node.right, min: node.value, max: max)
}

二叉树本身是由递归定义的，所以，从原理上讲，所有二叉树的题目都可以用递归来解。
二叉树的题目很容易牵涉节点往左还是往右的问题，所以在内部函数时，要想要有两个对应的参数.

二叉树的遍历

最常见的树的遍历有三种，前序、中序和后序遍历，这里用非递归的方法写前序遍历，用栈来实现。

func preorderTRaversal(root: TreeNode?) -> [Int] {
    var result = [Int]()
    var stack = [TreeNode]()
    var node = root
    
    while !stack.isEmpty || node != nil {
        if node != nil {
            result.append(node!.value)
            stack.append(node!)
            node = node!.left
        } else {
            node = stack.removeLast().right
        }
    }
    
    return result
}

原文作者：Jonathan Lu

原文链接：https://jonathanlu98.github.io/2020/06/10/%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%EF%BC%88%E4%BA%8C%EF%BC%89%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/

发表日期：June 10th 2020, 8:55:23 pm

更新日期：October 5th 2021, 11:34:35 pm

Next Post

实习面试整理
Previous Post

算法基础（一）基本的数据结构（数组、集合、字典、字符串）

CATALOG

1. 算法基础（二）数据结构