网易笔试 求最长的连续整数片段长度

缘起

给你100,2,1,3 这样的正整数序列, 要你求最长的连续正整数的片段的长度. 答案是3（因为有1 2 3）

注意，如果是要求数字还相邻才能算连续的话, 则就是0，不过这样的话, 问题就很平凡了——O(N)时间内解决（逐个扫描，发现更大的就更新），不过这里也给出相应的算法（源码1）.

Read More

在线算法和离线算法

所谓在线算法指的是询问是实时的，即来一个询问，程序回答一个询问，而离线算法指的是，先把所有的询问收集起来，然后跑程序，一口气给出所有的解答

RMQ之线段树解法

缘起

RMQ问题（Range Minimum/Maximum Query）指的是对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题. 本文给出线段树解法.

Read More

RMQ

缘起

【1】中给出了RMQ的线段树解法. 这里给出RMQ的ST算法（sparse-table），不论是线段树还是ST都属于在线算法. 关于在线算法和离线算法，参见【2】

Read More

LCA

缘起

LCA问题，即最近公共祖先问题（lowest common ancestor）. 问题描述如下

1
对于一棵有根树T（不一定是二叉树哦）的任意两个节点u，v，求出LCA(T, u, v)，即离根节点root最远的节点x，使得x同时是u和v的祖先。

LCA问题其实非常有用. 你们在做WEB开发的时候用的各种树的插件（如jquery、ztree等），要快速确定两个节点的LCA才能进行绘图.

Read More