PAT | 蓝桥 | LeetCode学习路径 & 刷题经验

你们要不要考虑也节省一下时间~

这份PDF题目叫做《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验 by 柳婼》,希望可以帮助学习算法路上的小可爱们节约时间、少踩一些坑、多走一些捷径~

一年前看过我blog的人应该知道,我曾经开通过知乎的值乎付费咨询,大概开通了大半年时间,期间也收到了很多咨询,绝大多数提问的话题都是“PAT、蓝桥、LeetCode怎么学如何刷题”,我也一一认真做了回答(绝大多数回答都在半小时以上),但是值乎的回答只能够发布语音,而且有回答时效,提问也有字数限制,后来问的人越来越多,我一天要花数小时在知乎回答上,而且回答的都是几乎相同的问题…对于分享算法经验来说,短短半小时确实不够,很多观点无法详细解释缘由,值乎一对一咨询确实不是一个很好的分享算法经验的平台,听者也很难短时间形成对问题答案的清晰理解,所以后来半年前我就关闭了知乎咨询的功能~不过还是有很多小可爱通过各种渠道向我咨询经验等问题,所以我花了好多天时间将这些问题的回答、刷题笔记、经验全都整理在了一份PDF中~这些问题包括:

里面不仅有关于这些竞赛的介绍、应该看哪些书、如何刷题,还有我自己刷算法过程中整理的笔记,目录如下:

这份经验一共3万7千字(想当年800字的高考作文都写那么辛苦…)在算法路上,我能帮的只有这么多了…希望能帮助你们少走很多弯路,少踩很多坑~剩下的就是靠你们自己刷题啦~还和离线版订阅获取的方式一样…打赏29元并备注邮箱号即可…打赏二维码在最下面…24小时内发送到邮箱…(一般一两个小时就收到了~)时间仓促,后期还会对这份文档的内容进行扩充完善…到时候有版本更新还会继续发送到邮箱中~感谢支持与信任~

L3-021 神坛 (30 分)-PAT 团体程序设计天梯赛 GPLT

在古老的迈瑞城,巍然屹立着 n 块神石。长老们商议,选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比,因此神坛的面积越小越好。特殊地,如果有两块神石坐标相同,或者三块神石共线,神坛的面积为 0.000

长老们发现这个问题没有那么简单,于是委托你编程解决这个难题。

输入格式:

输入在第一行给出一个正整数 n(3 ≤ n ≤ 5000)。随后 n 行,每行有两个整数,分别表示神石的横坐标、纵坐标(−109≤ 横坐标、纵坐标 <109)。

输出格式:

在一行中输出神坛的最小面积,四舍五入保留 3 位小数。

输入样例:

8 3 4 2 4 1 1 4 1 0 3 3 0 1 3 4 2

输出样例:

0.500

分析:A中存储神石的点坐标,B中存储去掉枚举点且排序后,两神石的之间的向量值。枚举每一个点作为起始点,按照极坐标将B排序后,按照向量计算中,三角形面积 = 1/2 * |x1y2 – x2y1|,遍历求出最小神坛面积~ 

L3-020 至多删三个字符 (30 分)-PAT 团体程序设计天梯赛 GPLT

给定一个全部由小写英文字母组成的字符串,允许你至多删掉其中 3 个字符,结果可能有多少种不同的字符串?

输入格式:

输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 106] 内的字符串。

输出格式:

在一行中输出至多删掉其中 3 个字符后不同字符串的个数。

输入样例:

ababcc

输出样例:

25

提示:

删掉 0 个字符得到 “ababcc”。

删掉 1 个字符得到 “babcc”, “aabcc”, “abbcc”, “abacc” 和 “ababc”。

删掉 2 个字符得到 “abcc”, “bbcc”, “bacc”, “babc”, “aacc”, “aabc”, “abbc”, “abac” 和 “abab”。

删掉 3 个字符得到 “abc”, “bcc”, “acc”, “bbc”, “bac”, “bab”, “aac”, “aab”, “abb” 和 “aba”。

