网易互娱4.15 笔试
2022年4月21日15:16:06
今天看了一下，流程结束，2.2/3就给我挂了？
第1题，根据前序遍历后序遍历数组 算出树任意两个节点的最远距离
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode():val(0),left(nullptr),right(nullptr){}
TreeNode(int x):val(x),left(nullptr),right(nullptr){}
TreeNode(int x,TreeNode* left,TreeNode* right):val(x),left(left),right(right){}
};
TreeNode* help(vector<int>& inorder,vector<int>& postorder,int left,int right,int begin,unordered_map<int,int>& map){
if(left>right)return nullptr;
int midVal=postorder[right];
int mid=map[midVal];
TreeNode* root=new TreeNode(midVal);
root->left=help(inorder,postorder,left,left+mid-begin-1,begin,map);
root->right=help(inorder,postorder,left+mid-begin,right-1,mid+1,map);
return root;
}
TreeNode* buildTree(vector<int>& inorder,vector<int>& postorder){
unordered_map<int,int> map;
for(int i=0;i<inorder.size();++i)map[inorder[i]]=i;
return help(inorder,postorder,0,postorder.size()-1,0,map);
}
int dfs(TreeNode* root,int& res){
if(root==nullptr)return 0;
auto left=dfs(root->left,res);
auto right=dfs(root->right,res);
res=max(1+left+right,res);
return 1+max(left,right);
}
int main(){
int n;
cin>>n;
vector<int> inorder(n);
vector<int> postorder(n);
for(int i=0;i<n;++i)cin>>inorder[i];
for(int i=0;i<n;++i)cin>>postorder[i];
auto root=buildTree(inorder,postorder);
int res=0;
dfs(root,res);
cout<<res-1<<endl;
} 2.lru
class Solution {
public:
int stat_hit_count(vector<int>& R, int N) {
capacity=N;
for(auto& r:R)insert(r);
return res;
}
private:
list<int> lru;
unordered_map<int,list<int>::iterator> map;
int capacity;
int res=0;
void insert(int key){
if(map.find(key)!=map.end()){
res++;
lru.splice(lru.begin(), lru,map[key]);
return;
}
if(map.size()>=capacity){
int key=lru.back();
map.erase(key);
lru.pop_back();
}
lru.push_front(key);
map[key]=lru.begin();
}
};
3 弹簧题 bfs和dfs都用了 仅过20% int bfs(vector<int>& jump){
int n=jump.size();
if(n==1)return 1;
queue<int> que;
unordered_set<int> visited;
que.push(0);
visited.insert(0);
int res=0;
while(!que.empty()){
int size=que.size();
for(int i=0;i<size;++i){
auto cur=que.front();
que.pop();
if(cur>=n)return res;
int right=cur+jump[cur];
if(!visited.count(right)){
que.push(right);
visited.insert(right);
}
for(int j=cur-1;j>0;--j){
if(!visited.count(j)){
que.push(j);
visited.insert(j);
}
}
}
res++;
}
return res;
}
int main(){
int n;
cin>>n;
vector<int> jump(n);
for(int i=0;i<n;++i)cin>>jump[i];
cout<<bfs(jump);
return 0;
} 
