学习并查集这种数据结构,进行集合的存储、合并与查找,解决连通性问题

并查集


  • 并查集

    1、并查集是一种支持合并和查询操作集合形式的数据结构,它支持两个集合的合并,并可以查询点与点之间连通关系
    2、并查集只需要一个数组pre[]存储点的前导点(父节点),在初始化pre[i] = i,表示点与自己连通,是单独的连通块,该功能由init()函数完成。并查集中还需要一个函数root(u),该操作将找到点 u 所属的连通块(的根节点)。该函数将递归查找 u 的父节点,直至找到根节点
    3、对于两个点 u 和 v合并操作,只需要将u 和 v 所属的连通块其中一个根指向另一个根即可,如pre[root(u)] = root(v);对于两个点 u 和 v查询操作,只需要判断u 和 v 所属的连通块根是否相同即可
    4、但前述root(u)函数的朴素算法每次都需要查找一整条父节点,效率太低,可以通过路径压缩优化程序:pre[u] = (pre[u] == u ? u : root(pre[u])),这样同一连通块第一次查找后每个节点都将直接指向当前根节点,提高以后查找的效率

阅读更多
C++并查集

学习树状数组,学习区间查询、单点修改和区间修改操作,使用树状数组来维护区间和

树状数组


  • 树状数组

    1、树状数组常用于维护区间和,有以下操作:单点修改O(log n),区间修改O(log n),区间查询O(log n)
    2、树状数组结构如下图,注意树状数组中一定不能用下标 0T[i]所存的值为管辖区间的和T[i]所覆盖的管辖区间[i - lowbit(i) + 1, i]管辖区间长度lowbit(i)
    3、lowbit(i)表示 i 的二进制只保留最后一位 1的结果(例如二进制1101100只保留后三位变为100),公式为lowbit(x) = x & -x

阅读更多
C++树状数组

学习并使用单调栈、单调队列。单调栈常解决距离最近的较大较小值问题,单调队列常用于解决滑动窗口问题及优化DP

单调栈


  • 单调栈

    1、在的基础上,如果保持栈内元素有序的,则称为单调栈,分为单调递增栈单调递减栈
    2、通常单调栈主要用于求位置最近更大值更小值,我们将在具体样例中分析

阅读更多
C++单调栈单调队列队列

贪心算法是十分常见的算法,一般写法简单,但正确性难以证明,比较感性

贪心算法


  • 适用前提

    1、简言之:可以找到一个局部最优解;可以从局部最优解推广到全局最优解
    2、严谨地说,两个条件分别是最优子结构贪心选择性质
    3、一般来说,贪心法往往是将某个东西排序,或者用(优先队列)等数据结构,每一步都取局部最优解,进而得到全局最优解

阅读更多
C++贪心

入门图这种数据结构,学习图的存储,学习 BFS、DFS 进行遍历搜索,学习回溯和剪枝,权值相等最短路

图的存储


  • 邻接表

    1、在计算机中,图的存储方式多种,最常用的是邻接表邻接矩阵邻接矩阵由于适用范围很小,故一般不考虑这种写法
    2、出度:如下图便是一幅有向图,其中一个节点指向的其他节点称为这个节点的出度指向出度节点的路径称为这个节点的出边。如下图中 2、5 为 1 的出度
    3、邻接表:就是将一个点的所有出点(邻接点)保存在一个数组中;拓展的过程,也就是遍历这个数组的过程。这个数组我们称为邻接表

阅读更多
C++DFSBFS回溯剪枝

使用质数筛快速判断质数,掌握埃氏筛和欧拉线性筛的思路和代码实现

素数判断


  • 素数判断

    1、最简单的判断质数的方式,便是从 2~x 依次尝试,如果尝试到有因子,则其不是质数。需要特判 2 为质数小于 2 的都不是质数(质数范围是大于 1 的自然数)
    2、朴素筛法可以简单进行优化,实际需要尝试的因子最多只到sqrt(x)。比如判断 25 时,易知只需要判断 2~5 有没有因子,因此不需要重复判断大于sqrt(x)的因子。提前使用变量记录sqrt(x),可以避免循环中重复计算sqrt的开销
    3、但假如要计算 2 ~ 106有多少个质数时,只使用素数判断效率很低(106 - 218ms),其额外判断了大量无用的数据,所以需要效率更高的筛法

阅读更多
C++数学质数筛

学习构建和使用二叉查找树,再进一步学习 AVL 树。了解哈夫曼树和哈夫曼编码

二叉查找树


  • 二叉查找树

    1、二叉查找树:又称二叉排序树/二叉搜索树,其任意节点与其左右子节点大小关系都有左 < 中 < 右,其中序遍历会得到一个递增序列,常用于元素的排序和查找,如下图
    2、查找元素二叉查找树是以二分查找为原型的数据结构,因此其查找操作时间复杂度为 O(log2n)。其查找元素的动作为从根节点起,如果要查找的值比根小,则继续查找左子树,否则查找右子树
    3、插入元素:与查找元素类似。如在下面的二叉查找树插入新元素 12,应放在元素 11右子节点处(从根节点依次比较 12 与 10、13、11 的关系)
    4、删除元素:实质是保持中序遍历(即递增序列)的顺序不变从中删除节点,重点在于如何填补空缺。如下图展示了三棵二叉树,分别代表三种删除情景情景一要删除节点 6(只有一边子树),可以直接将子树整体上移情景二要删除节点 7(两边都有子树),可以将其中序遍历前/后一个节点(即节点 6 或 8)填充到此处;情景三要删除节点 10,如果选择填充节点 14(其仍有子树),则还应递归处理 14 的空缺(按照前两种情景选择方法处理)

阅读更多
C++二叉查找树AVL树哈夫曼树

学习树这种数据结构,学习二叉树的遍历、构造等实现,学习线索二叉树

树的知识


  • 认识树结构

    1、:指有层次关系N 个节点有限集合(如下图);对于空树N = 0;对于非空树,有且仅有一个根。除外,可分为多个互不相交有限集合,称为子树
    2、节点:每个数据就是一个节点节点可分为分为根节点分支节点叶子结点。在两个节点的关系上分为前驱(父节点)和后继(子节点)
    3、在树中用来表明两个节点之间的层次关系(父子关系);高度指的是深度(层次),树的高度指的是整个树最深的层次数,如下图E 的高度为 3树的高度为 4指的是边的个数(子节点的个数),树的度指的是整个树各节点度的最大值,如下图A 的度为 3C 的度为 1树的度为 3

阅读更多
C++二叉树