Peterliang

分类

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

/ 注册

全部文章（共171篇）

NC571 题解 | #寻找牛妹#

题意分析给出一个以1为根的树，然后是m个询问，对于每个询问，需要我们计算从结点1到这个被询问的结点的最大的花费是多少？（题目中说的是至少要带多少金币才可以保证任何情况下都可以找到牛妹，所以应该是一个最大的花费。）思路分析首先，我们观察题目，我们发现这个题目是一个多组询问，所以应该是需要先...

牛客题霸

2021-09-10

0 605

NC567 题解 | #异次元空间#

题意分析给我们一个数组，这个数组的每个数都有一个每天都会进行一个增长，假如增长了x天，那么x天后的值为。但是这个数会对一个进行取模运算。同时，我们可以决定在什么时候让这个数字停止增长和继续增长。问至少要多少天可以使得这个数组里面的数字至少有个数字都为。思路分析首先，我们根据题目的意思进行...

牛客题霸

2021-09-10

0 789

NC569 题解 | #分组#

题意分析给你一个长度为n的序列，需要我们将这个序列分为连续的k部分，要求分的所有的情况里面，对于每个部分的数字的和，要求所有的部分数字的和的最小的最大化。样例解释有3种分法[1],[2,1,5]，数字和分别为1，8，最小值为1[1,2][1,5]，数字和分别为3，6，最小值为3[1,2,1],...

牛客题霸

2021-09-08

1 747

NC566 题解 | #连续段的中数#

题意分析给我们一个序列，要我们找出一个长度大于等于k的序列，然后这个序列里面的中数要尽可能大。“中数”的定义就是这个序列里面大于等于这个数字的个数要大于等于这个序列的长度的一半。所以在保证这个序列是升序排列的情况下，下图所示的就是中数。思路分析解法一暴力枚举+优先队列维护这个思路...

牛客题霸

2021-08-18

0 725

NC43 题解 | #没有重复项数字的所有排列#

题意分析给你一个序列，需要先将这个序列的相同的元素去掉，也就是先去重。然后按照原来的序列进行一个全排列，需要对每个排列进行字典序排列。前置知识我们按照顺序来。首先，你需要知道怎么去重，在C++里面，对数组的去重两种方法，一种是自己实现，先对整个数组进行排序，然后两两相邻的进行比较。一旦...

牛客题霸

2021-08-16

0 812

NC39 题解 | #N皇后问题#

题意分析经典模板题，n皇后问题。给你一张nxn的棋盘。需要往这个棋盘里面放一些棋子。然后需要保证这n个棋子之间不同同行同列和同正反斜线。也就是下图中在同一条线上面的不能同时放置棋子。思路分析好了，我们现在知道题目意思了，我们可以来说说怎么解这题。首先，我们需要知道如何判断两个位...

牛客题霸

2021-08-13

0 725

NC35 题解 | #最小编辑代价#

题目大意给你两个字符串，需要你通过执行三种操作，将一个字符串修改为另一个字符串。但是你执行这三种操作都是有代价的。三种操作分别对应三种代价。你需要使用最少的代价将这个字符串修改为另一个字符串。思路分析首先，这个题目是比较难的，我来大致介绍一下我的思路和想法。对于这个问题，最开始我想的是利...

牛客题霸

2021-08-13

0 1058

NC36 题解 | #在两个长度相等的排序数组中找到上中位数#

题意分析给你两个数组。数组都是按照从小到达进行排序的两个数组的大小相等需要我们求出两个数组的上中位数上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数同时时间复杂度为O(logn)，空间复杂度为O(1) 思路分析其实稍微了解过排序...

牛客题霸

2021-08-12

0 1006

NC30 题解 | #数组中未出现的最小正整数#

题意分析首先，这个题目的题目描述有点问题。而且测试数据估计比较水。希望可以加强一下。其实，我们来说一下这个题目的大意。就是给你一个数组，需要你快速找出这个数组里面没有出现过的最小的正整数。怎么快速呢？就是要做到O(n),然后呢？就是，空间复杂度要控制在O(1). 思路分析解法一哈希这...

牛客题霸

2021-08-12

0 821

NC29 题解 | #二维数组中的查找#

题意分析给你一个二维数组，这个二维数组从左到右是递增的，从上到下也是递增的。要我们判断某一个整数是否在这个数组里面。思路分析解法一暴力解法二维数组，判断是否存在某一个数字，似乎很好理解。最直接的方法就是直接暴力循环所有的位置，直接判断是否存在，这样的话最好的时间复杂度为O(1),最坏...

牛客题霸

2021-08-11

0 571