首页 > 网易笔试思路与前2题代码
头像
wayneYM
编辑于 2021-04-20 10:07
+ 关注

网易笔试思路与前2题代码

网易题目主要考察基础数据机构,都是模拟题,即按照题目操作选取对应的数据结构进行模拟操作即可。虽然博主很菜并不知道第三题的细节出了什么问题,第三题0都过不了,分享一下自己的思路。

第一题---乒乓球

每队6个人,3男3女,分别参加男双女双混双,所有人都要上,那么实际上每队只有9种出战策略。那么AB队各9种出战策略,直接枚举所有情况也就81种情况。直接写代码模拟就完事了,不想想花里胡哨的。

第二题---石头剪刀布

观察数据大小,最多1000个人,猜拳最多发生1000次。1000*1000=1e6左右,同样可以直接枚举算。
使用vec存每个人出什么(字符转成数字,好存,而且好判断输赢),再使用vis标记是否出局,原数据顺时针输出,默认向右打就好了,模拟游戏向右打M次,比较从谁开始剩余次数多即可。

第三题---分数排序

个人觉得这题出的好好,非常有游戏的感觉,虽然死活过不了,与大家分享下我的思路,恳请大佬评论区说我错哪了,我查了快40分钟了估计。

首先思考题目的要求

  • 要有一个分数列表,是顺序的
  • 通过id要索引到旧的分数(对比是否有提升)
  • 通过id要索引到是否拿过礼物(防止重复拿)
  • 可以拿到分数的中位数
基于以上几点,考虑到堆的中位数不好拿,所以决定直接用deque存分数,然后手动维护分数列表的有序型。同时使用map以用户id作为key,value使用pair存分数以及是否拿过礼物。那么还有一个问题,怎样进行分数的更新。考虑到分数是不需要与用户一一绑定的,比如分数列表有10个2分,此时有一个曾经拿了2分的用户拿到了4分,我们并不需要找到他当初拿的那个2分删除,随便找个2分删就完事了。

整体模拟流程如下

输入一条数据
map找玩过没 没玩过
    插入新数据  分数***deque
    玩过
    是否超过旧的分数,没超过直接退出当次循环  
        超过旧的分数
         在deque找个与旧分数相等的分数删掉,插个新的分数 计算中位数  看是否与当前分数相等  
检查领没领过礼物

map存  id:  分数  + 礼物拿过没
deque  只用存分数队列
    需要重写deque的插入删除函数保证有序型,同时要用到二分查找快速定位分数索引。
    
    
2w条记录,数据量上可以直接做,直接做好维护即可。

疑问点

分数与上一次玩相同但是突然符合中位数,拿不拿礼物?(都试过了,还是一个都过不了,菜了)


以下为代码:乱七八糟的注释较多,希望大家见谅。!第三题是不通过的代码,也顺手贴上来了希望有大佬指正!

三题的代码

//第一题
#include<iostream>
#include<vector>
using namespace std;

int main(){
    int T ;
    cin>>T;
    for(int _i = 0 ; _i < T ; ++_i){
        vector<int> teamAmale,teamAfe;
        vector<int> teamBmale,teamBfe;
        int pow;
        for(int _t = 0 ; _t < 3; ++_t){
            cin>>pow;
            teamAmale.push_back(pow);
        }
        for(int _t = 0 ; _t < 3; ++_t){
            cin>>pow;
            teamAfe.push_back(pow);
        }
        
        for(int _t = 0 ; _t < 3; ++_t){
            cin>>pow;
            teamBmale.push_back(pow);
        }
        for(int _t = 0 ; _t < 3; ++_t){
            cin>>pow;
            teamBfe.push_back(pow);
        }
        //输入完毕
        //实际上每对9种组队方法,  剩下的选人就确定下来了  一共81局
        //甚至可以直接遍历
        
        int Bwintimes;
        vector<vector<int> > Ascore(9,vector<int>(3));
        vector<vector<int> > Bscore(9,vector<int>(3));
        //算出A和B所有组合的得分情况。
        //男  女  混
        int Anan , Anv , Ahun;
        int Bnan , Bnv , Bhun;
        int idx = 0;
        for(int i = 0 ; i < 3; ++i){
            for(int j = 0 ; j < 3 ; ++j){
                Anan = teamAmale[0]+teamAmale[1]+teamAmale[2]-teamAmale[i];
                Anv = teamAfe[0]+teamAfe[1]+teamAfe[2]-teamAfe[j];
                Ahun = teamAmale[i]+teamAfe[j];
                Ascore[idx][0] = Anan;
                Ascore[idx][1] = Anv;
                Ascore[idx][2] = Ahun;
                
                Bnan = teamBmale[0]+teamBmale[1]+teamBmale[2]-teamBmale[i];
                Bnv = teamBfe[0]+teamBfe[1]+teamBfe[2]-teamBfe[j];
                Bhun = teamBmale[i]+teamBfe[j];
                Bscore[idx][0] = Bnan;
                Bscore[idx][1] = Bnv;
                Bscore[idx][2] = Bhun;
                
                idx++;
            }
        }
        //比较81次即可
        int ans=0;
        int Bwin=0;
        for(int i = 0 ; i < 9 ; ++i){
            for(int j = 0 ; j < 9 ;++j){
                Bwin = 0;
                if(Ascore[i][0] < Bscore[j][0])    Bwin++;
                if(Ascore[i][1] < Bscore[j][1])    Bwin++;
                if(Ascore[i][2] < Bscore[j][2])    Bwin++;
                if(Bwin>=2)    ans++;
            }
        }
        cout<<ans<<endl;
    }
    
    return 0;
} 
//第二题
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
vector<int> vec;

