retyrn

分类

题解(3)

/ 注册

全部文章（共206篇）

题解 | #旋转位置的特定牛# 两次二分

知识点二分思路首先和 NB79 旋转排列之找出最矮的牛这道题一样找到分界点，分界点两边都是有序的，可以直接二分查找是否存在对应的值。即两次二分，时间复杂度AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请...

2023-08-08

0 238

题解 | #旋转排列之找出最矮的牛# 二分

知识点二分思路首先特判首位两个元素的大小来排除没有移动的情况。在移动后，数组变成了两段递减的拼接，我们需要找到第一段的末尾，可以使用二分，如果当前的mid元素比首元素要大，那么在mid右端的部分将舍弃。每次会减少一半的范围。所以时间复杂度为AC Code（C++） class Solution { ...

2023-08-08

0 243

题解 | #分品种# 贪心

知识点贪心思路由于需要分割出更多的组，我们先预处理出每个字母出现的最后一个位置。之后我们指定一个开头，遍历从开头到当前字母的最后的位置（必须包含的位置），随着我们向后遍历会逐渐遇到新的字母，会把至少应该包含的末尾向后移动，直到我们遍历到末尾之后，就可以形成一个分割。之后加入答案即可。时间复杂度 AC...

2023-08-08

0 246

题解 | #寻找完成任务所需最短时间# 双指针

知识点双指针计数思路同向双指针，并维护两段指针之间的字母的计数，双指针每次右指针移动一次，左指针不断试探下一个位置是否可以，每次找到满足条件的最近的左指针。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、...

2023-08-08

0 346

题解 | #奶牛的活动面积# DP

知识点动态规划思路维护每个点的上边的连续的C的个数, 左边的连续的C的个数, 以及以该点为右下角的由C组成的正方形的长度; 上边和左边是很好维护的, 我们考虑如果当前点不是左上两条边的点的话, 那么如果满足当前点上面连续的C的个数和左边的连续的C的个数均大于f[i-1][j-1], 那么f[i][j...

2023-08-07

0 254

题解 | #最小三角路径和# DP

知识点动态规划思路定义 f[i][j] 为从起点到 (i, j)的最小的路径和每次转移可以从f[i-1][j-1] f[i-1][j]进行转移答案是最后一行的最小值时间复杂度 AC Code (C++) class Solution { public: /** * 代码中的类名、方...

2023-08-07

0 222

题解 | #训练聪明的牛II# DP

知识点动态规划思路状态表示: 定义 f[i] 为总和为i的最小个数，状态转移: 每一次转移是选定当前选哪一个数字，即时间复杂度为 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规...

2023-08-07

0 301

题解 | #挤奶路径2# 乘法原理 + DP

知识点乘法原理动态规划思路下面我们讨论DP解法。首先由于只能向右或者向下移动，那么说明任意值为2的点的横纵坐标大小关系必须是一致的，也就是对于点（x1，y1）和（x2，y2）而言，如果存在（x1 < x2）且 (y1 > y2)的情况一定是无解的排除掉这一点后，我们发现假如存在m个有牛...

2023-08-04

0 301

题解 | #训练聪明的牛# 反向构造哈希表 + 动态规划

知识点哈希表动态规划思路定义状态表示f[i] 表示前i个字母能否被合法分割; 那么只需要枚举当前字母所在的子串, 查询是否在wordList即可进行转移。使用哈希表将所有的word存起来可以做到O(len)的时间内查询是否存在；在枚举子串的时候倒着枚举可以减少复制字符串的时间消耗.时间复杂度 ...

2023-08-04

0 270

题解 | #牛群编号变更# 最长公共子序列 LCS

知识点最长公共子序列 LCSDP思路两个序列的公共子序列部分是不需要更改的，剩下的则需要增加或者减少，所以只需要求出最长公共子序列，每个序列除去最长公共子序列的部分就是需要更改的部分。定义 f[i][j]表示word1前i个字母和word2的前j个字母的最长公共子序列。时间复杂度 AC Code (...

2023-08-04

0 321