pat-1143 Lowest Common Ancestor (30分)
程序员文章站
2022-07-14 14:49:21
...
一个比较优秀的LCA的解题方法,虽然在复杂度上面可能会有一点点高。看到在解题目上面真的很巧妙。性质用得非常完美。这里我贴上一个关于LCA的专题:
:LCA专题
LCA我所了解的解法,倍增,tarjan等等…但是我还没学过那些算法,所以暂时不写了
解题思路:
对于题目的要求,我就将题目的前序BST序列先去进行转化(其实更多的是用到了bst的性质去做的):
转化后的树的结构是这样的:
我们不断去查询,输入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;
}
上一篇: 使用Docker在Nginx上运行简单的HTML网页
下一篇: 树中两个结点的最低公共祖先
推荐阅读
-
PAT甲级1143 Lowest Common Ancestor BST+LCA
-
1143 Lowest Common Ancestor 甲级
-
[C++] PAT 1143 Lowest Common Ancestor (30分)
-
⭐⭐⭐⭐⭐PAT A1143 Lowest Common Ancestor
-
PAT 1143 Lowest Common Ancestor 【C++版】
-
1143 Lowest Common Ancestor
-
pat-1143 Lowest Common Ancestor (30分)
-
1143 Lowest Common Ancestor (30分)
-
1143 Lowest Common Ancestor (30分)
-
LeetCode 236 -- 二叉树的最近公共祖先 ( Lowest Common Ancestor of a Binary Tree ) ( C语言版 )