Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 »  算法标签

取石子游戏

取石子是一种很有意思的游戏,一般给你若干堆石子,两个人根据指定规则轮流从中取若干石子,规定最后取光石子玩家获胜,假定双方玩家都采取最优策略,问先手是否有什么必胜策略。这个游戏看似简单,实则蕴含深刻的数学原理,本文将分析几种常见的取石子游戏的玩法。

继续阅读»

最远点对问题

二维平面上有n个点,怎么寻找距离最远的两个?
前面讨论过最近点对的问题,这里研究其相对的问题,虽然题目类似,但思想方法截然不同,本文将使用graham凸包扫描法和旋转卡壳算法进行求解。

继续阅读»

最近点对问题

二维平面上有n个点,怎么寻找距离最近的两个?
本文将实现一种O(nlogn)时间复杂度的分治算法,具体的思想方法参考了编程之美中寻找最近点对一章。

继续阅读»

外部排序

外部排序是指大量数据的排序,通常待排序的数据保存在外存储器上(比如硬盘),待排序的文件无法一次装入内存,需要在内存和硬盘之间进行多次数据交换,以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序,本文将通过具体的代码讲解一个简单的外部排序算法实现。

继续阅读»

LCA与RMQ互相转化

前面我们介绍过LCARMQ问题各自的解法,其实这两个问题非常类似,本质上是等价的。他们之间可以互相进行转化,并且复杂度不高,有时恰当的转化可以大大提升算法解决问题的性能,这里主要介绍二者之间互相转化的算法思想及核心代码实现。

RMQ问题的ST算法

RMQ问题(Range Minimum/Maximum Query,区间最值问题),是指给定一个长度为n的数列A,回答若干次询问RMQ(A,i,j)(i,j<=n)(通常次数非常巨大),每次返回数列A中下标在i,j里的最小(大)值。
RMQ问题解法很多,如朴素算法、线段树、ST算法RMQ与LCA互相转化等,不同算法思想及复杂度均有所差异。本文主要讲解其中非常高效的稀疏表算法(Sparse Table,ST算法)。

继续阅读»

LCA问题的跳表算法

LCA问题(Least Common Ancestors,最近公共祖先问题),是指给定一棵有根树T,给出若干个查询LCA(u, v)(通常查询数量较大),每次求树T中两个顶点u和v的最近公共祖先,即找一个节点,同时是u和v的祖先,并且深度尽可能大(尽可能远离树根)。
LCA问题有很多解法:线段树、Tarjan算法跳表RMQ与LCA互相转化等。本文主要讲解跳表算法的原理及详细实现,相对于Tarjan等算法而言,其不太为人所熟知,但同样是非常有效。

继续阅读»

LCA问题的Tarjan算法

LCA问题(Least Common Ancestors,最近公共祖先问题),是指给定一棵有根树T,给出若干个查询LCA(u, v)(通常查询数量较大),每次求树T中两个顶点u和v的最近公共祖先,即找一个节点,同时是u和v的祖先,并且深度尽可能大(尽可能远离树根)。
LCA问题有很多解法:线段树、Tarjan算法跳表RMQ与LCA互相转化等。本文主要讲解Tarjan算法的原理及详细实现。

继续阅读»

BFPRT算法

BFPRT算法是解决从n个数中选择第k大或第k小的数这个经典问题的著名算法,但很多人并不了解其细节。本文将首先介绍求解这个第k小数字问题的几个思路,然后重点介绍在最坏情况下复杂度仍然为O(n)的BFPRT算法。

继续阅读»

KM算法

KM算法是求一个二分图在完备匹配下的最大权匹配的算法,该算法是通过给每一个顶点标号将求最大匹配问题转化为求完备匹配的问题。
KM算法是在匈牙利算法基础上实现的,如果还未了解匈牙利算法及二分图相关概念,请先看匈牙利算法这篇文章。
继续阅读»

匈牙利算法

匈牙利算法是解决二分图最大匹配的经典算法,由匈牙利数学家Edmonds提出,核心是通过寻找增广路径以求得最大匹配。
本文将介绍匈牙利算法的思想及原理解释,最后提供一个C++代码实现。

继续阅读»

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论