欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

pat-1143 Lowest Common Ancestor (30分)

程序员文章站 2022-07-14 14:49:21
...

pat-1143 Lowest Common Ancestor (30分)

一个比较优秀的LCA的解题方法,虽然在复杂度上面可能会有一点点高。看到在解题目上面真的很巧妙。性质用得非常完美。
这里我贴上一个关于LCA的专题:LCA专题
LCA我所了解的解法,倍增,tarjan等等…但是我还没学过那些算法,所以暂时不写了

解题思路:
对于题目的要求,我就将题目的前序BST序列先去进行转化(其实更多的是用到了bst的性质去做的):
转化后的树的结构是这样的:
pat-1143 Lowest Common Ancestor (30分)

我们不断去查询,输入u和v。那么存在如下情况,因为bst的性质,左<中<=右。那么显然存在如下表示:(u<祖先&&v>祖先)||(v<祖先&&u>祖先)
但是u,v之间,也就是我们输入的点也是可以直接构成祖孙关系的。所以可以可以加上一个=。
然后对于没有出现的点,可以使用哈希表去映射查找, 也可以用散列去进行映射,性质我觉得几乎是一样的。

代码如下:

//四种情况,最后去进行分类讨论
#include <bits/stdc++.h>
using namespace std;
int main(){
    int m,n,u,v,a;
    cin>>m>>n;
    vector<int> pre(n+1);//其实这就直接包含了bst的前序序列
    unordered_map<int,bool> h;
    for(int i=0;i<n;i++){
        cin>>pre[i];
        h[pre[i]]=true;//对出现过的点打上标记
    }
    //现在进行最小工共祖先的查询
    for(int i=0;i<m;i++){
        cin>>u>>v;
        for(int j=0;j<n;j++){
            a=pre[j];
            //其实这里面算是三种情况
            if((a>=u&&a<=v)||(a>=v&&a<=u)) break;
        }
        //最后就是处理结果
        if(!h[u]&&!h[v]) //都没出现的话
            printf("ERROR: %d and %d are not found.\n",u,v);
        else if(!h[u]||!h[v]) //其中一个出现了
            printf("ERROR: %d is not found.\n",h[u]?v:u);//如果u是正确,表示的是u出现了,那么v肯定是没出现的
        else if(a==u||a==v) //其中一个点是另外一个点的祖先,这个可以稍微预处理一下
            printf("%d is an ancestor of %d.\n",a==u?u:v,a==u?v:u);
        else printf("LCA of %d and %d is %d.\n",u,v,a);
    }
    return 0;
}