分析:一个简单的动态规划题~使用dp[i][j]表示前i个字符串在删除j个字符的情况下能取到多少种情况。由于第i个字符只有删除以及不能删除两种情况,可以得到dp[i][j] = dp[i – 1][j](第i个字符不删,前i-1个字符删除掉j个再加上当前字符能取到的个数) + dp[i – 1][ j – 1](第i个字符删了,前i-1个字符删除掉j-1个能取到的个数)~注意可能存在的重复情况,如liuchuo在dp[6][3]时删除下标为3、4、5的”uch”后得到字符串的与删除下标为4、5、6的”chu”后得到的字符串都为”liu”,所以需要记录当前(下标为i)字符上一次出现的位置last(存在vis数组中),并判断i与last的差是否大于等于目前的j,如果更多的话,就已经不可能受到影响了,故需要减去dp[last – 1][j – (i – last)]的数量。 最后将所有删减情况加起来,得到最终答案~ 

L3-017 森森快递 (30 分)-PAT 团体程序设计天梯赛 GPLT

森森开了一家快递公司,叫森森快递。因为公司刚刚开张,所以业务路线很简单,可以认为是一条直线上的N个城市,这些城市从左到右依次从0到(N−1)编号。由于道路限制,第i号城市(i=0,⋯,N−2)与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过Ci​公斤。

公司开张后很快接到了Q张订单,其中j张订单描述了某些指定的货物要从Sj​号城市运输到Tj​号城市。这里我们简单地假设所有货物都有无限货源,森森会不定时地挑选其中一部分货物进行运输。安全起见,这些货物不会在中途卸货。

为了让公司整体效益更佳,森森想知道如何安排订单的运输,能使得运输的货物重量最大且符合道路的限制?要注意的是,发货时间有可能是任何时刻,所以我们安排订单的时候,必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输,则这两张订单的运输同时受2-3以及3-4两条道路的限制,因为两张订单的货物可能会同时在这些道路上运输。

输入格式:

输入在第一行给出两个正整数NQ(2≤N≤105, 1≤Q≤105),表示总共的城市数以及订单数量。

第二行给出(N−1)个数,顺次表示相邻两城市间的道路允许的最大运货重量Ci​(i=0,⋯,N−2)。题目保证每个Ci​是不超过231的非负整数。

接下来Q行,每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法,并且不存在起点和终点重合的情况。

输出格式:

在一行中输出可运输货物的最大重量。

输入样例:

10 6
0 7 8 5 2 3 1 9 10
0 9
1 8
2 7
6 3
4 5
4 2

输出样例:

7

样例提示:我们选择执行最后两张订单,即把5公斤货从城市4运到城市2,并且把2公斤货从城市4运到城市5,就可以得到最大运输量7公斤。

