retyrn

分类

题解(3)

/ 注册

全部文章（共206篇）

题解 | #交错编号# 动态规划

知识点动态规划思路因为要求刚好匹配所以不满足则不可以, 所以定义f[i][j] 表示t的前i个字符是否满足能 s前i个字符和x的前i-j个字符匹配由于所以状态数最多20000个每次状态转移, 讨论当前t中的字符和哪一个字符串的字符相匹配, 单次转移的时间复杂度为总的时间复杂度 AC Co...

2023-08-04

0 293

题解 | #牛群的编码# 模拟加法

知识点模拟思路模拟加法的进位过程，翻转两个字符串，从前往后进行加法，同时维护一个进位carry。每一次把当前位记录到结果字符串中。最后反转结果字符串即可。时间复杂度 AC Code (c++) class Solution { public: /** * 代码中的类名、方法名、参数...

2023-08-03

0 236

题解 | #交织子序列# DP

知识点动态规划思路因为要求刚好匹配所以不满足则不可以, 所以定义f[i][j] 表示t的前i个字符是否满足能 s前i个字符和x的前i-j个字符匹配由于所以状态数最多20000个每次状态转移, 讨论当前t中的字符和哪一个字符串的字符相匹配, 单次转移的时间复杂度为总的时间复杂度 AC Co...

2023-08-03

0 307

题解 | #农场的奶牛分组# 01背包

知识点背包问题 DP思路首先先对所有的数求和，如果是奇数则不可拆分。之后需要凑出sum/2的总和，问题转化成有n个数可以选一次或者不选，求出是否能凑出sum/2，则可以用01背包解决。实现上可以一维空间优化。时间复杂度 AC Code（C++） #include <numeric> ...

2023-08-03

0 295

题解 | #牛牛的跳跃挑战# 线性DP

知识点动态规划思路定义f[i]为到达下标为i位置所需要的最小的代价, 答案为f[n]每一次可以从前面3个位置进行转移时间复杂度 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定...

2023-08-03

0 329

题解 | #找出特定体重的牛群# 二分

知识点二分思路两次二分分别找到比所求段小的第一个位置和当前数字的第一个位置即可。重要的在于二分边界条件的书写。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可...

2023-08-03

0 283

题解 | #乳牛各类产奶统计# 前后缀分解

知识点前后缀分解前缀和思路不能使用除法，我们可以预处理每个位置的前后缀的乘积，然后遍历每个位置用前后缀的乘积来计算得到答案。时间复杂度预处理前后缀和遍历整个数组整体时间复杂度为AC Code（C++） class Solution { public: /** * 代码中的类...

2023-08-03

0 299

题解 | #牛群的位置排序# 二分

知识点二分思路在一个有序序列中寻找第一个大于等于x的值，可以使用二分法进行，实现上可以直接调用lower_bound函数时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规...

2023-08-03

0 277

题解 | #完全平方数的草料# 记忆化搜索

知识点记忆化搜索思路定义状态 f[i]为总和为i的最优分解, 由于可以全分解为1, 所以任何数都是存在合法分解的我们可以根据当前选取什么数t , 将该问题转化为一个子问题递归终点为x为0时返回空数组状态数为n, 每一次转移需要枚举次, 总的时间复杂度为 AC Code (C++) class S...

2023-08-02

0 376

题解 | #牛奶工厂# 归并

知识点模拟归并思路从后往前，归并两个数组，如果一个数组全用完了，就把剩下的接在后面就好了。时间复杂度为AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * ...

2023-08-02

0 345