9 sheepyWYY

尚未进行身份认证

暂无相关描述

等级
TA的排名 4w+

1147 Heaps 解析

感觉最近两次30分的题,不像以前那么麻烦了...检查最大最小堆.然后做一个后续遍历...序号从1开始就好了..多注意下端点的值,别搞错就好了。#include<iostream>#include<string>#include<string.h>#include<queue>#include<map>#inc...

2019-02-19 23:34:04

1146 Topological Order 解析

初看题目.妈耶...拓扑排序.只知道手工算。没敲过代码啊啊啊....绝望.jpg..再仔细看题...发现...emmmm貌似标记有没有前驱指向当前的点就好了..前驱为0,就OK。否则就不是拓扑序列。这个貌似叫入度???这中间闹了一个小插曲,不知道你们会不会遇到。我处理的时候是同步处理的,就是读一个数判定一次,失败就跳出。这一跳出就出问题了。怎么都查不出来怎么回事。算法怎么想都没有问题...

2019-02-19 23:32:07

1145 Hashing - Average Search Time 解析

这个很少有的直接考hash的实现..依然素数直接存着保存时间。Hash的停止判定我有些忘了...看别人的解法是循环表长次没有插入就失败..记得不是太清楚了...这个题有点水的成分,要再看看hash了。#include<iostream>#include<string>#include<string.h>#include<queu...

2019-02-19 23:27:13

1144 The Missing Number 解析

这个题没什么好说的。常规的hash就好了,然后遍历。注意数值的范围就好了。#include<iostream>#include<string>#include<string.h>#include<queue>#include<map>#include<set>#include<stack...

2019-02-19 23:23:37

1143 Lowest Common Ancestor 解析

开始看到这个题觉得还挺简单的..写个带父节点的BST直接遍历就好了。结果还是太年轻....会超时...于是,我们就要在查找的过程中做手脚了..我们同时在树里面查找两个节点,每一轮找完之后,如果发现两个节点一样,我们就记录下来,就是他们的共有父节点。这样就能省下一次查找的时间。另外这个题的一个坑点:仔细审题:iftheLCAisfoundand A isthekey....

2019-02-16 15:05:28

1142 Maximal Clique

许久没有练习PAT了,是时候刷一刷新的PAT了。感觉现在图的题换了风格。这个题目的Clique的主要解法还是:从一个点开始构建整个Clique,每次添加一个点,如果这个点和已经在Clique集合里面的点都临界我们就把他加入到Clique集合里面来。补充一下后面修改的时候遇到的问题。感觉这个题还是验证原序列之后再添加邻接点好一点。不然直接算可能性还是比较多可能性的。我现在写的程序有...

2019-02-12 21:22:55

1139. First Contact 解析

这个题真的是恶意满满...找同性的你们还找中间人emmmmm 如果把4位id当作整数去处理就会遇到极大的坑:1.有小于4位的值,输出的时候需要补零2.最大的坑.case2中会有-0000 http://blog.csdn.net/gl486546/article/details/78816363 看这个大神的帖子才发现这个问题,之前想到了0点会有问题,但是真的没有想到会出-0这样

2018-01-04 21:39:59

1138. Postorder Traversal 解析

刚开始看题,觉得怎么考这么简单的题。。然后一看N50000就知道是个大坑了.建树是不行的.时间会超,递归到第一个值就可以了#include#include#include#include#include#include#include#include#include#include#defineMAX50010usingnamesp

2018-01-04 21:33:10

1137. Final Grading 解析

要注意主要是取百分比的时候需要进位。按四舍五入的规则就好。#include#include#include#include#include#include#include#include#include#include#defineMAX10010usingnamespacestd;intp,m,n;structnode{ s

2018-01-04 21:30:11

1136. A Delayed Palindrome 解析

用string读入来回倒吧,写个简单的加法就好。#include#include#include#include#include#include#include#include#include#includeusingnamespacestd;stringn;boolisPal(strings){ stringans;