int beat(int i , int j ){
    if(vec[i] == vec[j])    return 0;
    
    if(abs(vec[i] - vec[j])==1){
        if(vec[i] > vec[j])    return 1;
        else                   return -1;
    }
    //只剩下02的情况的
    if(vec[i] > vec[j])    return -1;//2 0 输了
    else if(vec[i] < vec[j])    return 1;//0 2 赢了
    return -999;
}

int main(){
    int T ;
    cin>>T;
    for(int _i = 0 ; _i < T ; ++_i){
        int N ,M;//N人数  M轮次
        cin>>N>>M;
        vec.clear();
        //用数字代表石头剪刀布
        //2 1 0;
        char chos;
        for(int _t= 0 ; _t < N ; _t++){
            cin>>chos;
            if(chos=='R')vec.push_back(2);
            else if(chos == 'S')    vec.push_back(1);
            else if(chos == 'C')    vec.push_back(0);
        }
        //能否模拟,用什么模拟
        //1000个人  最多打1000次  可以模拟  1000*1000 = 1e6;
        int maxrest = -1;
        for(int i = 0 ; i < N ; i++){
            //从第i个人开始打,向右打
            int cur = i;//当前的人
            int rcur = (i+1)%N;
            int rest = N;//剩余的人
            vector<int> vis(N);//标记存活状态
            int flag;
            for(int t = 0 ; t < M ; ++t){
                //M轮次
                flag = beat(cur,rcur);
                if(flag > 0){
                    //cur赢了  右侧人移动
                    vis[rcur] = 1;
                    while(vis[rcur] == 1){
                        rcur = (rcur+1 )%N;
                    }
                    rest--;
                }
                else if(flag == 0){
                    //平局
                    cur = rcur;
                    rcur = (rcur+1)%N;//右移动
                    while(vis[rcur] == 1){
                        rcur = (rcur+1 )%N;
                    }
                }
                else if(flag < 0){
                    //cur输了
                    vis[cur] = 1;
                    cur = rcur;
                    rest--;
                    rcur = (rcur+1) % N;
                    while(vis[rcur] == 1){
                        rcur = (rcur+1 )%N;
                    }
                }
            }
            maxrest = max(maxrest,rest);
        }

        cout<<maxrest<<endl;
    }
    
    return 0;
}
//第三题,过不了过不了过不了
#include <iostream>
#include <vector>
#include <deque>
#include <map>
using namespace std;

//deq排序从小到大

int find(int score , deque<int>& deq){
    //返回deq中012456 搜3 返回3 搜7返回6? 第一个大于等于score的索引
    int l = 0 ;
    int r = deq.size()-1;
    int mid;
    while(l<=r){
        mid = (l+r)/2;
        if(deq[mid] == score){
            r = mid-1;
        }
        else if(deq[mid] < score){
            l = mid+1;
        }
        else if(deq[mid] > score){
            r = mid-1;
        }
    }
    return r+1;
}

void ins(int score , deque<int>& deq){
    //往deq插入一个数,并且维护好顺序
    if(deq.size() == 0){
        deq.push_back(score);
        return;
    }
    int num = find(score , deq);//返回的是第一个大于或者等于的  插在这个之前  没毛病
    deq.insert(deq.begin()+num, score);

    return ;
}
double  getmid(deque<int>& deq){

    int n = deq.size();

    if(n%2 == 0){
        //偶数
        return (0.0+deq[n/2] + deq[n/2-1])/2;
    }
    else
        return deq[n/2];
}

int main(){
    int T;
    cin>>T;
    for(int _i = 0 ; _i < T ; ++_i){
        int N;
        cin >> N;
        //输入一条数据
        //map找玩过没   没玩过插入新数据  分数***deque
        //map玩过   看看超没超过旧的  超过旧的去deque找个旧的 删掉,插个新的分数
        //计算中位数  看相不相等  检查领没领过礼物
        //关注点  同分但是突然符合中位数  也要拿礼物?
        //map存  id:  分数  + 礼物拿过没
        //deque  只用存分数队列
        //2w条记录,好像可以直接冲,直接做好维护即可。

        map<int,pair<int,int> > memo;//玩家号  分数  领过礼物否
        deque<int> deq;//分数队列
        int id,score;
        double midscore;//中位数
        int times=0;//领礼物次数
        int oldscore;
        for(int _t =0 ; _t < N ; ++_t ){
            cin>>id>>score;
            
            if(memo.count(id) == 0){
                memo[id] = make_pair(score,0);//0是没拿过礼物
                ins(score,deq);
            }
            else{//memo已有数据
                oldscore = memo[id].first;
                if(score >= oldscore){
                    //超过旧的   要去更新下分数
                    int pos = find(oldscore,deq);
                    //直接删除这个迭代器 再插
                    deq.erase(deq.begin()+pos);
                    ins(score,deq);
                }
                else{
                    continue;//没有触发分数更新  是不领奖的
                }
                    
            }
            midscore = getmid(deq);//找中间分数
                
            if(midscore==score && memo[id].second == 0){
                memo[id].second=1;
                times++;
            }
        }
        cout<<times<<endl;
        
    }
    return 0;
}

全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