fb面经的一题# JobHunting - 待字闺中
a*0
1 楼
给一个含有节点的数组,每个节点指向数组其他节点,或者数组外的节点,判断这个数
组中的节点所构成的树是tree
我的想法是用个map记录,-1表示没在数组中出现过。出现了就转为1。大致code
有没有更好的方法?
bool isTree(vector& a)
{
size_t n=a.size();
unordered_map nodeMap;
for(size_t i=0;i if(nodeMap[a[i]]==-1) {
nodeMap[a[i]]=1;
} else {
nodeMap[a[i]]=0;
}
if(nodeMap[a[i]->next]==0) {
nodeMap[a[i]->next]=1;
}
}
ListNode* root=NULL;
for(auto itr=nodeMap.begin(); itr!=nodeMap.end(); itr++) {
if(itr->second==0) {
root=itr->first;
} else if(itr->second<0){
return false;
}
}
return dfs(root);
}
// use dfs to decide if it's a tree
bool dfs(root){
}
组中的节点所构成的树是tree
我的想法是用个map记录,-1表示没在数组中出现过。出现了就转为1。大致code
有没有更好的方法?
bool isTree(vector
{
size_t n=a.size();
unordered_map
for(size_t i=0;i
nodeMap[a[i]]=1;
} else {
nodeMap[a[i]]=0;
}
if(nodeMap[a[i]->next]==0) {
nodeMap[a[i]->next]=1;
}
}
ListNode* root=NULL;
for(auto itr=nodeMap.begin(); itr!=nodeMap.end(); itr++) {
if(itr->second==0) {
root=itr->first;
} else if(itr->second<0){
return false;
}
}
return dfs(root);
}
// use dfs to decide if it's a tree
bool dfs(root){
}