算法

回溯法入门级讲解

说到回溯法,其实就是暴力搜索,并不是什么高效的算法,最多再剪枝一下。回溯算法能解决如下问题:(1)组合问题:N个数里面按一定规则找出k个数的集合(2)排列问题:N个数按一定规则全排列,有几种排列方式(3)切割问题:一个字符串按一定规则有几种切割方式(4)子集问题:一个N个数的集合里有多少符合条件的子集

上下界网络流总结

上下界网络流可以看做普通网络流的升级版,现在对于流量网络,我们不再只关注其流量的上界,而是同时关注流量的上下界。一、无源汇有上下界可行流这是上下界网络流中最简单的一种,给定一个没有源点和汇点、每条边的流量有上下界的流量网络,问是否存在一种可行流使得流量平衡。

最短路径,迪杰斯特拉(Dijkstra)算法及C/C++代码实现

1.何为最短路径最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径,大致可以分为如下几种问题,可无论如何分类问题,其本质思想还是不变的,即,求两点间的最短距离。a)确定起点的最短路径问题-即已知起始结点,求最短路径的问题。

区间DP实例讲解

一、什么是区间DP?顾名思义:区间DP就是在区间上进行动态规划,求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的DP算法。二、核心思路既然让我求解在一个区间上的最优解,那么我把这个区间分割成一个个小区间,求解每个小区间的最优解,再合并小区间得到大区间即可。

set theory(集合论)

1.集合论简介集合论,是数学的一个基本的分支学科,研究对象是一般集合。集合论在数学中占有一个独特的地位,它的基本概念已渗透到数学的所有领域。集合论或集论是研究集合(由一堆抽象物件构成的整体)的数学理论,包含了集合、元素和成员关系等最基本的数学概念。

递归算法概念与实例讲解

本篇主要是围绕着递归算法的概念、实质、思想以及设计要素四个方向叙述,同时通过实例讲解,促进大家对递归算法的理解。一、算法概念递归算法是一种直接或者间接调用自身函数或者方法的算法。说简单了就是程序自身的调用。二、算法实质递归算法就是将原问题不断分解为规模缩小的子问题,然后递归调用方法来表示问题的解。

在线算法和离线算法的区别

本章浅谈一下在线算法,当然,说到在线算法会想到离线算法,这两个概念都会提到,帮助大家理解。(一)在线算法在计算机科学中,一个在线算法是指它可以以序列化的方式一个个的处理输入,也就是说在开始时并不需要已经知道所有的输入。相对的,对于一个离线算法,

快速排序算法C/C++代码图文讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(nlogn)算法更快,因为它的内部循环(innerloop)可以在大部分的架构上很有效率地被实现出来。

DFS求有向图(无向图)两点间路径

本文会围绕算法中DFS求有向图或无向图两点间所有路径,先讲解DFS以及有向图或无向图的意思。有向图在图中的边是有方向的,表现出来就是有个箭头指示方向,节点只能单向通信或传递消息,相当于单行道,无向图边没方向是双向的,边连接的两个节点有通路可以双向通信,类似于双行道。

Boyer-Moore算法图文讲解

说到Boyer-Moore算法,它是一个字符串算法,这个算法追求的就是每次匹配,一般发现失败了,要往前移动尽可能多的距离,少算一点是一点。为了实现这个目标,首先算法选择的就是从pattern的尾部开始算。这个时候就会出现若干种情况。Boyer-Moore算法不仅效率高,而且构思巧妙,容易理解。