- 博客(59)
- 收藏
- 关注
RSS订阅
原创 网易互娱2017实习生招聘游戏研发工程师在线笔试第二场(神奇的数)
题意分析：（1）数论的题目，给出一个long long类型的范围[N,M],求出这个范围中满足三个条件的数的个数：①这个数至少包含('2', '3', '5')中的任意一个数字;② 这个数不能出现'18';③这个数能被7整除。（2）对于第一、三个条件比较好判断，第二个条件可以通过每次将这个数整除10，然后对100取模，看结果是否等于18，如不等于，则再除以10，依次循环，直到除
2016-04-22 22:16:17
2935
4
原创 网易互娱2017实习生招聘游戏研发工程师在线笔试第二场（一起消消毒）
题意分析：（1）题目是模拟开心消消乐的游戏逻辑，当交换两个相邻的图片时，如果交换后的面板中有连续的三个以上的相同的图片（拍成行或列），那么这些排列成行或列的相同的图形将消失，上面的图形将下落填充中间的空白，下落后有可能再次出现可消除的情况，于是同以上步骤，一直到最后没有可消除为止，求这次交换操作一共可消去多少个图形。（2）题目对游戏的原型进行了简化：即消去一部分图形之后，没有新的图形产生，
2016-04-22 21:53:51
2209
原创 网易互娱2017实习生招聘游戏研发工程师在线笔试第二场(图像处理)
题意分析：（1）给出一个N*M矩阵用来表示灰度图像，矩阵中的每一个数的范围在[0,255]之间，定义7种对矩阵的操作：1.顺时针旋转90度，2.逆时针旋转90度，3.上下翻转180度，4。左右翻转180度，5.给矩阵中的某个子矩阵(定义（x0,y0）为子矩阵的左上角，（x1,y1）为子矩阵的右下角）中的每个数加上一个特定的值val，6.同操作5，给子矩阵中的每个数减去val，7.截取矩阵中的某
2016-04-22 20:35:53
2139
原创 pat1056Mice and Rice (25)
题意分析：（1）给出一组数代表每个人的初始程序的“得分”，然后按照给出的一个任意排列的顺序，在这个排列中按照顺序每NG个人一组进行PK,每一组中最大的那个人PK胜出进入下一轮，剩余的人本轮淘汰，并且排名相同。不足NG人的小组按照一个小组计算（2）相信绝大多数人都没有弄清楚这题到底是怎么得出最终的计算排名，原因在以下几个方面：①那个排列就是出场的顺序，也就是每个人按自己的序号出场的顺序（
2015-10-23 16:43:29
1147
原创 pat1055The World's Richest (25)
题意分析：（1）给出若干个富人的姓名 年龄 财富值，以及若干个查询条件：前M名年龄在[a,b]之间的富人，并按照财富值递减 年龄递增 姓名递减的优先级顺序输出这些富人信息（2）水题，简单的排序题，对富人信息包装成结构体，然后排序可能坑点：（1）注意使用cin和cout会超时（2）注意字符串的使用，scanf不支持字符串，但使用C++字符串比较会很简单#include #i
2015-10-23 15:27:55
464
原创 pat1054The Dominant Color (20)
题意分析：（1）给出M*N的像素矩阵，矩阵的每个元素代表24比特的RGB值，找出这个矩阵中总个数超过一半的像素值（一定存在）（2）找出一组数中个数超过一半的数，以下有两种常见思路：①有一种思路是统计每个数出现的次数：先开辟大小为2^24+1的计数数组count，初始化为0，然后依据数组下标作为元素值统计数组中每个元素出现的次数。然后再寻找出现次数最多的那个数。这样做还没等统计完。第二个
2015-10-23 14:22:35
429
原创 pat1053Path of Equal Weight (30)
题意分析：（1）给出一颗树的父子表示关系，给出每一个节点自身编号和节点权值，然后给出每一个非叶子结点及其子节点的邻接关系，然后找出一条路径使得路径上节点的权值之和等于给定的值，若有多条路径，则按照序列的大小关系输出，序列的大小关系指的是：序列a>序列b,则从序列a和序列b的第一个元素开始，第一次出现在同等位置上的a的元素大于b的元素（2）使用DFS从根节点开始遍历，然后记录下当前的非叶子节
2015-10-22 22:36:07
736
原创 pat1052Linked List Sorting (25)
题意分析：（1）给出内存中链表的节点,节点定义为：address value nextaddress并且给出链表的起始地址，按照原来的格式输出这个链表经过按照value排序后的链表，即：链表节点的个数 起始地址以及每个链表的节点（2）因为涉及到链表节点的排序，先将链表的定义包装成结构体，然后按照value值进行排序，因为排序后address域没有发生变化，而nextAddress域变成了排
2015-10-21 16:30:50
494
原创 pat1051Pop Sequence (25)
题意分析：（1）给出若干个从1到N的排列，并且给出栈的深度，问这些排列是否是从1到N的出栈序列（2）判断一个序列是否是一个出栈序列受栈的深度、出入栈的顺序的制约：若入栈个数大于栈的最大深度，则此种入栈方式不合法，对应的序列不是出栈序列；另外由于是按序入栈，如出栈的元素在栈顶的下方，此时出栈的方式不合法，对应的序列不是出站序列。我们可以根据第一个出栈的元素去反推出入栈顺序，再通过比较下一
2015-10-21 15:06:34
450
原创 pat1050String Subtraction (20)
题意分析：（1）水题，给出两个字符串，按照相对顺序输出字符串1中除去字符串2包含的字符的剩余字符（2）建议不要暴力，O(mn)的复杂度肯定超时，首先在字符串1输入完之前，我们确实什么也干不了，那就直接用getline取字符串存好，这样效率高。在输入字符串2的时候，我们不要等输入完后再去处理，而应该在输入的时候就去处理，因为是字符，用ASCII来表示就是0~128之间的整数，因此没输入一个字
2015-10-16 19:56:28
432
原创 pat1049Counting Ones (30)
题意分析：（1）给出一正整数N，求从1到N之间的所有数当中含有1的个数（2）此题最容易想到的是从1到N遍历，求每个数中包含1的个数，但这样在数字比较大时，肯定超时。如果不遍历，那要怎么去求呢？这就需要寻找数学规律了。我们先从每一位开始：求当某个位置为1时共有有多少个数.以百为为例，如12145、12045、12145.即可能存在三种情况：①若此数百位本身就等于1，如12145，则大于等
2015-10-16 18:16:22
1061
原创 pat1048Find Coins (25)
题意分析：（1）给出若干个面值不同的硬币，可以重复，再给出任意一个金额，问是否能在这些硬币当中找出两个面值之和等于所给的金额，若有多种组合，给出具有面值最小的那个组合。（2）这题是一种超级经典的利用位图排序的例子。可以说如果了解了位图排序的精髓，这题除去输入时间，算法的时间复杂度可以控制在O(1)！！！极大地提高了算法的时间和空间效率。真可谓“大道至简”。有两种思路，第一种给出最容易想到的
2015-10-15 19:29:10
523
原创 pat1047Student List for Course (25)
题意分析：（1）此题和1039题正好相反，给出若干个学生的选课表，每个学生的ID由三位大写字母和一位数字组成，后面跟上选的课程总数以及课程的ID。按照课程的ID从小到大的顺序并按照字典序列出选择这门课程的学生的ID,（2）此题确实和1039题差不多一致，但如果是受1039题思路的引导，极有可能掉入陷进。这也是PAT以“坑”著称的地方。现在是我们要对每门课程维护一个列表，若某个学生选择了课程
2015-10-15 17:25:15
733
原创 pat1046Shortest Distance (20)
题意分析：（1）给出一个环形公路中几个相邻出口之间的距离，然后任意给出若干对出口，求出这些出口之间最短的距离，（即从一个出口沿着两个方向到达另外一个出口的最短距离）（2）建议大家画一个示意图，分别求出沿着两个方向遍历到达另外一个出口的距离，然后比较这两个距离（3）这题坑在第三个案例上面，即使是时间复杂度为O（n）的如此简单算法，PAT的出题人也要在此设坑，简单的遍历都会超时，看来我们不
2015-10-14 22:03:19
591
原创 pat1045Favorite Color Stripe (30)
题意分析：（1）给出一个有若干个数的偏好序列，同时给出另一个任意的数组，并且参照前面序列中元素出现的相对顺序（某些元素可以丢弃）依次从前往后选择数组中的元素组成一个新的数组，求这个数组的最大长度。（2）由于求解的是从数组A中下标范围到i这个序列的顺序，选择数组B中下标范围到j的最长数组的长度，可以分解为：A中下标范围到i,B中下标范围到j-1与A中下标范围到i-1,B中下标范围到j这两个子
2015-10-13 21:07:03
676
原创 pat1044Shopping in Mars (25)
题意分析：（1）给出一个整数序列，截取这个序列中的一段连续的子序列使得这个子序列的和等于给定的值，若不存在这样的序列，则找出序列的和大于给定值并且差值最小的。如有多个这样的序列，按照左边界的升序输出这些边界（2）一种简单的方法是从第一个位置开始，依次计算从第1、2..开始的连续和到等于M或者第一次大于M,在从第二个位置开始依次类推，这样时间复杂度就是o（n^2），很遗憾，这样的方案会导致有
2015-10-13 16:33:58
563
原创 pat1043Is It a Binary Search Tree (25)
题意分析：（1）给出一数列，判断这个数列是否是一个二叉查找树的先序遍历序列或镜像二叉查找树的先序遍历序列，所谓镜像二叉查找树就是二叉查找树所有节点的左右子树交换后的二叉树（2）二叉查找树有一个特性就是根节点左边所有子树节点的值小于根节点的值，右子树所有节点的值大于或等于根节点的值，同时左右子树也是一颗二叉查找树（3）由（2）的递归的性质：于是判断这个序列是否是BST或者镜像BST先序遍
2015-10-13 16:15:42
487
原创 pat1042Shuffling Machine (20)
题意分析：（1）给出54张扑克牌的原始顺序，给出任意1~54的排列，此排列意味着对本次扑克牌位置的调整，数组中的序号为a的值b,意味着将原来在a位置的扑克牌移动到第b号位置，求按此排列洗牌K次后的顺序。（2）因为每次所给的调整顺序一样，对于原始序列中的第i个牌，我们暂且就将他记为i，追踪它在K次调整后“花落谁家”，假设为j，然后用另外一个数组newOrder在第j个位置存i.这样每一张扑克
2015-10-12 22:39:04
664
原创 pat1041Be Unique (20)
题意分析：（1）给出一组数，找出这组数中第一个在此数列中只出现一次的数（2）水题，开辟一个数组作为位图索引使用，每出现某个数一次，就在索引位置+1，同时使用vector记录下原来的数组顺序,以便后面遍历使用，当第一次遍历到某个数时，其索引数组对应的位置值为1，则输出可能坑点：（1）不要对数组中每个元素采用循环遍历的方法，否则超时#include #include #incl
2015-10-12 21:14:39
501
原创 pat1040Longest Symmetric String (25)
题意分析：（1）给出一串字符串，求出其中最长的回文字串的长度（2）比较简单的做法是从第一个字符开始，依次同时向两边扩散检索，直至扫描整个字符串串结束。但需要注意子字符串长度为奇数和偶数时他们的扫描是不同的。（3）有一种比较难以想到动态规划做法是：将整个串str看作要求解的问题，他可以分解为str[0]~str[N-2]、str[1]~str[N-1]、str[1]~str[N-1]这三
2015-10-12 19:12:42
448
原创 pat1039Course List for Student (25)
题意分析：（1）给出每个课程的编号以及选课的人数和选课的学生的姓名，给出若干个同学的姓名，要求按照给出的顺序列出每个学生选定的课程数、课程编号（按照从小到大的顺序）（2）题目意思很简单，在做的过程中，可能会有多种方案，相信大家大部分人前面几个案例都可以过，就是最后一个案例要么超时，要么内存超限。因为涉及到根据字符串来索引列表，并且对索引到的结果排序。根据此思路就会出现三种做法，每一次都会从
2015-10-12 15:16:08
412
原创 pat1038Recover the Smallest Number (30)
题意分析：（1）给出若干个整数片段，问按怎样的顺序组合这些片段，使得这些片段组合起来后的数最小，求出这个最小的数（2）要确定这些片段的顺序，首先要明确的就是对于任意两个片段来说，确定其相对位置来说是很简单的，两个片段a、b，最直接的方法就是判断他们按两种方式连接后ab和ba的大小，如果这些片段都是字符串，那么ab和ba都是相同位数的，直接利用C++字符串比较即可（3）按照（2）的排序规
2015-10-12 10:09:23
579
原创 pat1037Magic Coupon (25)
题意分析：（1）给出两组数列，求从数列一中选择一部分数（可全选，也可只选其中一部分）与数列二中的一部分数相乘后（一一对应），将所得的乘积相加，求最大的和是多少（2）水题，首先需要明确一点：要使得和尽量大，那么每一项乘积必然要保证大于0，也就是相乘的两个数同号，另外，要使得结果最大，应该是最大的正数与最大正数相乘、最小负数与最小负数相乘，所谓"强强联合"，然后依次往后。（3）按照（2）思
2015-10-10 22:47:44
538
原创 pat1036Boys vs Girls (25)
题意分析：（1）水题，没有什么好分析的。不需要开数组，只需要维护两个结构体，一个是最高分女生、一个最低分男生，然后边输入边更新这两个结构体。可能坑点：（2）因为分数的范围是[0,100]，初始的最高分女生分数要设置为-1，不能为0，以免出现女生全是0的话，则不能更新，男生要设置为101，同理。#include #include using namespace std;str
2015-10-10 21:41:24
420
原创 pat1035Password (20)
题意分析：（1）给出若干个PAT考试登陆账户，为了防止账户密码中有个别引起混淆的字母和数字（l,1,O,0），统计密码中出现可能混淆的字母的账户个数，并将修改后的账户按原来的顺序输出可能坑点：（1）注意：当没有出现混淆字母的账户时候，如果原来有N条记录，则要区分N=1和N！=1时候，输出结果的account和accounts单复数之别（2）注意，在G++的编译器当中，当使用cout
2015-10-10 20:45:41
665
原创 pat1034Head of a Gang (30)
题意分析：（1）给出若干条通话记录（包括通话的两端的ID、时长），通过通话记录找出其中有多少个团伙，以及每个团伙的首领和团伙人数，所谓团伙就是指通过话的“联通”组织超过三人，可以理解为连通分量的人数超过三人，且集体通话时长超过一个给定的阈值。团伙首领是指在这个团伙中，这个人的通话时长最长（2）此题的目标是寻找满足权值超过阈值、节点数超过2的联通分量，最简单的方法就是通过深度优先搜索遍历整个
2015-10-10 18:30:08
1349
1
原创 pat1033To Fill or Not to Fill (25)
题意分析：（1）给出从出发地到目的地之间的若干个加油站的信息（每升价格 距出发点距离）以及油箱容量、目的地、每升油公里、油站数，出发时油箱为空，问要到达目的地的最少开销，如不能到达目的地，求出最多能够走多远。这题分明显是一道贪心算法题，贪心算法题最主要的是理清贪心的策略：算法前准备：①将站点信息包装成结构体②输入的站点时候过滤掉在目的地之外的站点（距离超过目的地），这些站点毫无
2015-10-07 21:04:14
598
原创 pat1032Sharing (25)
题意分析：（1）找出两个单词公共后缀的起始地址，单词以字符链表的形式存储起来，因为地址是5位整数，并且地址上的前驱后继关系唯一，因此开辟一个数组，其下标用来表示地址。因为题目给出的字母顺序是乱的，最好先用map存储链接关系。这样遍历效率会更高。遍历地址，并置数组相应的位置为1，当便利第二个单词的时候，当访问到此地址已经标记为1，则为公共后缀的开始位置。可能坑点：#include #i
2015-10-04 23:00:06
582
原创 pat1031Hello World for U (20)
题意分析：（1）给出一个长度大于5的字符串，然后从上到下输出n1个字符,从左到右到右输出n2个字符（包括边界，也就是n1的最后一个字符）,从下到上输出n3个字符，让结果尽可能呈现方形，按照题目中公式的理解:n1=n3（2）按照打印规则，在求出n1,n2,n3之后，先输出字符串第一个字符，中间应该空出n2-2个字符（因为n2也包括了n1和n3最底下的两个字符），再输出最后一个字符，依此类推。
2015-10-04 22:50:25
430
原创 pat1030Travel Plan (30)
题意分析：（1）给出城市的的地图分布以及道路距离和每条道路的开销，给出出发点到目的地，找出最短路径，若有多条这样的路径，选择开销最小的（2）这种题目已经不是什么难题了，之前的有很多这样的题目，参考1003（Emergency）、1018(Public Bike Management),都是深度优先，然后回溯，更新当前最短路径，而且由于开销并不是全局的，所以当最短路径更新的时候，开销要强制更
2015-10-04 21:54:03
427
原创 pat1029Median (25)
题意分析：（1）给出两个有序序列，求这两个有序序列的中位数。（2）由于合并两个有序序列，再排序取中位数，复杂度为O(nlogn)，会有几个案例超时,考虑到中位数的特殊性质，中位数一定是一个有序序列的中间位置的那个数，如果我们呢合并两个序列，那样之前给的两个有序序列这个条件我们就没用上。我们可以通过两个指针从队首依次顺序比较这两个序列的值并计数，数到第（M+N）/2的那个元素就是中位数了
2015-10-04 21:32:44
484
原创 pat1028List Sorting (25)
题意分析：（1）简单的排序题，按照不同的索引给学生的考试信息进行排序可能坑点：#include #include #include #include using namespace std;struct student{ char ID[7]; char name[9]; int score;};student stu[100001];bo
2015-10-04 21:21:16
444
原创 pat1027Colors in Mars (20)
题意分析：（1）水题：给出三个（0~168）十进制数，转换成13进制的数（0~9，A=10,B=11,C=12）按格式输出（2）进制转换使用除留余数法，对于余数大于9的需要变化成对应字符可能坑点：（1）当转换后只有一位的时候，需要补全前导0#include #include using namespace std;void transToMars(int num){
2015-10-04 21:16:06
428
原创 pat1026Table Tennis (30)
题意分析：（1）给出N个人到达乒乓球场的时间以及他们需要打多长时间的球，这些人分为两类：一类是VIP客户，一类是非VIP客户，所有的客户按到来的时间排好队伍等候，一旦出现空的乒乓球台，客户将立即选择编号最小的乒乓球台，每个客户最多不能超过两个小时，求每个客户的等待时间，以及每个乒乓球台一天服务了多少人。（2）VIP客户与普通客户不同点在于：一旦有VIP桌子空闲，处于等待队列中的最早到达的V
2015-10-04 20:20:29
2074
4
原创 pat1025PAT Ranking (25)
题意分析：（1）给出多个考点的考试人数以及考生考号和成绩，求出所有参加考试的人最终排名、考场编号、本考场排名（2）水题，考察排序，排名的规则按照以前的做法：按分数由高到低，同分同名次，不同分，按其在序列中的位置算排名可能坑点：#include #include using namespace std;struct testee{ string ID; in
2015-10-04 19:50:57
434
2
原创 pat1024Palindromic Number (25)
题意分析：（1）给定一个正整数N，如不是回文数，执行N+N各位数字颠倒后组成的数，求在第几步之后得到的结果是回文数。（2）由于涉及到调换数的位置的操作，并且当我们看到N可能坑点：（1）即使是用long long类型也未必保险，因为K是在100以内的。#include #include using namespace std;bool isPalindromic(stri
2015-10-04 17:35:45
410
原创 pat1023Have Fun with Numbers (20)
题意分析：（1）水题，给出一个长度在20以内的正整数，问翻倍之后结果是否是原来的数的各位数字组成的一个新排列（2）使用数组num[10]来统计每个数字出现的频数，输入数字时，在对应的下标位置开始计数，遍历结果时，执行对应下标位置自减，最后遍历数组，有不为0的则不是可能坑点：（1）20位以内的整数可能已经超出long long类型的范围，还是采用字符串或者是字符数组来处理#inc
2015-10-04 17:23:19
465
原创 pat1022Digital Library (30)
题意分析：（1）给出若干条书籍信息：按照书名、作者、关键字、出版商、出版年份的格式列出；再给出若干条检索记录，这些检索记录是围绕书名、作者、关键字、出版社以及年份，来按顺序列出查询的书的ID,考察的是排序和查找。（2）将书的信息包装成结构体，在这些结构体当中，比较容易检索的包括书名、作者、出版社、出版年份；而对于关键字来说，由于每本书最多会有5个关键字，书的数目比较大时，如果将关键字向量或
2015-10-04 16:46:52
1732
1
原创 pat1021Deepest Root (25)
题意分析：（1）这一题型比较巧妙，直接给出一个树的拓扑结构，求出这棵树最深的根，言外之意就是指：当以这个节点为根的时候，树具有最深的深度。若这个图具有多个连通分支，就输入分支数。（2）首先给出算法，随后证明这个算法一定能找到它所有的最深根：第一步：从任意一个节点开始进行深度优先遍历，找到离他最远的节点（可能不止一个，记为集合A）；第二步：再从A中任意选一个节点出发进行深度优先遍历，找到离他
2015-10-03 18:26:34
1204
3
原创 pat1020Tree Traversals (25)
题意分析：（1）这是很数据结构中很经典的一类题型，给出中序序列和先序或者后序序列中的一种，求另外另类序列。一般若是求层序，需要构建二叉树，如果不是，可以不用建树；（2）建树的过程是一个递归的过程，最后按层次遍历打印可能坑点：（1）建树的时候大多数人可能坑在不知道应该如何传根节点的指针。其实很简单，因为需要建树，调用建树操作一定是最后影响到这个指针的，所以一定要使用引用#incl
2015-10-03 18:11:53
453
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人