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

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

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

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

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

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

PAT 1155 Heap Paths (30 分)- 甲级

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))

One thing for sure is that all the keys along any path from the root to a leaf in a max/min heap must be in non-increasing/non-decreasing order.

Your job is to check every path in a given complete binary tree, in order to tell if it is a heap or not.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (1<N≤1,000), the number of keys in the tree. Then the next line contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.

Output Specification:
For each given tree, first print all the paths from the root to the leaves. Each path occupies a line, with all the numbers separated by a space, and no extra space at the beginning or the end of the line. The paths must be printed in the following order: for each node in the tree, all the paths in its right subtree must be printed before those in its left subtree.

Finally print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all.

Sample Input 1:
8
98 72 86 60 65 12 23 50
Sample Output 1:
98 86 23
98 86 12
98 72 65
98 72 60 50
Max Heap
Sample Input 2:
8
8 38 25 58 52 82 70 60
Sample Output 2:
8 25 70
8 25 82
8 38 52
8 38 58 60
Min Heap
Sample Input 3:
8
10 28 15 12 34 9 8 56
Sample Output 3:
10 15 8
10 15 9
10 28 34
10 28 12 56
Not Heap

题目大意:给出一颗完全二叉树,打印出从根节点到所有叶节点的路径,打印顺序先右后左,即先序遍历的镜像。然后判断该树是大顶堆、小顶堆或者不是堆~

分析:1.深搜打印出所有路径(从右往左,即先序的镜像),vector保存一路上的节点,通过push和pop回溯,维护路径,index <= n是对只有左叶节点没有右叶节点的点特判
2.判断是否为堆:从第二个节点开始遍历,如果比父节点小,就不是小顶堆,如果比父节点大,就不是大顶堆~

 

在二叉树中有两个结点m和n,若m是n的祖先,则使用后序遍历可以找到从m到n的路径

首先需要理解的是,前中后序遍历都是通过递归的方式,将后来需要用到的结点保存在栈中,比如下面这颗树:

如果是前序遍历,根左右,过程是:根节点m入栈并输出,访问m的左孩子a,a入栈并输出,访问a的左孩子c,c入栈并输出,c没有左孩子,无元素入栈,c没有右孩子,无元素入栈,c出栈,此时栈顶元素为a,访问a元素的右孩子d,d入栈并输出,d没有左孩子,无元素入栈,d没有右孩子,无元素入栈,d出栈,a左右子树都访问完了所以出栈,现在栈顶元素是m,m已经没有作用了所以出栈,访问m的右孩子b,m的右孩子b入栈并输出,接着访问b的左孩子e,e入栈并输出……

如果中序遍历,左根右,过程是:根节点m入栈,访问m的左孩子,所以m的左孩子a入栈,访问a的左孩子,所以a的左孩子c入栈,c没有左孩子,c现在输出并出栈,c没有右孩子所以没有元素入栈,现在栈顶元素是a,a输出并出栈,a的右孩子d入栈,此时d没有左孩子所以没有元素入栈,d输出并出栈,d没有右孩子所以没有元素入栈,现在栈顶元素是m,m输出,此时m已经没有作用了所以出栈,m的右孩子b入栈,访问b的左孩子,所以b的左孩子e入栈……

所以在前序和中序的过程中,如果n在m的右子树部分,遍历过程中找到了n,但是m已经不在栈中,因为栈中只会保留等会需要用到的e和b结点,而m已经完成了访问根结点和m的左子树的任务,已经被出栈,所以无法追溯n如何走到m

但是后序遍历就不一样啦,后序的顺序是左右根,所以只要m的左右子树还没遍历完成,m就不能出栈,在遍历m的左右子树过程中,无论在m的左边还是右边找到了n,都可以直接返回然后根据栈中的路径让n找到回到m的路,这样就能找到m到n的路径~

所以一旦n在m的右子树,且离的较远,m就会在前序和中序的过程中因为已经完成了访问左、访问根的任务,而被栈遗忘,让找到了n的时候也不知怎么回到m……而只有后序会让作为祖先(子树的根)的m永远被铭记直到n找到m为止…

【iOS】Tab Bar 的 Item 按钮的像素大小要求

根据苹果官方人机界面指南(Human Interface Guidelines)可以得知:

iOS系统会根据设备和方向显示两种标签栏:常规(Regular)紧凑(Compact),所以在设置自定义Tab Bar Item的时候也应该包含常规和紧凑两种不同的尺寸

根据图形是圆形、方形、宽形、高形,像素也有不同的要求:

如果图标是圆形的,应该提供:25pt@2x、25pt@3x、18pt@2x、18pt@3x

如果图标是方形的,应该提供:23pt@2x、23pt@3x、17pt@2x、17pt@3x

如果图标是宽形的,应该提供:31pt@2x、31pt@3x、23pt@2x、23pt@3x

如果图标是高形的,应该提供:28pt@2x、28pt@3x、20pt@2x、20pt@3x

以下是完整表格~