By Jalan
文章目录
**By Jalan**知识工具需求数学数据结构和算法语言
题干输入条件输出条件例子例1输入输出
题解第一次(测试点0,测试点1,测试点3不过)思路预期时间复杂度编写用时代码CPP运行用时
结尾
知识工具需求
数学
数据结构和算法
语言
题干
输入条件
M<=1000询问数,N<=10000节点数. 给一个中序和先序 m行每行是询问节点
输出条件
找到:LCA of U and V is A. 如果根是其中之一:X is an ancestor of Y. 其中一只找不到:ERROR: U is not found. 都找不到:ERROR: U and V are not found.
例子
例1
输入
6 8
7 2 3 4 6 5 1 8
5 3 7 2 6 4 8 1
2 6
8 1
7 9
12 -3
0 8
99 99
输出
LCA of 2 and 6 is 3.
8 is an ancestor of 1.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.
题解
第一次(测试点0,测试点1,测试点3不过)
我测试用例写了不少了啊咋回事,有没有解惑的微信转您10块哈
思路
LCA问题.询问有多组,考虑使用tarjan解决. 还顺便需要一个hash散列来看询问是否在树里.
输入数据到数组preorder和inorder里,用数组hashList来统计出现过的节点.输入问题对到query里.创建tarjan的必须条件,比如并查集函数,标记有问询数组q,标记访问过数组known等.遍历询问.符合要求的加入q.不符合要求的加入数组ans创建一个map index目的是通过一对数字找到提问的序号.
预期时间复杂度
编写用时
40分钟
代码
CPP
#include <algorithm>
#include <stdio.h>
#include <unordered_map>
#include <vector>
using namespace std
;
vector
<int> preoder
;
vector
<int> inorder
;
typedef struct node
{
int x
= -1;
int y
= -1;
int id
= -1;
} node
;
vector
<node
> query
;
int m
, n
;
vector
<int> hashList(10001);
vector
<int> parent
;
int findRoot(int x
, vector
<int> parent
)
{
while (parent
[x
] != -2)
{
x
= parent
[x
];
}
return x
;
}
void unionNode(int insert
, int beInsert
, vector
<int> &parent
)
{
parent
[insert
] = beInsert
;
}
unordered_map
<int, vector
<node
>> queryPair
;
vector
<bool> known(10001);
struct an
{
int x
;
int y
;
int id
;
int kind
= 0;
} a
;
vector
<an
> ans
;
vector
<int> hashId(1001);
void dfs(int il
, int ir
, int pl
, int pr
)
{
int root
= preoder
[pl
];
int rootInIndex
= -1;
for (int i
= il
; i
<= ir
; i
++)
{
if (inorder
[i
] == root
)
{
rootInIndex
= i
;
break;
}
}
int lsize
= rootInIndex
- il
;
int rsize
= ir
- rootInIndex
;
if (lsize
)
{
dfs(il
, il
+ lsize
- 1, pl
+ 1, pl
+ 1 + lsize
- 1);
unionNode(preoder
[pl
+ 1], root
, parent
);
}
if (rsize
)
{
dfs(ir
- rsize
+ 1, ir
, pr
- rsize
+ 1, pr
);
unionNode(preoder
[pr
- rsize
+ 1], root
, parent
);
}
known
[root
] = true;
for (int i
= 0; i
< queryPair
[root
].size(); i
++)
{
int id
= queryPair
[root
][i
].id
;
if (hashId
[id
] == 0)
{
int x
= queryPair
[root
][i
].x
;
int y
= queryPair
[root
][i
].y
;
if (x
== -1)
{
if (known
[y
] == true)
{
int kind
= findRoot(y
, parent
);
ans
.push_back({query
[id
].x
, query
[id
].y
, id
, kind
});
hashId
[id
] = true;
}
}
else
{
if (known
[x
] == true)
{
int kind
= findRoot(x
, parent
);
ans
.push_back({query
[id
].x
, query
[id
].y
, id
, kind
});
hashId
[id
] = true;
}
}
}
}
}
bool cmp(an a
, an b
)
{
return a
.id
< b
.id
;
}
int main(int argc
, char const *argv
[])
{
scanf("%d%d", &m
, &n
);
preoder
.resize(n
);
inorder
.resize(n
);
query
.resize(m
);
for (int i
= 0; i
< n
; i
++)
{
scanf("%d", &inorder
[i
]);
hashList
[inorder
[i
]]++;
}
for (int i
= 0; i
< n
; i
++)
{
scanf("%d", &preoder
[i
]);
}
for (int i
= 0; i
< m
; i
++)
{
scanf("%d%d", &query
[i
].x
, &query
[i
].y
);
query
[i
].id
= i
;
}
parent
.resize(n
+ 1);
for (int i
= 0; i
< n
+ 1; i
++)
{
parent
[i
] = -2;
}
for (int i
= 0; i
< m
; i
++)
{
int x
= query
[i
].x
;
int y
= query
[i
].y
;
int id
= query
[i
].id
;
if (hashList
[x
] == 0 && hashList
[y
] == 0 && hashId
[id
] == 0)
{
ans
.push_back({x
, y
, id
, -3});
hashId
[id
]++;
continue;
}
if (hashList
[x
] == 0 && hashList
[y
] != 0 && hashId
[id
] == 0)
{
ans
.push_back({x
, y
, id
, -2});
hashId
[id
]++;
continue;
}
if (hashList
[x
] != 0 && hashList
[y
] == 0 && hashId
[id
] == 0)
{
ans
.push_back({x
, y
, id
, -1});
hashId
[id
]++;
continue;
}
queryPair
[x
].push_back({-1, y
, id
});
queryPair
[y
].push_back({x
, -1, id
});
}
if (n
!= 0)
{
dfs(0, n
- 1, 0, n
- 1);
sort(ans
.begin(), ans
.end(), cmp
);
}
for (int i
= 0; i
< ans
.size(); i
++)
{
int x
= ans
[i
].x
;
int y
= ans
[i
].y
;
int kind
= ans
[i
].kind
;
if (kind
== -3)
{
if (x
== y
)
{
printf("ERROR: %d is not found.\n", x
);
}
else
{
printf("ERROR: %d and %d are not found.\n", x
, y
);
}
continue;
}
if (kind
== -2)
{
printf("ERROR: %d is not found.\n", x
);
continue;
}
if (kind
== -1)
{
printf("ERROR: %d is not found.\n", y
);
continue;
}
if (kind
== x
)
{
printf("%d is an ancestor of %d.\n", x
, y
);
continue;
}
if (kind
== y
)
{
printf("%d is an ancestor of %d.\n", y
, x
);
continue;
}
printf("LCA of %d and %d is %d.\n", x
, y
, kind
);
}
return 0;
}
运行用时
结尾
看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀 @.@ 也欢迎关注我的账号呀=]
**开心code每一天**
