retyrn - 个人主页动态 - 牛客网

发布(207) 评论刷题收藏

2023-07-29 11:23

浙江大学 C++

题解 | #贪吃牛# 线性DP

知识点动态规划思路典型的动态规划问题，可以按照当前吃一块还是两块草料进行划分状态转移方程为可以看出其实是斐波那契数列，时间复杂度为AC code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ int eatGrass(int n) { int f[30]; f[1] = 1; f[2] = 2; for (int i = 3; i <= n; i ++) { f[i] = f[i - 1] + f[i - 2...

0 点赞评论收藏

分享

2023-07-29 11:17

浙江大学 C++

题解 | #基因变异最小次数# BFS最短路

知识点BFS 最短路思路每一步的代价为1，可以用BFS求最短路。每次搜索尝试把每个字母换成“ACGT”中的一个，如果在备选中则可以加入队列。具体细节和上一题完全一致。AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param start string字符串 * @param end string字符串 * @param bank string字符串vector * @return int整型 */ using psi = pair<string, int>...

0 点赞评论收藏

分享

2023-07-29 10:31

浙江大学 C++

题解 | #牛群最短移动序列# BFS求最短路

知识点哈希表 BFS思路这是一个从beginWord到endWord的最短路问题，由于每次权重为1，所以可以用bfs解决。bfs很容易搜索空间爆炸，但是本题要求搜索的每个节点必须出现过，所以状态数最多有2000个。所以我们可以用哈希表存储所有的允许的字符串，每次用O(1)的时间得到是否存在该元素（实际上如果key是string的话会和字符串长度正比）每次转移我们枚举把某个字母转换成哪一个小写字母即可，每次最多考虑16*26次时间复杂度为 n是合法字符串的数目，m是字符串的长度，由于哈希表判断，实际的时间复杂度是AC Code (C++) class Solution { public: /**...

0 点赞评论收藏

分享

2023-07-29 10:13

浙江大学 C++

题解 | #连续的牛群标签序列# 哈希表

知识点哈希表思路原数组中存在的数放到数轴上的话，其实是一段一段的。我们要求的是最长段的长度。我们可以把原数组放到哈希表中，逐个枚举每一段的开头元素，然后向后延伸，找到每一段的长度后更新答案。由于原数组是一段一段的，所以我们最后的遍历次数其实是的，整体时间复杂度为AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param tag int整型vector * @return int整型 */ int longestConsecutive(vector<int>...

0 点赞评论收藏

分享

2023-07-28 22:00

浙江大学 C++

题解 | #牛群定位系统# DFS

知识点DFS思路这样例都有错误，无语==，说是按照出现的顺序排列，结果样例2根本不是用一个最暴力的办法，把所有的字符串存在哈希表里面，把每一个位置作为第一个出现的字符开始暴力搜索可以出现的所有字符串，由于最长字符串限制在12，所以当长度达到12的时候停止搜索。我们考虑一下时间复杂度：除了第一个字符以外，后面还要搜索最多11个字符，由于搜索不能回头，每一步最多三个方向，计算次数为次枚举起始点，一共144个位置，因此总体计算次数小于考虑每个字符串哈希所有的时间为因此计算度少于时间限制为5秒 可以跑完AC Code (C++) #include <functional> class So...

0 点赞评论收藏

分享

2023-07-28 20:37

浙江大学 C++

题解 | #牛群分组II# 回溯

知识点回溯思路每个数字只能选一次，要获取全部的方案，可以采用回溯的方法。从左到右选择是否把当前元素加入路径，当到达末尾或者累积总和大于等于要求时停止。当总和等于要求值时加入答案。由于我们优先选取当前元素的路径，所以得到字典序递增的答案。AC code(C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param candidates int整型vector * @param target int整型 * @return int整型vector<vector<>>...

0 点赞评论收藏

分享

2023-07-28 20:11

浙江大学 C++

题解 | #牛群喂食# 回溯

知识点回溯思路获取所有的方法，可以使用回溯的方法。首先先把备选的数字进行从小排序，之后讨论每个位置选几个的方法来进行递归，直到到达备选数组的末尾或者总和大于要求时递归终止。当满足总和正好等于要求时加入答案数组。由于我们是一个一个加入路径，而且回溯的备选数组是从小到大的，因此我们获得的路径是符合字典序的；要求字典序降序，所以我们把答案反转即可。AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param candidates int整型vector * @param ta...

0 点赞评论收藏

分享

2023-07-28 19:18

浙江大学 C++

题解 | #牛群排队# 全排列

知识点回溯思路范围很小，所以可以用回溯来做。因为是要求逆序，所以从大的数开始往小的数搜。为了省事用了prev_permutation函数AC code (C++) #include <algorithm> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector<vector<>> */ vector<vector<int> > cow_permute(v...

0 点赞评论收藏

分享

2023-07-28 12:36

浙江大学 C++

题解 | #牛棚分组# 回溯

知识点回溯思路数据范围很小，可以考虑回溯的方法。从1开始向n搜索，直到待选个数为0或者已经超出范围时停止，同时维护路径，如果满足条件则将当前路径加入答案中。因为要求字典序，所以我们优先选择保留当前数字的路径。AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param k int整型 * @return int整型vector<vector<>> */ vector<vector<int> &g...

0 点赞评论收藏

分享

2023-07-27 21:09

浙江大学 C++

题解 | #牛群的活动区域# flood fill

知识点flood fill思路我们考虑什么B字符不能转化为A；我们从边缘的B的位置开始flood fill 访问到的位置说明不是被A包围的B则不能变为A，我们将剩余的B都转化为A即可。时间复杂度每个点最多访问一次，时间复杂度为AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param board char字符型vector<vector<>> * @return char字符型vector<vector<>> */ in...

0 点赞评论收藏

分享

2023-07-27 14:48

浙江大学 C++

题解 | #农场牛群众数# 哈希表

知识点哈希表思路遍历整个数组，用哈希表维护每次可能成为众数的数是谁，如果出现了更好的位置更新。时间复杂度为AC Code（C++） #include <unordered_map> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector */ vector<int> findMode(vector<int>& nums) { vector<int> cnt(...

0 点赞评论收藏

分享

2023-07-27 14:30

浙江大学 C++

题解 | #直线上的牛# 哈希表 gcd

知识点哈希表 最大公因数gcd思路我们如果按照一般的直线方程y=kx+b的形式会产生k和b是浮点数的情况，这样会产生精度问题。我们换这样一个思路，遍历整个数组，枚举一个点作为直线的起点；现在已经选定好一个点做起点后，我们再遍历整个数组（这次取起点以外的n-1个点），分别计算他们之间的横纵坐标的差值对，用哈希表统计差值对，一样的差值对说明在一条直线上。哈希表中的最大值则是选定当前起点的最大值。统计差值对，如果两个数都是正数，那么可以除以gcd让他们互质得到最简形式，如果存在一个是0，那么让另外一个是1即可，因为不存在相同的两个点，我们不会有差值都是0的情况。哈希表的话，由于cpp语言特性上没有支...

0 点赞评论收藏

分享

2023-07-27 12:02

浙江大学 C++

题解 | #牛舍扩建# 区间合并

知识点区间合并思路由于原序列已经有序且无重叠，我们只需要找到和新加入的序列有重叠部分的区间后把他们合并即可，没有重叠的部分直接加入答案。遍历一遍数组，时间复杂度为AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param intervals int整型vector<vector<>> * @param new_interval int整型vector * @return int整型vector<vector<>> */ ...

0 点赞评论收藏

分享

2023-07-27 10:55

浙江大学 C++

题解 | #奶牛喂养时间# 贪心

知识点区间合并 贪心思路经典区间合并问题，按照左端点排序，相等的话按照右端点排序。维护当前加入段的左右端点，只有下一段的左端点在当前段的右端点右边，不能并入同一段，把当前段加入后，重置加入的段。剩下的情况都是可以加入的。时间复杂度主要瓶颈在排序上，AC code（C++） #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param intervals int整型vector<vector<>> * @return int整...

0 点赞评论收藏

分享

2023-07-26 21:36

浙江大学 C++

题解 | #牛吃草问题# 八皇后问题 DFS

知识点DFS 回溯知识点经典八皇后问题，从上到下一行一行填入，枚举填在哪一列，同时开三个布尔数组分别代表某列、某对角线、某副对角线是否被使用。回溯后记得恢复现场。时间复杂度为AC code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ int totalNCow(int n) { vector<bool> cols(10), d1(20), d2(20); int res = 0; function&l...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务