Peterliang

题解

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

/ 注册

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

NC161 题解 | #二叉树的中序遍历#

NC161 题解 | #二叉树的中序遍历# 题意分析给你一棵二叉树，需要你给出这棵二叉树的中序遍历的序列。思路分析这是一个很经典的题目，主要的考察点就是DFS递归的思想，首先，我们需要知道什么是中序遍历？中序遍历就是先遍历二叉树的左子树，然后遍历二叉树的根节点，然后遍历二叉树的右子树。对...

Go

2021-11-12

0 715

NC160 题解 | #二分查找-I#

NC160 题解 | #二分查找-I# 题意分析在一个升序，没有重复元素的序列里面找到一个固定的目标值，返回这个下标，没有就返回-1 思路分析解法一循环遍历直接对整个数组进行暴力求解，遍历整个数组即可。代码如下遍历的时间复杂度为O(n)O(n)O(n) 过程中只用了少数几个变量，...

Go

2021-11-10

0 510

NC157 题解 | #单调栈#

NC157 题解 | #单调栈# 题意分析给我们一个数组，我们需要找出每个位置左边和右边最近的比这个位置的数字小的数的位置、如果没有。那么就用-1表示。思路分析暴力模拟这里，我们先直接按照题目的意思进行暴力模拟，我们遍历整个数组，对于寻找左边的位置，我们从这个位置的前一个位置进行枚举，...

C++

2021-11-10

0 473

NC140 题解 | #排序#

NC140 #排序# 题意分析一个面试经常会问的题目，考察基本的排序。给我们一个序列，需要我们将这个数进行从小到大排序。思路分析这种题目算是一个很经典的题目，这里介绍两种高效的排序方法。其思想都是利用递归进行实现的。快速排序法快速排序的思想就是我们先设定一个基准，然后将这个要排序...

C++

2021-11-08

0 594

NC139 题解 | #孩子们的游戏(圆圈中最后剩下的数)#

NC139 题解 | #孩子们的游戏(圆圈中最后剩下的数)# 题意分析给出一个0-n-1的数字排列，我们最开始从0开始(包括0）走m个数字，然后将这个数字删除，然后继续执行这项操作，直到最后只剩下一个数字，问这个数字是什么？这里要注意删除了的数字就没有了，不能重复计数。样例解释如下图思路...

C++

2021-11-07

0 414

NC138 题解 | #矩阵最长递增路径#

题意分析给出一个二维矩阵，矩阵的每个位置有一个数字，我们需要任意选择一个起点，然后从这个起点出发，每次只能走比当前数字更大的位置，问我们最多可以走多少步。每次走的位置只能是上下左右四个方向，同时不能越界。每个格子最多只能走一次。思路分析一个DFS的操作，我们发现，我们可以枚举某一个起点...

C++

2021-11-07

7 1425

NC137 题解 | #表达式求值#

题意分析给出一个合法的表达式，需要我们计算这个表达式的值。思路分析对于这种表达式的求值，我们在确实输入的序列是合法的情况下我们可以使用递归的方法进行求解。我们可以递归计算每个括号的值，然后我们将整个表达式切分成数值和运算符的形式，我们将我们得到的数值放到栈里面，然后将所有的符号都尽量转...

Python2

2021-11-05

0 604

NC136 题解 | #输出二叉树的右视图#

题意分析给出一个二叉树的前序遍历的序列和中序遍历的序列，我们需要找到这个二叉树的右视图结点的权值构成的数组。这里的右视图就是从右边向左边进行投影能看到的序列有哪些? 思路分析前置知识我们首先需要知道二叉树的先序遍历的序列和中序遍历的序列是什么？如下图我们把一棵树分为根结点，...

C++

2021-11-05

1 789

NC591 题解 | #牛牛的Fib序列#

NC591 题解 | #牛牛的Fib序列# 题意分析题目给出一个序列的前两项，需要我们计算这个序列的第n项的值，并且题目给出序列满足f[i]=f[i−1]+f[i+1]f[i]=f[i-1]+f[i+1]f[i]=f[i−1]+f[i+1] 思路分析首先，我们对上面的公式进行推导 f[i...

C++

2021-10-12

0 520

NC565 题解 | #分石子#

NC565 题解 | #分石子# 题意分析给出n堆石头以及每堆石头的数量，然后我们可以将任意堆石头数量大于1的分为两堆，问最后分为m堆中，分得的所有堆里面的最小值最大是多少？思路分析对于这种最小值最大，最大值最小等的问题，一半都是采用的是二分的方法进行处理。我们先判断怎样二分具有单调性...

Go

2021-10-12

0 855