Peterliang

题解

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

/ 注册

全部文章 / 题解（共52篇）

NC2 题解 | #重排链表#

题意分析给出一个链表，需要我们对这个链表进行重新排列，交错取出原来的链表最前面没有被取过的和最后面没有被取过的结点，新的链表就是按照这个取出的顺序重新拼接而成的一个链表。样例解释思路分析题目的意思是给我们一个链表的头结点，需要我们不能改变结点内部的值，只能改变结点的next指针。这样...

牛客题霸题解

2021-07-15

2 1056

NC1 题解 | #大数加法#

题意分析这个题目让我们求出两个很大很大的数的和。思路分析思路一用Python 我们知道，目前对于大多数高级语言，都存在着对高精度的处理。所以我们直接使用Python就行了。代码如下** 需要遍历字符串a和b的每个字符，时间复杂度为O(lena+lenb) 需要存储a和b字符串，空...

题解刷题牛客题霸

2021-07-15

34 6444

JZ67 题解 | #剪绳子#

题意分析题目的意思是给出一个数字，让我们将这个数字进行分解，然后找到分解后所有的数的乘积最大的情况。样例分析，我们可以将8分解为2x3x3，得到的结果就是18,这个可以自己暴力枚举一下所有的情况进行验证。思路分析这个题目，我主要用的是三种方法进行解答解法一暴力枚举我们可以发现...

题解刷题

2021-07-14

3 947

JZ66 机器人的运动范围

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

题解刷题

2021-07-14

1 862

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

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

题解刷题

2021-06-23

2 1430

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

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

题解刷题

2021-06-23

1 777

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

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

题解刷题

2021-06-23

0 691

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

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

题解刷题

2021-06-23

1 1263

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

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

题解刷题

2021-06-23

1 1242

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

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

题解刷题

2021-06-23

14 3029