一点一点了解S4

1.支持为【S 备忘录】设置密码

操作:应用程序-S备忘录-长按住需要加密的备忘录-选择锁定-设置新密码并保存。
文章分类 未分类

RMQ(区间最值查询) And LCA(最近公共祖先)

以前上大学的时候,解决RMQ只会ST算法,LCA就转成RMQ来做。今天无聊打算学习下笛卡尔树,也顺便复习下RMQ,找到此文,敬仰之情,滔滔不绝,特别是最后的解决RMQ的预处理O(n),查询O(1)的解法。

另外本文并未介绍解决LCA的离线算法tarjan

转自:http://blog.csdn.net/hell2pradise/article/details/5815959

英文原帖地址:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_%28RMQ%29

RMQ(Range Minimal Query)问题

给定一个数组A[1..N],RMQ(A,i,j)就是A[i..j]的最小值的下标。

From TopCoder

朴素的RMQ在线算法O(N2)-O(1)

逐一计算出每一对(i,j)的值,存储在NXN的数组M中,算法复杂度为N*N2=N3。利用动态规划,可以降低到O(N2)。

  1. void
  2. rmq_dp(int a[],int m[][MAXN],int n)
  3. {
  4.     int i,j;
  5.     for(i=0;i<n;i++)
  6.         m[i][i]=a[i];
  7.     for(i=0;i<n;i++)
  8.         for(j=i+1;j<n;j++)
  9.             m[i][j]=a[m[i][j-1]]>a[j]?j:m[i][j-1];
  10. }

时空复杂度均为O(N2)。

O(N)-O(sqrt(N))的一种解法

将数组按照每段的大小为sqrt(N)(向下取整)进行分段,则一共有sqrt(N)(向上取整)段

From TopCoder

用M[0..sqrt(N)]保存每一段的最小值,复杂度为O(N)。

查询的过程先求出i,j所在段x,y

RMQ(i,j)=M[x]                    x==y

RMQ(i,j)=Min{A[i..sqrt(N)+i-1],M[x+1..y-1],A[y*sqrt(N)..j]}                        x!=y

元素个数最多不超过3sqrt(N)

Sparse Table algorithm(ST算法)O(N*logN)-O(1)

实际上也是一种DP算法,用m[i][j]来表示从下标i开始,长度为2j的子数组的最小值,数组大小只需要m[0..N-1][0..logN]

DP状态转移方程为

M[i][j]=A[i]                                                                       j=0

M[i][j]=Min{A[M[i][j-1]],A[M[i+2j-1][j-1]]}                        j>0

  1. void
  2. rmq_st(int a[],int m[][LOGMAXN],int n)
  3. {
  4.     int i,j;
  5.     for(i=0;i<n;i++)
  6.         m[i][0]=a[i];
  7.     for(i=0;i<n;i++)
  8.         for(j=1;i+(1<<j)-1<n;j++)
  9.             m[i][j]=a[m[i][j-1]]<a[m[i+(1<<(j-1))][j-1]]?m[i][j-1]:m[i+(1<<(j-1))][j-1];
  10. }

查询的过程需要找到能够将区间[i,j]覆盖但是又不能越界的两个m区间,采用的方法是

m[i][k]为从i开始长度为2k的区间,m[j-2k+1][j]为以j结束长度为2k的区间

需要的条件是j>=i+2k-1>=j-2k+1

故取k=log(j-i+1)

取a[m[i][k]]和a[m[j-2k+1][k]]中的较小的值的下标即为RMQ(i,j)

Segment trees 线段树 O(N)-O(logN)

解决RMQ问题也可以用Segment trees,Segment trees是一种类似堆的数据结构,定义如下

[0,9]的segment trees如下图所示

segment trees可以采用heap的数据存储结构,节点node的左儿子为节点2*node,右儿子为2*node+1

类似堆,可以用数组M[1..2*2logN+1]来表示,对于RMQ问题,存储的区间信息就是该区间的最小值

segment trees的一个建立过程:初始调用应该是 segtree_init(1,0,N-1,m,a)

  1. void
  2. segtree_init(int node,int b,int e,int m[],int a[])
  3. {
  4.     if(b==e)
  5.         m[node]=b;
  6.     else{
  7.         segtree_init(node*2,b,(b+e)/2,m,a);
  8.         segtree_init(node*2+1,(b+e)/2+1,e,m,a);
  9.         m[node]=a[m[node*2]]<a[m[node*2+1]]?m[node*2]:m[node*2+1];
  10.     }
  11. }

