数据结构和算法

数组

连续的支持随机访问的数据结构，插入删除复杂度O(n)，随机访问复杂度O(1)

寻址公式：a[k]_address = base_address + k * type_size

链表

不连续的数据结构，通过指针连接节点，插入删除复杂度O(1)，随机访问复杂度O(n)

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

基础的几个算法

这几个要写的滚瓜烂熟

如果涉及到头节点可能改动的话添加一个哨兵节点

1 2	ListNode *dummy=new ListNode(-1); dummy->next=head;

LRU缓存淘汰算法

用双链表和哈希表实现，哈希表中存储双链表的节点

查找：从哈希表中找到双链表的节点，并把这个节点移动至双链表的头部，时间复杂度O(1)

删除：从哈希表中找到要删除的结点删除即可，时间复杂度O(1)

添加：先判断是否在缓存中，如果在的话就将其删除并重新添加至链表头部，如果不在的话再判断缓存是否已满，如果满了要把尾部节点删除再添加至头部，没满的话直接添加就可以了

class LRUCache {
public:
    struct Node {
        int key, val;
        Node *left, *right;
        Node(int _key, int _val): key(_key), val(_val), left(NULL), right(NULL) {}
    }*L, *R;
    unordered_map<int, Node*> hash;
    int n;
    void remove(Node* p) {
        p->right->left = p->left;
        p->left->right = p->right;
    }
    void insert(Node* p) {
        p->right = L->right;
        p->left = L;
        L->right->left = p;
        L->right = p;
    }
    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1, -1), R = new Node(-1, -1);
        L->right = R, R->left = L;
    }
    int get(int key) {
        if (hash.count(key) == 0) return -1;
        auto p = hash[key];
        remove(p);
        insert(p);
        return p->val;
    }
    void put(int key, int value) {
        if (hash.count(key)) {
            auto p = hash[key];
            p->val = value;
            remove(p);
            insert(p);
        } else {
            if (hash.size() == n) {
                auto p = R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }
            auto p = new Node(key, value);
            hash[key] = p;
            insert(p);
        }
    }
};

栈

先进后出的容器

stack<int> s;
s.push(i);//将元素i压⼊栈s中
s.pop(); // 移除栈顶元素
s.top()//s的栈顶元素
s.size()//s的元素个数

队列

先进先出的容器

queue<int> q;
q.push(i);//将i的值压⼊队列q中
q.pop(); // 移除队列的队⾸元素
q.front()//队首元素
q.back()//队尾元素
q.size()//队列的元素个数

排序算法

O(n^2^)的算法

冒泡排序

原地排序，稳定排序

插入排序

原地排序，稳定排序，但数据移动比冒泡排序的交换赋值操作要少，所以运行速度比冒泡快

选择排序

原地排序，不稳定排序

O(nlogn)的算法

归并排序

用二分法将数组二分至最小（1个或者两个），然后对每个数组进行排序，再不停合并数组（在合并过程中有序排列）

归并的难点不在于”归“，而在于”并“，这里是新建了一个tmp数组用双指针遍历两个数组每次放入较小的一个数，合并完成后再将tmp数组重新赋值回原数组

因为对值相同的数，是优先把第一个数组里的放入tmp，所以归并排序也是稳定的排序。很明显它并不是原地排序，但因为合并完数组之后tmp的内存空间就可以被释放，所以它的空间复杂度是O(n)

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

快速排序

选定一个数，然后把所有大于（小于）这个数的放到一边，再用递归分别对左右两边不停进行一样的操作即可。

用two pionts思想，指针从两端往中间走，遇到大于（小于）（不符合条件）的停下，然后交换两个指针对应的值继续走，代码模板如下

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

因为数据可能交换，所以快速排序不是稳定的排序，最坏的时间复杂度可能要到O(n^2^)，但通过原地分区，实现了原地排序，所以数据少的时候使用归并排序，时间复杂度稳定并且因为数据少也不会占用太多额外空间，数据大的时候再使用快速排序

原地分区是快速排序的核心，根据这个可以快速求出数组中第k小的数acwing786，每次要尽可能地使得两边分区的数量尽可能相同，可以使用三数取中法，每次取头、中、尾三个数，选择其中的中位数作为分区点

线性排序

主要用在一些场景上

桶排序

把数据按照数据大小的范围分成若干份，每份之中进行快速排序，再依次取出

适合用于外部排序（内存不足时可以把数据分成若干份一份一份排）

计数排序

统计相同元素的个数，顺序求和，这样就可以获得数据中小于等于某个数的数量，该数量也就是这个数的下标，获得下标后要将数量减去1，这样相同的数就排到一起了，依次获取一遍即可得到所有数的下标

适合用于数据范围不大的场景，比如高考分数排序，可以理解成特殊的每个桶里的数都相同的桶排序

基数排序

从最高位开始逐位排序，每一位的排序可以使用桶排序或者计数排序（必须是稳定的排序）

适合用于排序位数比较大的并且位数要一致（不一致的补0），比如10万个手机号码

二分算法

二分的核心思想是寻找一个边界，这个边界的一边满足这个性质另一边不满足

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;//注意这里有个+1
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

使用方式：1. 设置判别函数check 2.根据check的结果来查看区间更新方式 3.查看区间更新方式来决定是否要+1

旋转数组中的最小数字

跳表

