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

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

继续阅读»

二分查找

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

继续阅读»

快速排序的实现与应用

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

继续阅读»

哈夫曼编码

哈夫曼编码(Huffman Coding)是一种非常经典的编码方式,属于可变字长编码(VLC)的一种,通过构造带权路径长度最小的最优二叉树以达到数据压缩的目的。
哈弗曼编码实现起来也非常简单,在实际的笔试面试过程中有可能会遇到,本文主要介绍具体的编码原理,以及使用STL的优先队列进行实现。

继续阅读»

位运算应用技巧(2)

位运算可以直接操作计算机内存中整数的二进制位,运行效率很高,而且在代码中巧妙地使用位运算能使程序变得迷人,彰显编程的魅力。
这里介绍一些比较常用的位运算技巧,分为两个部分,本文主要介绍一些综合运用的方法。

继续阅读»

位运算应用技巧(1)

位运算可以直接操作计算机内存中整数的二进制位,运行效率很高,而且在代码中巧妙地使用位运算能使程序变得迷人,彰显编程的魅力。
这里介绍一些比较常用的位运算技巧,分为两个部分,本文主要介绍一些基本概念及简单应用。

继续阅读»

我的博客

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

站内搜索

最新评论