查询过程

  1. int
  2. seg_query(int node,int b,int e,int i,int j,int m[],int a[])
  3. {
  4.     int p1,p2;
  5.     if(i>e || j<b)
  6.         return -1;
  7.     if(i<=b && j>=e)
  8.         return m[node];
  9.     p1=seg_query(node*2,b,(b+e)/2,i,j,m,a);
  10.     p2=seg_query(node*2+1,(b+e)/2+1,e,i,j,m,a);
  11.     if(p1==-1)
  12.         return p2;
  13.     if(p2==-1)
  14.         return p1;
  15.     return a[p1]<a[p2]?p1:p2;
  16. }

比较次数为O(logN)

Lowest Common Ancestor (LCA问题) 这里讨论的都是在线算法

 一个分段解法 O(N)-O(sqrt(N))

以sqrt(H)为大小进行分段,H为树的高度,例如

用一个深度优先遍历的顺序来预处理每个节点i

对于第一段所有的节点i,祖先是节点1,置P[i]=1

后面的每一段的最上层的节点,即深度最低的节点i,P[i]=father[i],其他层次的节点i,P[i]=P[father[i]]

这样预处理后,每个节点都指向上一段的最低一层,即深度最高的祖先节点,对于P[i]=P[j],节点i,j的LCS一定是P[i]或P[i]的子节点

这样,如果要查询的两个节点 (x,y) 如果P[x]=P[y] ,那么最多进行O(sqrt(H))次查询即可得到

[c-sharp] view plaincopy
  1. while(x != y)
  2.     if (L[x] > L[y])
  3.        x = T[x];
  4.     else
  5.        y = T[y];
  6. return x;

对于P[i]!=P[j]的,进行O(sqrt(H))次处理,使得P[x]=P[y] ,继续用上面的代码进行查询

  1. while (P[x] != P[y])
  2.     if (L[x] > L[y])
  3.          x = P[x];
  4.     else
  5.        y = P[y];

一共需要2*sqrt(H)次操作,最坏情况下H=N,算法最坏情况下的复杂度为O(sqrt(N))

另外一种简单的解法 O(NlogN)-O(logN)

仍然是DP,设P[i][j]为节点i的第 2j 个祖先,那么有状态转移方程

P[i][0]=father[i]

P[i][j]=P[P[i][j-1]][j-1]     j>0

用2进制的思想,先使深度较高的节点2进制的阶段上升,使两个节点在同一深度上,设p,q为两个待查节点,且L(p)>L(q),L表示p,q的深度,令log=log(L(p)),那么用log位2进制数就可以表示p的深度,从2log开始检查,如果L(p)-2log仍 然>=L(q),那么p=P[p][log],上升到相应的祖先节点,log–,重复检查直到log=0。当两个节点在同一深度上,如果两个节点 相等,那么直接返回,如果不相等,同样利用二进制思想,从log开始检查,如果P[p][log]!=P[q][log],分别上升至P[p][log] 和P[q][log],循环到0的时候,必然有LCA(p,q)=father(p)

预处理复杂度为NlogN,查询复杂度为logH,最坏情况下H=N,为logN

从LCA到RMQ

LCA问题可以在线性时间内转化成RMQ问题,所有解决RMQ问题的方法都适用。

深度优先遍历树,并且记录每次访问边的端点,首先记录下根节点,那么一共有2N+1个节点被记 录,用数组E[1..2N+1]来存储节点,并且用L[1..2N+1]来存储相应的节点的深度。R[1..N]来表示第一次访问节点N的数组E的下标, 例如对于上图,R[9]=10,R[12]=15,而LCA(9,12)=E[RMQ(L,10,15)]。

同时L数组有个特点,相邻元素的差为+-1,一般叫做+-1RMQ问题。

从RMQ到LCA

RMQ问题同样可以转换到LCA问题。这意味着一般的RMQ问题可以转换成特殊的+-1RMQ问题。我们需要用到 cartesian trees 笛卡尔树。

