首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
牛客89号
获赞
117
粉丝
21
关注
0
看过 TA
6
IP属地:美国
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑牛客89号吗?
发布(99)
评论
收藏
刷题
牛客89号
关注TA,不错过内容更新
关注
2015-05-12 23:56
[PAT解题报告] Counting Leaves
给定一个树,求每层没有孩子的节点数。首先,树是邻接表的形式给的,即每个节点的孩子有哪些。其次,这个树是有根树。注意:节点数0 < N < 100, 但题目好像没说节点id是连续的,尽管都小于100。所以我没有假设节点id连续,读入的节点数n,我也没有用。 不过我假设了每个写出的节点id, k 后面跟k个孩子,而k不应该等于0,确实题目没说k != 0这个问题…… 两种办法解决这个问题: 第一种方法对每个节点记录一个父亲f值,然后标记该节点是否有孩子hasSon[i]——我们不应该用度是否为1来判断叶子,因为只有两个节点的时候,根不能算做叶子。然后根...
0
点赞
评论
收藏
分享
2015-05-12 22:59
[PAT解题报告] A+B Format
题目比较简单,求a + b的和。 对于这种问题,需要注意 (1) 有几组数据, (2) 数据范围有多大。 好在题目都有清晰的描述。我们知道只有一组数据,数据范围是-106到10 6 ,这说明答案不会超过int范围。输出要注意就是输出的格式要按照三位一节的形式输出。比如1000, 要输出1,000。 我们有大概有两种方法对待这种问题: (1) 把答案存入字符串,再输出 ,很方便。 c语言有sprintf可以直接把答案写入字符串再3位3位输出即可,注意3位是从低位算的,所以要把高位的n % 3位先输出了(n是总位数,如果有余数显然要先输出来),还要注意什么时...
0
点赞
评论
收藏
分享
2015-05-12 22:58
[PAT解题报告] Tree Traversals
给定二叉树的后序和中序遍历,返回它的层序遍历。 分析: (1) 先还原二叉树。 因为节点数很少,我们可以用一个大的全局数组代替指针变量——当然每个节点的左右孩子还是指针变量,只不过它们的值指向大数组里的元素,而不是真正自己从堆里开辟的空间。还原可以递归进行。 后序遍历序列最后一个字符x是根节点 (R)x 中序遍历找到对应的x (A)x(B), 它被切分为(A)、(B)两部分,分别对应左右子树。从后序遍历序列的(R)中切分出(A)和(B)那么长的两段,对应于左右子树的后序遍历序列。然后递归还原左右子树即可。 还原出二叉树,做层序遍历时,只需要进行bfs就可以了。...
0
点赞
评论
收藏
分享
2015-05-12 10:21
[PAT解题报告] Queueing at Bank
一个银行有K个窗口,每个窗口只能服务一个人,有n个人,达到时间不同,银行开始服务和结束服务的时间是8点到17点,如果17点前到达,但是在排队,最后服务的时间比17点晚是可能的,但是17点以后到达的人就没办法了。给定每个人达到时间和服务的时间,求办理业务的人的平均等待时间。 分析: 这个也是模拟题。其实我们不关心每个人在哪个窗口排队或者服务,我们没有必要记录哪些人在哪个窗口——只要记录哪些人在什么时间被服务,在什么时间服务结束即可。当然需要记录还有多少个窗口。我们用一个“事件控制器”——即表示事件的队列,最初每个人达到事件都放入队列里,然后每个人记录一个服务开始的事件,当服务...
0
点赞
评论
收藏
分享
2015-05-10 11:57
[PAT解题报告] Battle Over Cities
给定一个无向图,问删掉一个节点(和与之相关联的边)之后,我们需要再新建多少条边,能保证这个图的其他点互相可达。 分析:我们把一个图切成若干个连通分量——每个连通分量当作一个“大”的节点,这些“大”节点之间是没有边相连的,这些“大”节点内部的真正节点是互相连通的。如果有n个“大”节点,我们连(n - 1)条边,就可以形成一棵树,所有的真正节点之间也都有道路相连了。 所以这个题本质就是删一个节点之后,看连通分量的个数,减1就是答案。求连通分量可以用bfs和dfs,dfs简单点。另外还要注意,如果原始图只有一个节点,删掉这个节点之后就是一个空的图了——所以算连通分量...
0
点赞
评论
收藏
分享
2015-05-10 04:19
[PAT解题报告] The Best Rank
简单题,输入是每个学生的id以及三门课程成绩,分别是C语言(C),数学(M)和英语(E), 三门课程成绩都是不超过100的非负整数。对每个学生,再求一个平均分(除以3,下取整),作为另外一个分数A。对每个学生按照“ACME”的顺序找到他最好的名次,例如某学生的平均分是第1名, C是第2名,M是第3名,E是第4名,则对于他来讲最好是选择按照平均分排名。也就是说对每个学生选出对他最有利的那一维作为他排名的依据。查询排名的学生可能不存在,所以要用一个map保存所有id和真正编号(0..n - 1)的对应关系。 题目没什么坑,我们可以对每个学生按照ACME分别排序,排序当然可以直接...
0
点赞
评论
收藏
分享
2015-05-09 12:42
[PAT解题报告] Radix
题目给定两个“数”,已知其中一个数是w进制的,问另外一个数是几进制才能使得这两个数相等。所有数长度不超过10,每一位只有0-9还有a-z。首先题目没给数据范围,我们先把第一个w进制的数化成10进制的整数,注意用long long——好在范围够用。下面考虑另外一个数的进制,关键问题在进制可以很大,比如11这个数,在3610进制中会达到(3610+1)那么大,所以我们还是要慎重考虑进制。好在进制可以二分,我们二分一个进制b,然后把第一个数x化成b进制数存到数组里,和第二个数比一下看看是不是一样,因为我们选择的b越大,x转换过来的数“形式”上越小,所以这个是有单调性的。我们总可...
0
点赞
评论
收藏
分享
2015-05-08 07:32
[PAT解题报告] Sign In and Sign Out
给定每个人进出机房的时间记录,来得最早的人和走得最晚得人分别负责开门和锁门。输出来得最早得人和走得最晚得人得id。 这个题,首先注意id里面没有空白,所以可以使用scanf直接读入数据。 关于时间的处理:输入的时间是hh:mm:ss的,我们可以用scanf("%d:%d:%d")读出h,m,s再把它们统一为一个整数,统一的方法其实可以很多,例如我们可以把它们接成一个6位数:h * 10000 + m * 100 + s。但是我个人比较喜欢的是转换成秒数——或者说这是60进制的数,也就是转换成h * 3600 + m * 60 + s,这样就可以直接...
0
点赞
评论
收藏
分享
2015-05-07 06:10
[PAT解题报告] A+B for Polynomials
题目输入的是两个多项式,求的是两个多项式的和。 多项式使用非0项的系数和次数来表示的,并且是按降幂输入的。预先给出了非0项的个数(很小,不超过10)。 例如 2 1 2.4 0 3.2 表示2.4x + 3.2, 并且知道次数小于1000,输出也按同样格式输出,注意只输出非0项。 这个题类似于两个有序list的合并,因为多项式的加法无非就是合并同类项而已。 我们做题可以选择最不容易出错的方法,对于本题,因为次数不超过1000,我们用数组表示某个次数项对应的系数再方便不过了,而且数组比链表容易写,出错的可能性低。关键还是数据范围,次数才1000,如果次数达到1...
0
点赞
评论
收藏
分享
1
2
3
4
5
6
7
关注他的用户也关注了:
牛客网
牛客企业服务