changed.

题解

/ 注册

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

题解 | #一样的水#

题意整理：题目给出一个数组以及一组查询，每个查询的值表示需要让数组中至少存在个大小相等的值，而答案所求的就是对于每个查询，仅对数组元素进行加1操作，需要几次操作能够满足要求。在满足最小操作次数的前提下，需要使得该相等的值最小方法一：暴力核心思想：容易想到的一种思路就是：首先对数组排序，然后对...

2021-09-21

0 450

题解 | #最大四边形面积#

题意整理：在题目给出的数组中，选择四个数，将其组成一个四边形，求解数组中的数能够组成的四边形中的最大面积。四边形的不稳定结果，其面积可以变化，所以需要分析四条边能够组成的最大面积首先明确，当存在一条边的长度大于等于其他三条边的长度之和时，这四条边无法组成四边形，面积为0.再则，可以得出一个结论，当...

2021-09-20

0 716

题解 | #数组求和统计#

题意整理：整理题意既：给出两个大小为n的数组a, b，统计有多少数对(l, r)满足且a数组的[l,r]区间和等于b数组的的和方法一：暴力枚举核心思想：可以对a进行二重枚举，既枚举l和r，然后计算对应值是否满足条件。第二维的枚举使用变量sum统计前面的数的和，使得对单个区间计算的复杂度为1 ...

2021-09-20

0 467

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

题意整理：既对一颗以根节点给出的树进行中序遍历。二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历树，而在访问左子树及右子树的时候按照同样的方式遍历，遇到空节点返回，直到遍历完整棵树。方法一：递归实现核心思想：按照中序遍历的意义，很容易想出递归实现，既创建递归函数dfs(root...

2021-09-19

0 535

题解 | #二分查找-I#

题意整理：题意已经非常明显，既书写一个对不存在重复元素的排序数组的二分查找二分查找既利用数组排序特性的一种高效查找算法，一次可以去除一半的待查找元素，所以时间复杂度为方法一：书写简单二分核心思想：采用双指针的方法，左指针开始时指向数组头部，右指针开始时指向数组尾部，每次都对两指针中间值与目标...

2021-09-19

0 528

题解 | #最小生成树#

题意整理：去除题目背景后,实际上就是需要对一个给定边权的图,求其最小生成树.最小生成树:在一个具有N个顶点的带权连通图G中，如果存在某个子图G'，其包含了图G中的所有顶点和一部分边，且不形成回路，并且子图G'的各边权值之和最小，则称G'为图G的最小生成树。注意到最小生成树并不唯一最小生成树有两种常...

2021-09-19

0 585

题解 | #单源最短路#

题意整理：题目以边的形式给出一个有向图，要求找到图中指定两个点（1，n）中的最短路径为了便于后续操作，我们先将给出的边权数组转化为点对之间的距离，对于没有边链接的距离为INT_MAX，对于重边取得较小值。方法一：DFS（超时）核心思想：首先，我们需要从起点1开始，往能够前往的点进行搜索。此处...

2021-08-13

1 498

题解 | #单调栈#

题意整理：本题题意很明显。给定一个数组，需要找到数组中每个元素左边和右边的第一个比元素小的数字。方法一：暴力核心思想：根据题意，对每一个元素，都各自往左以及往右遍历数组，直到到达数组边界或者找到第一个比元素小的数字即可。核心代码： class Solution { public: ...

2021-08-13

0 636

题解 | #01背包#

题意整理： 0-1背包是极其经典的动态规划问题。理清题意，题目通过数组给出个背包，每个背包为二元数对，求解对给定体积，在选择若干个物品，满足时能够得到的最大重量。方法一：动态规划核心思想：可以发现，对一个物体，我们可以选择将它装入背包，以及不选择，这就将问题划分成了更小的子问题，可以...

2021-07-27

0 627

题解 | #不相邻最大子序列和#

题意整理：本题实际上的要求就是从数组中选择一些数，要求这些数字不相邻，求能够得到的最大子序列和。对于一个数字，如果它相邻的数字被选取，那么我们不能选取这个数字；如果它相邻的数字没有被选取，那么我们可以考虑选取或者不选取这个数字。注意到一个问题，对于连续的三个数 ,在这三个数中，我们最少会选择一个数...

2021-07-26

0 764