网易互娱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;
}




全部评论
第三题是输入的问题,有的测试用例是几组连在一起的,加个while判断是否输入结束了就行,出题人没说清楚,离谱😅
3 回复 分享
发布于 2022-04-15 21:35
我第一题用的方法是计算左右子树的结点数,根据结点数算出深度,然后相加,但是只过了一部分,我觉得我的方法没问题啊,楼主觉得我方法错在哪啊🤔
1 回复 分享
发布于 2022-04-15 22:05
第三题20的都是没有加循环,因为输入数据有很多组
1 回复 分享
发布于 2022-04-15 21:48
请问各位,是取最高吗?我后来改代码没来得及改回去😥
1 回复 分享
发布于 2022-04-15 21:47
就很倒霉 周三华为笔试分糖果bug让我遇到 今天网易互娱又有bug 让我遇到
1 回复 分享
发布于 2022-04-15 21:33
第三个怎么都是20%
1 回复 分享
发布于 2022-04-15 21:30
第三题有问题吧
1 回复 分享
发布于 2022-04-15 21:29
友友看看奇安信暑期实习有没有你感兴趣的岗位(内推码:NTALAw5) https://campus.qianxin.com/
点赞 回复 分享
发布于 2022-05-01 09:10
这个笔试会限定你用的编程语言么?🤔
点赞 回复 分享
发布于 2022-04-17 10:21
t1题目的样例5,根据你的代码求出来是6额
点赞 回复 分享
发布于 2022-04-16 21:05
第二题不会 第三题我估计大家都是去查的网上的解答吧 不然这题挺难的 我不信这么多人能做出来
点赞 回复 分享
发布于 2022-04-16 18:59
第三题我调了1个多小时,怎么都是20%,不懂这么简单的题有啥坑
点赞 回复 分享
发布于 2022-04-16 14:28
其实第一题不建树也可以的
点赞 回复 分享
发布于 2022-04-16 11:13
我也20%,心态爆炸
点赞 回复 分享
发布于 2022-04-16 11:09
做一道的能过笔试嘛。。
点赞 回复 分享
发布于 2022-04-16 10:17
100 100 0
点赞 回复 分享
发布于 2022-04-16 02:59
问一下老哥 第三题dfs的用例过了多少
点赞 回复 分享
发布于 2022-04-15 23:41
第一题加了map还是a不了
点赞 回复 分享
发布于 2022-04-15 21:53
请问网易这个可以用本地ide吗?
点赞 回复 分享
发布于 2022-04-15 21:53
第一二题都是过了87左右😂
点赞 回复 分享
发布于 2022-04-15 21:53

相关推荐

点赞 评论 收藏
分享
07-03 16:02
门头沟学院 Java
点赞 评论 收藏
分享
评论
4
13
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务