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

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算法。

继续阅读»

C++类型转换

类型转换可以将一种类型的数据转化为另一种类型的数据以满足精度或者其他方面的要求,是程序设计过程中经常遇到的问题。
C++在C语言的类型转换基础上添加了很多新的特性,可以更清晰地表明程序员的意图,以及进行更安全的转换,需要根据不同的场景适当地选择使用。本文主要介绍C和C++中关于类型转换的相关内容。这里主要关心显示的强制类型转化,隐式类型转换由编译程序按照一定规则自动完成,而不需人为干预,较危险的转换通常伴有警告提醒,唤起程序员的注意。

继续阅读»

并查集及其在最小生成树中的应用

并查集是一种用途广泛的数据结构,能够快速地处理集合的合并和查询问题,并且实现起来非常方便,在很多场合中都有着非常巧妙的应用,。
本文首先介绍并查集的定义、原理及具体实现,然后以其在最小生成树算法中的一个经典应用为例讲解其具体使用方法。

继续阅读»

二分查找

二分查找是一种经典的算法,是每个程序员的入门内容之一,但是根据《编程珠玑》上面介绍,90%的程序员写的二分查找的程序中有bug,并且他并不认为没有bug的代码就是正确的。
可见二分查找是比较考验程序员的编码基本功的。那么如何查找数组中一个元素是否存在并且如何找出其第一次或最后一次出现的位置呢?本文接下来将对这个问题进行仔细分析并提供相应的代码。

继续阅读»

CPU占用率正弦曲线

编程之美上有这么一道题:写一个程序,让用户来决定Windows任务管理器(Task Manager)的CPU占用率。程序越精简越好,计算机语言不限。例如,可以实现下面三种情况:

继续阅读»

快速排序的实现与应用

快速排序(Quick Sort)是一种非常经典高效的排序算法,采用了基于比较的递归分治策略,平均情况下复杂度为O(nlogn),但最坏情况会退化到O(n^2)。
在笔试面试过程中经常会有关于快速排序的问题,甚至要求面试者当场手写代码,本文将简单介绍快排原理并提供具体的代码实现,以及其在求第n小的数中的经典应用。

继续阅读»

在Visual Stuido中使用DLL

前面在在Visual Stuido中创建DLL这篇文章中介绍了如何在Visual Studio中创建自己的DLL,本文将继续讨论如何在Visual Studio中调用自己新建的DLL或者使用别人提供的DLL。
由于DLL调用有显示调用和隐式调用之分,适用于不同情况的需求,以下将分别进行详细介绍。

继续阅读»

在Visual Stuido中创建DLL

DLL(Dynamic Link Library,动态链接库)是Windows中一个包含可由多个程序同时使用的代码和数据的共享库,是实现代码复用提高软件开发效率的重要途径。Linux下等价的概念称为so(share object)文件,本文主要关注Windows方面的内容。

继续阅读»

C/C++中的预编译指令

程序的编译过程可以分为预处理、编译、汇编三部分,其中预处理是首先执行的过程,预处理过程扫描程序源代码,对其进行初步的转换,产生新的源代码提供给编译器。
预处理过程读入源代码之后,会检查代码里包含的预处理指令,完成诸如包含其他源文件、定义宏、根据条件决定编译时是否包含某些代码的工作。下面介绍一些C/C++中预编译的指令。

继续阅读»

我的博客

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

站内搜索

最新评论