2018-01-04 21:27:26

1135. Is It A Red-Black Tree 解析

当时被红黑树吓傻了。。。然后走上了不归路。主要还是没有理解红黑树也是一个顺序树,中序就是从小到大的顺序。然后结合给的前序建树。后面判定的时候也是没有理解那个任意定点到树叶节点黑色节点数相同的意思。当作黑色节点高度这样去想会容易不少。还是知道的太少了。。#include#include#include#include#include#include#i

2018-01-03 23:05:05

1134. Vertex Cover 解析

这个题还是挺有新意的,要想想才能做。当时不知道怎么回事绕进去了。估计一直做图的题做傻了。。。。这个题需要反过来想。把边编号,然后放到对应的定点vector里面去,然后对给的顶点集去访问边,看边有没有全部被访问。#include#include#include#include#include#include#include#include#include

2018-01-03 23:02:11

1133. Splitting A Linked List 解析

就是把一个链表按负数,0-k,大于k的顺序排序。emmm 直接老办法。遍历链表的时候放到不同的vector里面去,后面倒到一起输出就好了。#include#include#include#include#include#include#include#include#include#defineMAX100000usingnam

2018-01-03 23:00:24

1132. Cut Integer 解析

就是把两个数拆成两截,然后看能不能被两部分整除~int就足够了没有溢出的情况#include#include#include#include#include#include#include#include#includeusingnamespacestd;intn;stringnum;inta,b,z;bools

2018-01-03 22:58:40

1115. Counting Nodes in a BST 解析

按要求建立BST树然后层序遍历,统计每层的个数和最大层数,按要求输出最后两行个数就好。#include#include#include#include#include#include#include#include#include#defineMAX10010usingnamespacestd;intn;structnode{

2017-09-01 00:33:05

PAT 甲级 汇总

终于把PAT甲级的题目都补齐啦~~~撒花~~~臭不要脸的给自己弄了个汇总23333。1001.A+BFormat解析http://blog.csdn.net/sheepywyy/article/details/539950441002.A+BforPolynomials解析http://blog.csdn.net/sheepywyy/a

2017-08-12 22:59:06

1072. Gas Station 解析

这个题的题目真的是好长好长,而且要理清的东西挺多的。不过后面的输出给了比较时候要用的数据的提示。首先,我们要保证加油站到居民楼越远越好,靠的是min{加油站到剧名楼的距离}的大小,取大的。然后min{}还相等,取avg{加油站到剧名楼的距离}的大小,取小的。然后avg{}还相等,取编号小的。这个题为了便于处理,我把编号连续化了,居民楼的编号排前面,加油站的接在后面。这样dijstr

2017-08-12 22:47:53

1065. A+B and C (64bit)

主要考察数据相加会溢出的问题。溢出只有两种情况1、正+正溢出为负肯定比c大2、负+负溢出为正肯定比c小考虑好这两个就问题了。#include#include#include#include#include#include#include#include#include#includeusingnamespaces

2017-08-11 23:19:31

1064. Complete Binary Search Tree 解析

参考了 http://blog.csdn.net/iaccepted/article/details/20726067 的思想这个题很好的利用了树的的各种性质,很值得琢磨。首先:完全二叉树放在以1为开始编号的数组中满足左孩子的编号=root编号*2;右孩子的编号=root编号*2+1;而且按数组顺序输出直接就是层序遍历的顺序。其次:二叉搜索树的中序序列就是顺序排序

2017-07-27 00:24:10

1063. Set Similarity 解析

参考了 http://blog.csdn.net/u014646950/article/details/47608823 的做法刚开始做的时候最后一个测试点总是超时。应该直接把重复的都去除掉,用set自带的查找去完成(效率高),没找到会返回结尾来判定是否找到。#include#include#include#include#include#include#inc

2017-07-27 00:19:58

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!