数组A[0..N-1]的笛卡尔树是一个以数组最小值为根的二叉树C(A),以该最小值的下标i来标识根节点。如果i>0那么该节点的左儿子是数组A[0..i-1]的笛卡尔树,否则就没左儿子。右儿子是数组A[i+1,N-1]的笛卡尔树。如果数组里有相同的元素,该数组的笛卡尔树不是唯一的,这里相同的元素取第一个出现的,所以这里的笛卡尔树是唯一的。显然,RMQ(A,i,j)=LCA(C,i,j),示例如下

 

可以用栈来完成RMQ到LCA的线性时间的转化。初始栈为空,数组元素依次入栈,入栈的元素 从栈底到栈顶是递增的顺序,即,如果入栈的元素i小于栈顶元素,那么栈顶元素出栈,直到栈顶元素<=当前要入栈的元素i为止,接着完成i入栈,并且 i作为入栈前栈顶的右儿子,而最后出栈的元素作为i的左儿子。如此循环所有元素,最后将栈排空,最后出栈的就是根节点。

修改树
0 0 0是树中唯一的节点。
1 0 1 A[1]>A[0],故1入栈,1为0的右儿子。
2 0 2 A[2]<A[1],1出栈,2入栈,2为0的右儿子,1为2的左儿子。
3 3 A[3]是数组中最小的元素,故所有元素都出栈,3为树的根。0为3的左儿子。
4 3 4 4入栈,4为3的右儿子。
5 3 4 5 5入栈,5为4的右儿子。
6 3 4 5 6 6入栈,6为5的右儿子。
7 3 4 5 6 7 7入栈,7为6的右儿子。
8 3 8 8也是最小的元素,除了3所有的元素出栈,8为3的右儿子,最后出栈的4为8的左儿子。
9 3 8 9 9入栈,9为8的右儿子。
T[i]表示i的父亲节点。st[]实现栈。
  1. int
  2. rmq2lca(int *a,int n)
  3. {
  4.     int i,k,top;
  5.     int st[MAXN];
  6.     top=-1;
  7.     k=top;
  8.     for(i=0;i<n;i++){
  9.         while(k>=0 && a[i]<a[st[k]])
  10.             k–;
  11.         if(k!=-1)
  12.             T[i]=st[k];
  13.         if(k<top)
  14.             T[st[k+1]]=i;
  15.         st[++k]=i;
  16.         top=k;
  17.     }
  18.     T[st[0]]=-1;
  19. }
+-1RMQ问题的算法 O(N)-O(1)

现在我们知道一般的RMQ问题可以通过LCA来转化成+-1RMQ问题。我们可以利用+-1的性质来找到一个O(N)-O(1)算法。

对于数组A[1..N],相邻元素之差为+-1,那么对于所有的i,j的RMQ(A,i,j)的集合就只有 2N 种可能性。

将问题按照大小为 I=(logN)/2 分组,故共有 N/I 组,数组 A‘ 存储每一个分块的最小值,数组 B 存储其下标,时间复杂度为O(N)。数组A’和B的大小都为N/I。现在我们用ST算法来预处理A’,时空开销都为 O(N/l*log(N/l))=O(N) 。每一个分块的大小为I,故每一个分块的RMQ就只有2I=sqrt(N) 种可能性。计算出每一种可能性并存储在表P中,时空复杂度为O(sqrt(N)*I2)=O(N),计算出每一个小块所属于的数组,数组类型可以用10序列来表示,即计算两个元素的差,然后用0来替换-1,复杂度为O(N)

对于查询RMQ(i,j),计算出i,j所在块x,y和块内下标a,b

如果x==y,则进行块内搜索,查出块x的数组类型,用a,b查询表P即可。

如果x!=y,则i,j区间分成三块,a到x块末尾,x+1到y-1块,y块开头到b,每一块的查询都是O(1)的复杂度,求出最小值即可。

文章分类 算法

what is love?

每天听到他说“我爱你” 但还是老觉得他不够爱我,也许这源于人性天生的贪婪 、没有安全感…爱是一种无色无味无形的东西,乍听可能觉得虚无缥缈,但是如果你愿意去感受去体会,爱无处不在! 或许平淡的柴米油盐中你不会发现爱,而往往在遇到摩擦遇到分歧的时候你才有所体会。每个人的思维方式都不一样,尤其是男人同女人,区别更是大大的!面对同一件事,面对他奇怪的逻辑,莫名其妙的理论你也许想摔门,想砸东西,想破口大骂,这时候爱会突然出现来控制我们的大脑,让你选择去信任、去理解、去接受……

