Peterliang

分类

PAT挑战日记(15) 《算法竞赛进阶指南》系列题解(4) 心路历程(1) 未归档(5) 模板(2) 题解(145)

/ 注册

全部文章（共171篇）

JZ66 机器人的运动范围

题意分析给我们一张二维的地图，初始的位置在（0,0），可以往上下左右四个方向进行移动。但是移动需要需要满足如下条件：不能超过地图的边界移动的位置的坐标的数位的数字的和不能超过给定的数字思路分析这个题目我主要用的是BFS和DFS这两个算法进行求解。可以结合这个图进行理解。...

题解刷题

2021-07-14

1 874

JZ26 题解 | #二叉搜索树与双向链表#

题意分析给出一棵二叉树，我们需要按照这棵树的节点的权值的大小先进行升序排序，然后在不改新增节点的前提下将它改为一条双向链表。原来的左指针作为一个前驱指针，右指针作为一个后继指针。思路分析解法一对于这个题目，一开始想的是用一个map存储每个数字对应的一个节点，这种的思路其实是有问题的...

题解刷题

2021-06-23

2 1427

JZ24 题解 | #二叉树中和为某一值的路径#

题意分析给你一棵二叉树，需要求出这棵二叉树从根节点到叶子节点形成的连续的路径中路径和等于给定的数字的情况，并且按照字典序输出。样例解释对于样例一，我们发现一共存在三条路径，分别为[10,5,4],[10,5,7]和[10,12].所以我们样例就很好理解了。思路分析 DFS+回溯法 ...

题解刷题

2021-06-23

1 776

JZ35 题解 | #复杂链表的复制#

题意分析感觉这个题目意思还是比较难理解的。但是幸好给出了样例的相关解释，就是给出一个固定的链表，需要我们对这条链表进行深拷贝，然后返回一个新的链表的头即可。解决这个题目的关键，首先是需要理解什么是深拷贝。深拷贝：从堆内存中开辟一个新的区域存放新对象，对对象中的子对象进行递归拷贝,拷贝前...

题解刷题

2021-06-23

0 691

JZ27 题解 | #字符串的排列#

题意分析题意给出一个字符串，需要返回这个字符串的所有的字符按照字典序的全排。（一个很经典的模板题）前置知识 DFS的回溯法，这里我默认读者掌握了DFS的基本思想。所以我这里主要来介绍一个什么是回溯法。我们来结合这个图来帮助大家理解什么是回溯法，这里介绍的是一棵二叉树的一个回溯，其实...

题解刷题

2021-06-23

1 1263

JZ28 题解 | #数组中出现次数超过一半的数字#

题意分析给出一个数组，我们需要找出在这个数组里面出现的次数超过这个数组长度的一半的那个数字。思路分析思路一由于需要我们求出众数，那么我们可以尝试着先进行排序，然后我们只需要遍历排好序的数组就行了，这种情况下排序的时间复杂度是,但是我们遍历的时候如果最好只要n/2+1就行，最差就是n。由...

题解刷题

2021-06-23

1 1240

JZ29 题解 | #最小的K个数#

题意分析根据题目我们可以知道，就是给出一个数组，让我们求出最小的k个数字所构成的数组。如果不足以构成k个数字，那么就返回一个空数组。样例解释，这里我用的是第二种解法思路分析解法一根据题目的要求，需要我们求出最小的k个数字，对于这种有大小顺序的情况，我们很容易想到的就是先进行排序...

题解刷题

2021-06-23

14 3029

JZ30 题解 | #连续子数组的最大和#

题意分析给出一个数组序列，找出和最大的连续子数组的和。并且要求时间复杂度O(n)（由于这个题目比较简单，所以我们重点放在如何解题上面）考点是差分前缀和，下面大家可以结合下面这个图来更好地理解什么是差分思想，其实这只是一个很基础的一个差分，差分思想还是很重要的，可以帮助我们更好地优化我们的代码。...

题解刷题

2021-06-23

6 1465

JZ23 题解 | #二叉搜索树的后序遍历序列#

题意分析题意给出一个二叉树的后序遍历的结果，需要我们判断这棵二叉树是否为二叉搜索树。样例解释首先，我们来说明一下本题目的样例样例如上图，看图知道，这个就是一个二叉搜索树。所以返回的是true。但是，我们如何用程序实现这种判断呢？前置知识什么是二叉搜索树，简单来说，就是对于一个二...

题解刷题

2021-06-21

1 915

JZ22 题解 | #从上往下打印二叉树#

题意分析首先，这个题目没有说明数据是如何给出的，建议补一个样例的解释。另外，这个题目的难度应该属于简单范围。这是我对本题样例的理解。题目给出一个二叉树的先序遍历的序列，需要我们求出这个二叉树的层序遍历的序列。样例解释如上面所示。前置知识首先，我们需要知道什么是二叉树，简单来说就是一个一棵树...

题解刷题

2021-06-20

1 948