-w573

算法一撇之数据结构

算法是的基础应该是数据结构,适合的数据结构能优雅的解决问题。

数组

数组的最大优点是可以快速查询。数组最好的应用在于索引有语意的情况。

动态数组

数组的空间是有限的,那么如果增加或者删除的时候,开辟空间的长度不够或者多余的时候,应该怎么办呢?
一个直接的方法是。相应的把内存空间扩张或者收缩相应的倍数,一般可以设置为两倍。

动态数组的话,因为开辟的空间,每一次都需要将原本的数据复制到新的array上来。所以这个操作的复杂度是O(n)。

但是从概率上来说,你执行了n次操作之后才会有一次扩容操作。操作均摊下来,时间复杂度应该是 O(1)

当然还有一个极端情况下是。不断的添加和删除最后一个元素,同时触发扩容或缩容操作。这时候它的时间复杂度就会提升到 O(n)。出现这个问题的原因是我们在添加的时候立即进行了扩容,一个比较好的处理方法是:当开辟空间的时候,逻辑和原来不变,当超出内存空间的时候进行扩容;但是当删除元素的时候,只有在容量变为原来的1/4的时候才进行缩容。

链表 LinkedList

链表的优点是动态的容量和具有天然的递归性质,缺点也很明显是不适合有索引语义的情况,失去了随机访问能力。
这是什么意思呢?链表插入的复杂度是 O(1),但是查找的话就要从头遍历。

使用链表来实现栈

链表添加和删除节点的复杂度是 O(1),那么就很适合使用链表来实现栈的数据结构,这个实现和用 array 来实现没有复杂度的差异。

使用链表来实现队列

因为获取链表尾部要遍历所有元素,所以是耗时的,一个解决方法是再定义一个尾节点变量

但是一个操作,比如删除尾部节点也不简单,还是需要遍历

这时候换一个思路,我们把 tail 作为队尾,front 作为队首,这个队列变成从后指向前的 Node

链表是天生可以实现递归的结构

递归的本质是将原来的问题转化为更小的统一问题。
递归的优点是非常容易理解,而且在处理非线性问题的时候有自己的优势,他的缺点也同样很明显,就是会占用大量的系统资源。

思路通常是:

  1. 先找到最小的问题
  2. 尝试解决最小的问题
  3. 将最小的问题推广到原来的问题
  4. 链表的操作都可以尝试用递归实现

哈希表

牺牲了顺序性,节点的前驱后继。优点是很快,一般在语言里面会把类的地址作为哈希的值,在 swift 里面也是 class 会有 hashcode,但是 struct 没有,这时候要自己重写 Hashable。

处理的方法是将 Key 转换为索引:

  1. 对于小的数来说,直接作为索引
  2. 负数的话,可以全部增加一个正数
  3. 字符串可以对每个字符 * 26^(length - index) % M


【(避免整型溢出)】

对于特别大的数,可以 取模降低冲突的概率

链地址法

每个地址存一个查找表,可以是链表也可以是树。
链表在数据量少的话是很快的,如果量大的话可以考虑转为红黑树,不过这就会导致类型必须是可比较的

平均每个地址承载的元素多过一定量,就扩容。

-w573

这里又要涉及到扩容的情况,扩容的方式应该按照 M 为素数进行扩容

Queue

用数组队列的复杂度问题

如果使用数组队列来实现,那么在出队的时候所有的元素都要向前移动一位,就会造成不必要的操作。

但是其实出队之后,我们看数组里面的内容,他依然还是一个队列的形式,那么我们可以维护一个队首和队尾的变量。在入队的时候,如果队尾指针已经指向空间的尾部,那么就指向头部,从头部没有值的地方继续赋值。

直到 tail + 1 = header
之所以加一是因为我们约定 tail == header 的时候是队列空的时候

栈虽然简单,但是应用很多,比如:

  • 实现 Undo
  • 程序调用栈
  • 括号匹配

二叉树

应该是蛮常见的数据结构了,比如目录、文件夹结构、组织架构,应用很广:
比如:

  • 找一个比一个元素小或者大的值
  • 一个特定元素的 index,或者是 index 的元素是多少
  • rank
  • ceil
  • select

-w886

二分搜索

提到二叉树,不能不提到二分搜索,二分搜索要求元素是有序的,需要先进行排序。
应用包括:

  • floor
  • ceil

二分搜索树

更进一步是二分搜索树了,每个节点都:

  1. 大于左子树的所有节点的值
  2. 小于右子树的所有节点的值

也就是说,对于某个节点,你要查找小于它的值,就往左子树查找,不用管右子树,这就加快了查找速度
存储的数据必须有可比性,也就是实现 Equatable

通常二分搜索树不包含重复的元素,但是如果你想要包含重复的元素,可以在定义里面设置,比如左子数是小于等于节点或者是设定右子树是大于等于节点的情况。

二分搜索树的递归部分


根节点通常作为条件

    // 返回新插入节点后二叉树的根
    private func add(rootNode:Node?, value:T) -> Node {
        if let rootNode = rootNode {
            if value < rootNode.data {
                rootNode.left = add(rootNode: rootNode.left, value: value)
            }else if value > rootNode.data {
                rootNode.right = add(rootNode: rootNode.right, value: value)
            }
            // if value == rootNode.data pass
            return rootNode
        }else{
            size += 1
            return Node(value)
        }
    }

二分搜索树的遍历

这些遍历方式说白了是代表打印 根 Node 的位置

前序:

print(RootNode)
递归 Left Leaf
递归 Right Leaf

中序 —— 中序的一个特性是打印出来是有序的
递归 Left Leaf
print(RootNode)
递归 Right Leaf

后序:
递归 Left Leaf
递归 Right Leaf
print(RootNode)

遍历的操作实际上是对每个节点有个先后次序的排列,我们可以尝试用来处理

-w1040

BST的其他操作

1. 广度优先遍历(层序遍历)

更快的找到想要的解,深度优先遍历一下子就跑到太极端的情况

适合打印树的内容,处理最短路径

需要借助队列

也就是将子节点入队,然后出队,如果出队的节点有子孩那么子孩子入队。

2. 删除极值

最小值,也就是递归左子树
最大值,递归右子树

如果删除没有子节点 的节点,那么只需要将从父节点指向它的链接 指向nil。

如果待删除节点只包含一个子节点,那么原本指向它的节点就得做些调整,使其指向它的 子节点。

如果待删除节点包含两个子节点,正确的做法有两种:要么查找待删除节点左子树 上的最大值,要么查找其右子树上的最小值

    func removeMax() -> Node? {
        //get max 的作用是为了返回 remove 的值
        //否则在下一步操作中 最大值会被设为 nil
        let maxNode = getMax()
        //这里的递归是为了调整二叉树结构,在删除了最大值之后,最大值的左子树要调整到最大值的父节点,作为它的右子树
        root = removeMax(rootNode: root)
        
        return maxNode
    }
    // 用作调整树结构
    func removeMax(rootNode: Node?) -> Node? {
        if rootNode?.right == nil {
            let leftNode = rootNode?.left
            rootNode?.left = nil
            size -= 1
            return leftNode
        }
        rootNode?.right = removeMax(rootNode:rootNode?.right)
        return rootNode
    }
3. 删除任意值

如果删除没有子节点 的节点,那么只需要将从父节点指向它的链接 指向nil。
如果待删除节点只包含一个子节点,那么原本指向它的节点就得做些调整,使其指向它的 子节点。
如果待删除节点包含两个子节点,正确的做法有两种:要么查找待删除节点左子树上的最大值,要么查找其右子树上的最小值

Comments
Write a Comment