文章分类 未分类

boyaa David

          星期四去参加公司的“博雅互动第17期新生代训练营”,地点是在华侨城的鸿波酒店会议室。

还蛮好玩,有几个触动我的点想记录下来:

其中有个环节是【拥抱自己】,刚开始觉得略煽情,哈。当房间里灯灭了,跟随主持人的指引,闭上眼睛,双手放在胸前,试着将自己抱得越来越紧的时候,突然有种莫名的感动…和感触。我们每个人尤其是girls,常常在希望甚至祈求得到别人的一个拥抱却从来没想过去抱抱自己,或许其实这样更带感哦!那酱紫的话,我们自己能轻易做到的事为什么要去等待别人的施舍,所以,在娇娇空间看到过的一句话说的很对:【不管是友情还是爱情,你来,我热情拥抱。你走,我坦然放手】。我们都该骄傲的活着,活出自我!

就这个话题,我又想起之前九月先生推介看的一个复旦大学陈果老师的一个视频【大学生导论】。她关于孤独的解释让我印象深刻,摘录几段哈:

“很多时候我们总想找一个远离喧嚣的地方,因为对人产生了疲劳。对人、对人性、对人的精神产生了严重的疲劳,失去了儿童般的纯真、好奇心。而且拥挤会带来喧闹,喧闹剥夺了我们的宁静,剥夺了我们的闲情。但是人只有在宁静的状态下才可能有闲情去欣赏他人之美,去欣赏生活之美。所以我们比任何时候更加需要孤独,因为只有当你无需迫于无奈的跟人对话的时候你才能够恢复跟自己的对话。但人一旦跟自己打交道的话就是自我反思,自我反思是一切思想的源头,人是在思考自己而不是思考他人的过程当中产生了智慧,人也是在自我批判而不是批判他人的过程中展示了勇气。所以【自己】何等重要,一个陪伴我一生的唯一的人,但是我们往往对她很有疏忽。”

“我们的大城市往往就是充斥这种虚假的繁华和虚假的快乐和感情上的矫揉造作,

我们很多时候互相恭维着,用这种互相恭维来变现自我的谦虚;

我们很多时候互相闲聊着 用闲聊来表现自己的优雅品味 自己性格的温和;

我们取悦着对方 从而好像显得自己也很快乐;

我们叹息这 让自己感觉自己很善良;

但这一切基本上都是假的 这一些..过程中,你既看不见思想 也看不见灵魂

真实是最高的高贵”

所以人啊,花点心思去爱自己吧。只有懂得什么对自己是好的,才可能知道什么对他人是好的。你只有学会自爱,才有可能真正的关爱他人。

还有另一个环节也是【拥抱】,拥抱身边的人。这里有个视频:http://www.iqiyi.com/w_19rrcu64el.html,看一下吧。爱的传递不解释。

最后说一件关于培训后遗症的糗事,培训中有个环节是关于【全力以赴】的。之后我就感觉自己充满了正能量,以至于周五晚上跟九月先生打电话说到第二天要六点起床赶去罗湖口岸,他调侃我说,起那么早,别去了吧。我说我会全力以赴的!然后第二天,早上六点半赶上了第一班地铁,当走到罗宝线终点站“机场东”的时候,我才猛的发现我的目的地是罗宝线的另一个终点站“罗湖”。我崩溃了…….在罗湖等着我的小伙伴也崩溃了。so,有时候我们的失败,并不是方法不对,或是努力不够,仅仅是因为我们方向错了。。。

文章分类 未分类

one day in HK

也许十年之后 距离越来越远 联系越来越少 但我会记得你们曾经是最佳损友

                                                                                                                                                                                                      ———致freads

也许年轻就是如此 虽然我们一无所有 但每天都过的满足 感动 快乐 愿我们一直这样傻傻的爱下去

                                                                                                                                                                                                      ———致lover

曾经的我们哭过 笑过  爱过 痛过 追求过 放弃过  喝醉过 疯狂过 潇洒过 纠结过 彷徨过 奋斗过 2。过…重要的是现在依然能保持微笑

                                                                                                                                                                                                        ———致我们终将逝去的青春

文章分类 未分类