redis中的数据结构，在有序链表上每两个结点提取一个到上一级，逐级建立索引，每次从最上面一层开始找，逐层往下找，类似于二分，插入、删除、查找的时间复杂度 O(logn)，相当于用空间换时间，空间复杂度O(n)，插入后需要动态更新，通过一个随机函数决定它被放入哪一层的索引

散列表

基于数组的随机访问特性，把key转化为数组下标去访问value，这个转化函数称为散列函数，散列函数要求生成的值要尽可能随机并均匀分布。插入、删除、查找时间复杂度都是O(1)，但数据会被散列函数打乱，经常与双向链表（跳表）共同使用以实现有序，如LinkedHashMap

unordered_map<string, int> m;
m[key]=value;
m.size()//元素的个数
m.erase(key);//删除键为key的元素
m.count(key)//键为key的元素个数（只可能是0或者1）

装载因子

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度，装载因子越大，哈希表性能越差，装载因子过大时要动态扩容，过小的话也可以动态缩容，一次性动态扩容消耗太大，可以把动态扩容操作分散到插入操作中，每插入一个数据转移一次数据，多次插入后就实现了数据扩容，

哈希算法

将任意长度的二进制值串映射为固定长度的二进制值串

散列冲突

不同的key值通过散列函数得到相同的下标，解决方法：

开放寻址法

如果发现存储空间已被占用，就寻找下一个可用的空间，寻找方式可以顺序，可以跳跃

序列化容易，删除麻烦，装载因子不能太大，当数据量比较小、装载因子小的时候，适合采用开放寻址法，如Java 中的ThreadLocalMap

链表法

每个节点都对应一个链表，相同hash值的元素会放到同一个链表中

对内存的利用率高，装载因子上限大（甚至能大于1），适合存储大对象、大数据量的散列表，也可以把链表换成红黑树来优化

字符串哈希

把字符串当成一个p进制的数并mod一个q，就是字符串的哈希值（p一般取131，q取2^64^，也可以使用unsigned long long类型存储，这样就会自动mod 2^64^）

先预处理字符串中所有前缀的哈希值存入h数组，这样[l,r]之间的字符串的哈希值就等于h[r]-h[l-1]*p^r-l+1^

二叉树

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

遍历的时间复杂度是O(n)

二叉查找树

左节点<根节点<右节点

查找：先取根，如果比根小就递归左边，如果比根大就递归右边

插入：如果要插入的数据比节点的数据大，并且节点的右子树为空，就放在右边，否则递归右子树，左子树同理

删除：如果没有子节点，直接让指针指向null，如果只有一个，让父节点指向这个子节点

如果有两个子节点，找到这个节点的右子树中的最小节点，把它替换到要删除的节点上，然后再删除掉这个最小节点

中序遍历二叉查找树就可以得到有序的序列，时间复杂度O(n)，平衡二叉树的查找、插入、删除复杂度都是O(logn)

红黑树

一种近似平衡二叉树（左子树和右子树高度相差不超过1，高度接近logn）

根节点是黑色的
每个叶子节点都是黑色的空节点（NIL）
任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的
每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点

维持平衡的操作：左旋、右旋、改变颜色

B+树

对有序数据用m叉树建立索引，m的值取决于硬盘一页的大小，这样每访问一个节点就相当于访问一页硬盘，只需要一次IO，适合储存在硬盘中，MySQL的索引

每个节点中子节点的个数不能超过 m，也不能小于 m/2，如果超过就进行分裂，如果小于就进行合并；
根节点的子节点个数可以不超过 m/2，这是一个例外；
m 叉树只存储索引，并不真正存储数据，这个有点类似跳表；
通过链表将叶子节点串联在一起，这样可以方便按区间查找；
一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。

堆

一颗完全二叉树（除了最后一层都是满的，最后一层靠左边），根节点的值大于左右节点

堆化：从一个节点开始，从下往上或者从上往下，如果不满足条件就交换父节点和子节点，时间复杂度O(logn)

插入：把插入的元素放到最后，然后从这个元素开始从下到上堆化

删除：把最后一个元素放到删除元素的位置，然后从这个位置开始从上往下堆化

priority_queue<typename> q;//默认是大根堆
priority_queue<int,vector<int>,greater<int>> minheap;//这样可以生成小根堆
q.push(x);//插入x并自动排序
q.pop();//弹出队头元素
q.top()//访问队头元素
q.empty()//返回是否为空

堆排序

建堆：方法一：从第一个元素开始依次执行插入操作；方法二：把所有非叶子节点（有子节点的节点）从上往下堆化一遍
排序：把堆顶元素与最后一个元素交换，然后n-1个数重新堆化，重复该过程n次即可

堆排序因为涉及到元素交换，所以不稳定，它是原地排序，时间复杂度O(nlogn)，但因为访问数组下标跳跃，并且要多次交换数据，所以实际使用性能不如快速排序

利用堆求中位数

剑指offer41

图

由节点和边组成的数据结构，分为无向图（边没有方向），有向图（边有方向），带权图（边有权重）

邻接矩阵

用一个n*n的二阶矩阵存储（n为节点数），横纵坐标分别表示两个点，如果连接着就把值设为1或者权重，用坐标的先后顺序表示有向性

邻接表

用一个带链表的哈希表存储每个节点，链表里存储每个节点连接的节点，如果是有向图，就存储指向的节点

邻接表比邻接矩阵占用空间少，但更耗时间

Trie树

通过树的形式存储字符串，公共的前缀为根节点