一、背景 朴素的求幂时间复杂度为O(n),对于一些较大的数据，其运行效率不理想。 而快速幂，其时间复杂度为O(logN),大大提高了运行效率。 二、原理 首先我们需要将幂转换...
IP属地：甘肃
-
快速幂
-
Python编程第七、八章重点
1.Input()的工作原理 1.1 input()函数让程序暂停运行，等待用户输入一些文本。获取用户输入后，Python将其存储在一个变量中，以方便使用。 如：messag...
-
Python编程第五、六章重点
1.基本语法 1.1 if,else后面都要加：，用缩进区分模块。1.2 c语言中的逻辑运算符'&&'，'||'等，在python中用and,or表示。1.3 python用...
-
Python编程第三、四章重点
1.列表介绍 1.1 列表：由一系列按特定顺序排列的元素组成。1.2 可以将任何东西加入列表，其中的元素之间可以没有任何关系。1.3 [ ]来表示列表，并用逗号来分隔其中的元...
-
Python编程第二章重点
1.变量 1.1 定义变量不需要定义类型。1.2 单引号，双引号没区别。1.3 strip()方法删除空格。 2.数字 2.1 表示乘方运算。如：32=92.2 str()方...
-
质数筛选
1、埃式筛法： 1.1 思路 从2开始遍历所有数字，将没有标记的数字作为质数。同时在遍历的时候，如果该数字是质数，则需要将该质数的所有倍数进行标记。 1.2 代码 2、线性筛...
-
二分图
1、二分图定义 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i ...
-
最小生成树
1、prim算法 1.1 思想 prim算法思想与dijkstra算法类似：区别就是prim算法中的距离数组表示的是该点到已确定集合最近的距离；而dijkstra算法中表示的...
-
SPFA算法
1、bellman-ford算法 spfa算法由bellman-ford算法优化而来。bellman-ford算法可以用来求权值为负的最短路，同时也可以求有边数限制的最短路。...
-
Dijkstra算法
1、思想 核心是贪心算法。每次取还未确定的点中，到源点距离最短的点。然后比较原来到所有点的距离与经过该点后的距离的大小，不断循环，直到所有点都被确定。 2、步骤 1.首先需要...
-
有向图的拓扑排序
1、题目 给定一个n个点m条边的有向图，点的编号是1到n，图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。若一个由图中所有点构成的序...
-
图的存储——邻接表
1、邻接表与邻接矩阵 1.1 图的存储方式 一般分为邻接表和邻接矩阵邻接矩阵：就是用横纵坐标来表示不同结点的编号，矩阵中的值(0,1)表示两个结点间是否相连。这样空间复杂度就...
-
堆
1、性质 1.1 堆中某个节点的值总是不大于或不小于其父节点的值；(最小堆，最大堆)1.2 是一棵完全二叉树。 2、基本操作 2.1 down操作： 2.2 up操作： 3、...
-
并查集
1、概念 1.1集合 并查集是一个集合，它把所有具有相同属性的元素放在一个集合中。在查找两个元素是否具有相同属性时，只需要查看他们的所在的集合是否相同就可以了。但如果用正常的...
-
Trie树
1、Trie树的作用 最大限度的利用字符串的公共前缀来减少查询时间。 2、Trie树的基本操作 这里我们可以用数组来模拟单链表构造Trie树。 2.1插入 思路：逐位遍历字符...
-
KMP算法
1、朴素的字符串匹配算法 它是通过一个循环找到所有有效偏移，最坏情况的时间复杂度为O((n-m+1)m)。 2、KMP算法 该算法是由Knuth、Morris和Pratt三个...
-
滑动窗口
1、题目 给定一个大小为n≤106的数组。 有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。 您只能在窗口中看到k个数字。 每次滑动窗口向右移动一个位置。 您的任务是...