文档章节

网易实习笔试真题C/C++

r
 ranjiewen
发布于 2016/11/03 23:48
字数 672
阅读 1
收藏 0

刚做的时候根本就没有想到解题思路,刚好看到了别人的思路,自己写了一下。里面对unordered_map及vector二维数组的建立很灵活,另外区别了一下map,unordered_map,hash_map;但是没有弄清楚unordered_map,hash_map的区别。以后遇到了在细细研究。

另一个关于二叉树的笔试真题:http://www.cnblogs.com/ranjiewen/p/5341287.html  。

//小明陪小红去看钻石,他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们们比较了一段时间后,
//它们看中了两颗钻石g1和g2。现在请你根据之前比较的信息判断这两颗钻石的哪颗更重。
//给定两颗钻石的编号g1, g2,编号从1开始,同时给定关系数组vector, 其中元素为一些二元组,第一个元素为一次比较中较重的钻石的编号,
//第二个元素为较轻的钻石的编号。最后给定之前的比较次数n。请返回这两颗钻石的关系,若g1更重返回1,g2更重返回 - 1,无法判断返回0。
//输入数据保证合法,不会有矛盾情况出现。
//
//
//测试样例:
//
//2, 3, [[1, 2], [2, 4], [1, 3], [4, 3]], 4
//返回: 1

//思路:
//就是一个森林,关系存在就是以g2为根节点的树下面的节点中有g1,
//或者以g1为根节点的树的下面的节点包含g2
//我们采取层序遍历的方式遍历以g1开头的整棵树,和以g2开头的整棵树.

#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;
class Cmp
{
    bool judge(int g1,int g2,unordered_map<int,vector<int>> ans)  //判断是否有记录
    {
       //查找g1是否比g2重
        queue<int> q;
        unordered_map<int, bool> mark;//用于标记当前节点是否遍历过
        q.push(g1);
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            mark[cur] = true;
            if (cur==g2)   //钻石的重量各不相同,g1和g2不可能相同
            {
                return true;
            }
            for (size_t i = 0; i < ans[cur].size(); i++)
            {
                if (!mark[ans[cur][i]])  //没有遍历过   //    2->4->3
                    q.push(ans[cur][i]);
            }
        }
    }
public:
    int cmp(int g1,int g2,vector<vector<int>> records,int n)
    {
        unordered_map<int, vector<int>> ans;
        for (size_t i = 0; i < n; i++)  //赋值
        {
            ans[records[i][0]].push_back(records[i][1]);
        }
        if (judge(g1,g2,ans))
        {
            return 1;
        }
        else
        {
            if (judge(g2, g1, ans))
            {
                return -1;
            }
            else
                return 0;
        }
     }
};

int main()

{
    int g1 = 2, g2 = 3,n=4;
    vector<vector<int>> records;
    vector<int> a = { 1, 2 }, b = { 2, 4 }, c = { 1, 3 }, d = { 4, 3 };
    records.push_back(a);
    records.push_back(b);
    records.push_back(c);
    records.push_back(d);
    Cmp chooseWeighter;
    chooseWeighter.cmp(g1,g2,records,n);
    return 0;
}

根据ans的内存情况,我们可以推断

unordered_map<int,vector<int>> ans的用法,特别是
ans[cur][i]的表示。

本文转载自:http://www.cnblogs.com/ranjiewen/p/5328646.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
腾讯阿里网易游戏华为科大讯飞面经

本人是一非科班妹子,在找实习的过程中面试了腾讯、阿里、网易游戏、华为、科大讯飞(面试的顺序),前面三个都挂了。。。 1.腾讯提前批——游戏客户端开发 自我介绍+项目经历(问的很细) ...

牛客网
2018/06/13
0
0
是技术太次,还是要得太高。面试屡屡失败!

先来个背景介绍。 本人计算机科学与技术专业,C++方向,2013年毕业。非211,非985,但是在学校期间主攻技术,基础和知识面还是不错的。从C、C++、C#、java、php、Qt都有接触,数据库、多线程...

changnet
2015/04/25
2.7K
16
想从事IT行业的你,一定看看这篇文章

很多想从事IT行业的小伙伴都会问: 我该如何学习技术? 我应该选择什么样的方向来深入学习并以此来就业? 如何证明自己的技术很牛? 什么是程序员的核心竞争力? 如何成为一名优秀的工程师?...

蓝神100
2018/06/28
0
0
hadoop好找工作吗

自我感觉C/C++学的很不错了,数据结构算法也掌握了不少(除了课本上的算法题都自己动手写过,还做过将近100道ACM题),自己写的小软件主要是MFC写socket网络程序,脚本语言熟悉PHP。但在北京...

荡荡
2014/11/20
599
4
C++学到什么程度可以去参加信息学竞赛

经常有朋友问我,小朋友C++学到什么程度可以去参加信息学竞赛? 要回答这个问题,就得先知道信息学竞赛考察的是什么内容。信息学竞赛的主要方式是上机编写算法,算法要借助于某种编程语言比如...

海天一树X
04/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

oracle ORA-39700: database must be opened with UPGRADE option

ORA-01092: ORACLE instance terminated. Disconnection forced ORA-00704: bootstrap process failure ORA-39700: database must be opened with UPGRADE option 进程 ID: 3650 会话 ID: 29......

Tank_shu
今天
1
0
分布式协调服务zookeeper

ps.本文为《从Paxos到Zookeeper 分布式一致性原理与实践》笔记之一 ZooKeeper ZooKeeper曾是Apache Hadoop的一个子项目,是一个典型的分布式数据一致性的解决方案,分布式应用程序可以基于它...

ls_cherish
今天
4
0
聊聊DubboDefaultPropertiesEnvironmentPostProcessor

序 本文主要研究一下DubboDefaultPropertiesEnvironmentPostProcessor DubboDefaultPropertiesEnvironmentPostProcessor dubbo-spring-boot-project-2.7.3/dubbo-spring-boot-compatible/au......

go4it
昨天
1
0
redis 学习2

网站 启动 服务端 启动redis 服务端 在redis 安装目录下 src 里面 ./redis-server & 可以指定 配置文件或者端口 客户端 在 redis 的安装目录里面的 src 里面 ./redis-cli 可以指定 指定 连接...

之渊
昨天
2
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部