数据结构和算法

1. 数据结构

• 物理数据结构

  • 数组

  • 链表

• 逻辑数据结构

  • 栈

  • 队列

  • 散列表（哈希表）

  • 树

  • 堆 （一棵完全二叉树）

  • 图

2. 算法

• 查找算法

  • 顺序查找

  • 二分查找

  • 插值查找

  • 斐波那契查找

  • 数表查找

  • 分块查找

  • 哈希查找

• 排序

  • 冒泡排序

  • 快速排序

  • 选择排序

  • 归并排序

  • 插入排序

  • 希尔排序

  • 堆排序

  • 桶排序/基数排序

数组和链表

数组: 内存中连续的一段存储空间。

链表: 链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

链表的优点： 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素； 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点： 因为含有大量的指针域，占用空间较大； 查找元素需要遍历链表来查找，非常耗时。

适用场景： 数据量较小，需要频繁增加，删除操作的场景

• 反转链表 - reverse linked list

def reverseList(self, head):
    cur, prev = head, None
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    return prev

• 链表交换相邻元素 - swap node

def swapPairs(self, head):
    pre, pre.next = self, head
    while pre.next and pre.next.next:
        a = pre.next
        b = a.next
        pre.next, b.next, a.next = b, a, b.next
        pre = a
    return self.next

• 探测环 - detect cycle 给定一个链表，判断链表中是否有环。

def hasCycle(self, head):
    fast = slow = head
    while slow and fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

堆栈和队列 (Stack、Queue)

https://www.bigocheatsheet.com/ leetCode-20 Valid Parentheses

def isValid(self, s):
    stack = []
    paren_map = {')':'(', ']':'[', '}':'{'}
    for c in s:
        if c not in paren_map:
            stack.append(c)
        elif not stack or paren_map[c] != stack.pop():
            return False
    return not stack

优先队列

正常入、按照优先级出 实现机制

1. Heap 堆

2. Binary Search Tree 二叉搜索树

哈希表

映射(Map) & 集合(Set) HashMap, TreeMap HashSet, TreeSet

树

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。

二叉树

节点度就是这个节点的孩子数量，例如有左右孩子的节点，它的度为2，如果只有左孩子或者只有右孩子的节点，它的度就是1，叶节点就是度为0的节点（没有孩子）。

满二叉树

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

如图所示

这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。

完全二叉树

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

二叉搜索树（Binary Search Tree）

也叫二叉查找树, 二叉搜索树是有数值的，二叉搜索树是一个有序树

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 它的左、右子树也分别为二叉排序树

下面这两棵树都是搜索树

平衡二叉搜索树 (AVL树)

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

如图:

二叉树的遍历方式

二叉树主要有两种遍历方式：

1. 深度优先遍历：先往深走，遇到叶子节点再往回走。

2. 广度优先遍历：一层一层的去遍历。

深度优先搜索 DFS (Depth-First-Search)

寻找最短路径

• 前序遍历（递归法，迭代法）

• 中序遍历（递归法，迭代法）

• 后序遍历（递归法，迭代法）

广度优先搜索 BFS (Breadth-First-Search)

寻找有没有路径

• 层次遍历（迭代法）

这里前中后，其实指的就是中间节点的遍历顺序, 前中后序指的就是中间节点的位置

看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

• 前序遍历：中左右

• 中序遍历：左中右

• 后序遍历：左右中

可以对着如下图，看看自己理解的前后中序有没有问题。

递归和分治

Recursion 递归 - 循环 通过函数体来进行的循环

分治 - Divde & Conquer

堆

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树。 将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。