retyrn

分类

题解(3)

/ 注册

全部文章（共206篇）

题解 | #牛群的编码II# 模拟大整数减法

知识点模拟大整数减法思路大整数减法板子题，我们可以从后往前模拟减法的“相减借位”的过程，时间复杂度为题面说除了0以外无前导零，结果测试点还有前导零的情况。AC Code（C++） #include <algorithm> class Solution { public: /...

2023-08-16

0 364

题解 | #牛的回文编号III# 位运算双指针

知识点位运算双指针思路我们维护一对反向双指针，每次左指针右移、右指针左移，如果出现不相等则不为回文串，反之则为回文串。AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 ...

2023-08-16

0 342

题解 | #找到满足条件的牛群组合# 双指针

知识点双指针思路首先排序，枚举第一个元素，用双指针来得到第二个和第三个元素。实现上如果当前元素和上一个元素相等的话可以跳过，因为当前的所有情况已经在上一个元素处枚举过了。时间复杂度 AC Code（c++） #include <vector> class Solution { publi...

2023-08-15

0 336

题解 | #牛群买卖计划II# 状态机DP

知识点状态机DP思路定义 f[i][j][st] 前i天完成j笔交易，手上股票持有状态为st 的价值最大值。状态转移可以分为当前股票保持或者卖出两种状态，就可以进行转移。答案为前n天手上持有状态为0的最大值。时间复杂度AC Code（C++） class Solution { public: ...

2023-08-15

0 404

题解 | #牛群买卖计划# 状态机DP

知识点状态机DP思路定义 f[i][j][st] 前i天完成j笔交易，手上股票持有状态为st 的价值最大值。状态转移可以分为当前股票保持或者卖出两种状态，就可以进行转移。答案为前n天手上持有状态为0的最大值。时间复杂度AC Code（C++） class Solution { public: ...

2023-08-15

0 324

题解 | #牛群买卖计划III# 贪心

知识点贪心思路由于可以在某一天卖出之前的所有牛，为了利益最大化，我们需要在价格最高的那天卖出之前的购入的所有牛，在价格次之的一天卖出之前的所有牛（排除之前已经卖出的）……因此我们可以对价格从高到低排序，每次从卖出日向前枚举找到没有卖出的一段卖出，累计答案。时间复杂度 AC Code (C++) #i...

2023-08-15

0 281

题解 | #寻找牛群中的最高牛# 遍历

知识点遍历数组思路求单峰的最大值的话，我们可以用二分解决，但是多峰的话二分无法解决。hack数据：[1,2,4,2,3,11][1,2,4,3,2,11]峰值中最高的牛，其实也就是最高的牛。遍历数据即可。时间复杂度AC Code（C++） class Solution { public: /...

2023-08-15

0 356

题解 | #最大养牛利润# 贪心

知识点贪心堆思路我们按照cost的大小进行排序，每一次饲养可以选取当前cost允许养的利润最大的牛。实现上我们用一个指针来维护一下加入的位置，用一个堆来选每次最大利润的牛。一共进行k轮，k不大于n。时间复杂度为AC Code（C++） #include <numeric> #inclu...

2023-08-15

0 337

题解 | #最高售价的两只牛# 堆 + 多路归并

知识点堆多路归并思路如果直接维护一个堆来维护最大的k组数对，遍历每一对数，时间复杂度是，显然超时，不做讨论。我们考虑把每个priceA的位置当做一个组，然后每个组的起点位于priceB的末尾，建立一个堆选出那个组是最大的。首先我们把每个priceA的位置和priceB的末尾元素组成的组入堆。之后...

2023-08-15

1 242

题解 | #牛群放牧顺序# bfs 求最长上升路径

知识点bfs思路每个点的应该放牧的值实际上是左右两侧最长上升路径的节点个数。可以找出最低的点，做多源bfs从而找到每个点的最长上升路径，这一步可以用bfs或者dijkstra算法。因为每个点在左右两侧的大小关系是固定的，每个点最多入堆常数次，时间复杂度为。AC Code (C++) #include...

2023-08-15

0 274