retyrn

分类

题解(3)

/ 注册

全部文章（共206篇）

题解 | #相等的草堆# 前缀和

知识点前缀和思路从左到右遍历，找到第一个左右两边的质量相等的位置，计算左右两边的质量可以计算前缀和优化每次计算到时间复杂度为AC code （C++） #include <numeric> class Solution { public: /** * 代码中的类名、方法...

2023-07-25

0 287

题解 | #最大放牛数# 贪心

知识点贪心思路贪心，从左到右优先填入可以填入1的位置，如果可以填完则可以不引发争斗，反之会引发争斗。AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * ...

2023-07-25

0 341

题解 | #牛群重量积# 前缀和

知识点前缀和思路不让用出发，那就预处理左边和右边的前缀和，找到每个位置对应的左右的长度之后乘一起得到答案。时间复杂度预处理的时间复杂度为总体的时间复杂度为AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请...

2023-07-25

0 347

题解 | #牛群的喂养顺序II# 拓扑排序

知识点拓扑排序思路和上一道题完全一样，只需要在bfs出队的时候记录下顺序即可。如果结果数组记录已达的点的个数等于全部个数，证明全部点可达；否则返回空数组。时间复杂度点数为n 边数为m时间复杂度为AC code（C++） class Solution { public: /** * ...

2023-07-25

0 301

题解 | #向左移动牛群II# 模拟

知识点模拟思路k先对n取模，因为比n大会循环回来没有意义；之后模拟填入数字即可。时间复杂度为。AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * *...

2023-07-25

1 269

题解 | #没有出现的编号# 哈希表

知识点哈希表思路遍历整个数组可以求出最大的负数建立哈希表，然后从1开始查看是否存在该正数，因为最多n个数，所以尝试最多n次时间复杂度为AC code （C++） #include <unordered_set> class Solution { public: /** ...

2023-07-25

0 288

题解 | #牛群的喂养顺序# 拓扑排序

知识点拓扑排序思路题目给定一些喂养关系，我们可以抽象为假设喂养a之前需要喂养b，我们建立一条从b到a的有向边，因此对整个图跑拓扑排序，如果所有点都可达，就说明能喂养完全。如果有一些点不能喂养（存在环），就不能喂养完全。时间复杂度假设点数为n，边数为m；建图和统计入度时间复杂度为跑拓扑排序（BFS）每...

2023-07-24

0 345

题解 | #售价的中位数# 对顶堆

知识点对顶堆思路动态维护中位数。可以搞两个堆，一个是较小的一半数（大顶堆），一个是较大的一半数（小顶堆），较小元素的堆至多比较大元素的堆多一个元素。这样每次求中位数，要么是小数堆的堆顶，要么是小数堆和大数堆的堆顶的平均数，单次时间复杂度为。然后考虑如何维护这两个堆。每次我们加入一个新的元素，先加入大...

2023-07-24

0 309

题解 | #牛的生长情况# 单调栈

知识点单调栈思路题意是寻找右边第一个比当前值大的数，这可以用单调栈维护，时间复杂度为AC code （C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * ...

2023-07-24

0 293

题解 | #牛舍的占地面积# 单调栈解法

知识点单调栈题意和思路这题题面太抽象了，不能加个图吗？？样例一是这样的：蓝色是这几个牛棚，橙色是那个盖布。因为盖布的长度和最短的牛棚一致，我们考虑每个位置作为“最小”时对答案的贡献，然后我们可以发现，当某个位置作为最小值是，盖布的另一条边的长度等于左右两侧第一个比当前长度短的距离。求左右两侧第一个比...

2023-07-24

5 384