分析:每个路程受到其中最小承重量限制,不同的运输路线[a, b],[c,d]之间有3种关系 1.[a, b]与[c,d]无交集,则可以同时进行两个运输订单 2.如果一个路线包含于另一个路线中,那么选择少的那一段显然更优 3.[a, b]与[c,d]存在交集,交集为[c,b],则能最大运输货物重量为min([c,b],[a,c] + [b,d]。 综上,我们可以将点坐标,按照右端点从小到大的顺序排列,相等的情况下,按照左端点从小到大的顺序排列。只需要建立一棵具有区间加以及区间最小值的线段树即可,符合结分配合律,故不需要lazy数组。遍历排序后的接线信息,每个路线取到最大运输货物后,减少本线路的通货承重量,即可得到最终答案~ 

注意:输入的路线起始与结束不一定小的在前面,大的在后面~  

 

L3-016 二叉搜索树的结构 (30 分)-PAT 团体程序设计天梯赛 GPLT

二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树。(摘自百度百科)

给定一系列互不相等的整数,将它们顺次插入一棵初始为空的二叉搜索树,然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后,得到一棵二叉搜索树,则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”(指自顶向下的深度相同)、“2是4的双亲结点”、“3是4的左孩子”都是正确的;而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。

输入格式:

输入在第一行给出一个正整数N(≤100),随后一行给出N个互不相同的整数,数字间以空格分隔,要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M(≤100),随后M行,每行给出一句待判断的陈述句。陈述句有以下6种:

  • A is the root,即”A是树的根”;
  • A and B are siblings,即”AB是兄弟结点”;
  • A is the parent of B,即”AB的双亲结点”;
  • A is the left child of B,即”AB的左孩子”;
  • A is the right child of B,即”AB的右孩子”;
  • A and B are on the same level,即”AB在同一层上”。

题目保证所有给定的整数都在整型范围内。

输出格式:

对每句陈述,如果正确则输出Yes,否则输出No,每句占一行。

输入样例:

5
2 4 1 3 0
8
2 is the root
1 and 4 are siblings
3 and 0 are on the same level
2 is the parent of 4
3 is the left child of 4
1 is the right child of 2
4 and 0 are on the same level
100 is the right child of 3

输出样例:

Yes
Yes
Yes
Yes
Yes
No
No
No

分析:简单的二叉搜索树内结点关系问题~Tree中存储每个节点的信息,cnt保存每个节点的序列号,root为树的根,f的值表示问讯关系是否成立,Find查询节点数值对应的序列号。insert为插入新节点进入二叉搜索树的函数,按照规则判断左右孩子是否为空(用-1表示),是的话就当成新节点的位置插入~

 

L3-012 水果忍者 (30 分)-PAT 团体程序设计天梯赛 GPLT

2010年风靡全球的“水果忍者”游戏,想必大家肯定都玩过吧?(没玩过也没关系啦~)在游戏当中,画面里会随机地弹射出一系列的水果与炸弹,玩家尽可能砍掉所有的水果而避免砍中炸弹,就可以完成游戏规定的任务。如果玩家可以一刀砍下画面当中一连串的水果,则会有额外的奖励,如图1所示。

现在假如你是“水果忍者”游戏的玩家,你要做的一件事情就是,将画面当中的水果一刀砍下。这个问题看上去有些复杂,让我们把问题简化一些。我们将游戏世界想象成一个二维的平面。游戏当中的每个水果被简化成一条一条的垂直于水平线的竖直线段。而一刀砍下我们也仅考虑成能否找到一条直线,使之可以穿过所有代表水果的线段。

如图2所示,其中绿色的垂直线段表示的就是一个一个的水果;灰色的虚线即表示穿过所有线段的某一条直线。可以从上图当中看出,对于这样一组线段的排列,我们是可以找到一刀切开所有水果的方案的。

另外,我们约定,如果某条直线恰好穿过了线段的端点也表示它砍中了这个线段所表示的水果。假如你是这样一个功能的开发者,你要如何来找到一条穿过它们的直线呢?

输入格式:

输入在第一行给出一个正整数N(≤104),表示水果的个数。随后N行,每行给出三个整数xy1​、y2​,其间以空格分隔,表示一条端点为(x,y1​)和(x,y2​)的水果,其中y1​>y2​。注意:给出的水果输入集合一定存在一条可以将其全部穿过的直线,不需考虑不存在的情况。坐标为区间 [−106,106) 内的整数。

输出格式:

在一行中输出穿过所有线段的直线上具有整数坐标的任意两点p1​(x1​,y1​)和p2​(x2​,y2​),格式为 x1​y1​x2​y2​。注意:本题答案不唯一,由特殊裁判程序判定,但一定存在四个坐标全是整数的解。

输入样例:

5
-30 -52 -84
38 22 -49
-99 -22 -99
48 59 -18
-36 -50 -72

输出样例:

-99 -99 -30 -52

分析:将所有水果信息按照x轴顺序排列好,枚举每一条水果线段,以最它的最低点作为参照点,然后取和其他所有线段点所成直线的交集。如果与所有的水果都有公共的斜率交集,说明存在以枚举线段最低点为刀砍线上的一个点。方便起见,选取其余线段最大斜率的最小值作为目标直线上的另外一个点,即为答案~Fruit中存储每个水果的坐标信息,kmax表示从枚举点出发能经过所有线段的直线的最大斜率,kmin表示从枚举点出发能经过所有线段的直线的最小斜率,tkmax、tkmin为两个水果之间的最大、最小斜率~