算法

前缀和理解与应用

本篇内容主要学习前缀和与其应用。一、前缀和概念前缀和是指某序列的前n项和,可以把它理解为数学上的数列的前n项和,而差分可以看成前缀和的逆运算。合理的使用前缀和与差分,可以将某些复杂的问题简单化。简单来说:我们有一个数组x和它的前缀和数组y,他们满足以下公式。

什么是拓扑排序?

拓扑排序的英文名是Topologicalsorting。拓扑排序要解决的问题是给一个图的所有节点排序。一、什么是拓扑排序在图论中,拓扑排序(TopologicalSorting)是一个有向无环图(DAG,DirectedAcyclicGraph)的所有顶点的线性序列。

归并排序算法C/C++代码图文讲解

归并排序算法是在分治算法基础上设计出来的一种排序算法,它可以对指定序列完成升序(由小到大)或降序(由大到小)排序,对应的时间复杂度为O(nlogn)。(1)算法思路归并排序算法实现排序的思路是:1.将整个待排序序列划分成多个不可再分的子序列,

什么是字符串(str)?

其实说到字符串,这个概念没有具体的说法,但是我们根据平时的归纳总结,也能一段,便于大家理解,字符串就是把字符连在一直,串成一串又一串;字符串内可以包含数字、字母、特殊符号等所有内容;在Python中只要对一些内容加上对双引号或一对单引号,就默认为是字符串;(三对单引号或三对双引号可以写多行字符串)。

最小生成树,普利姆(Prim)算法及C/C++代码实现

1.最小生成树(又名:最小权重生成树)概念:将给出的所有点连接起来(即从一个点可到任意一个点),且连接路径之和最小的图叫最小生成树。最小生成树属于一种树形结构(树形结构是一种特殊的图),或者说是直链型结构,因为当n个点相连,且路径和最短,那么将它们相连的路一定是n-1条。

简述LGV引理

LGV引理可以用于在DAG上求解不相交路径方案数问题,下面我们简单介绍一下。一、简介LGV引理英文全称是Lindström–Gessel–Viennotlemma,可以用来处理有向无环图上不相交路径计数等问题。在此之前,大家要先了解图论相关概念、矩阵、高斯消元求行列式等知识,

C++STL之Map容器

1.简介Map也是一种关联容器,它是键—值对的集合,即它的存储都是以一对键和值进行存储的,Map通常也可以理解为关联数组(associativearray),就是每一个值都有一个键与值一一对应,因此,map也是不允许重复元素出现的。同时map也具备set的相关功能,

各种排序算法总结

1.排序汇总类别排序方法时间复杂度空间复杂度稳定性平均情况最好情况最坏情况插入排序直接插入O(n^2)O(n)O(n^2)O(1)稳定希尔排序O(n^2)O(n)O(n^2)O(1)不稳定选择排序直接选择O(n^2)O(n^2)O(n^2)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlo

DAG上的DP实例讲解

DAG是学习动态规划的基础,(DAG:有向无环图。)很多问题都可以直接转化为DAG上的最长路、最短路或路径计数问题。两个经典的DAG模型,嵌套矩形和硬币问题。一、嵌套矩形(1)第一个DAG模型:矩形嵌套问题描述:有n个矩形,每个矩形可以用a,b来描述,表示长和宽。

数据结构的特点

本篇我们来总结一下数据结构的特点,帮助大家更好的运用。1、数组数组使用下标查找十分迅速,但计算机内存有限,故数组的长度有限,数组初始化就需要声明数组的长度。实际应用当中的数据往往十分庞大;无序数组的查找最坏情况需要遍历整个数组;后来人们提出了二分查找,