retyrn

分类

题解(3)

/ 注册

全部文章（共206篇）

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

知识点回溯思路每个数字只能选一次，要获取全部的方案，可以采用回溯的方法。从左到右选择是否把当前元素加入路径，当到达末尾或者累积总和大于等于要求时停止。当总和等于要求值时加入答案。由于我们优先选取当前元素的路径，所以得到字典序递增的答案。AC code(C++) class Solution { pu...

2023-07-28

0 240

题解 | #牛群喂食# 回溯

知识点回溯思路获取所有的方法，可以使用回溯的方法。首先先把备选的数字进行从小排序，之后讨论每个位置选几个的方法来进行递归，直到到达备选数组的末尾或者总和大于要求时递归终止。当满足总和正好等于要求时加入答案数组。由于我们是一个一个加入路径，而且回溯的备选数组是从小到大的，因此我们获得的路径是符合字典序...

2023-07-28

0 259

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

知识点回溯思路范围很小，所以可以用回溯来做。因为是要求逆序，所以从大的数开始往小的数搜。为了省事用了prev_permutation函数AC code (C++) #include <algorithm> class Solution { public: /** * 代...

2023-07-28

1 221

题解 | #牛棚分组# 回溯

知识点回溯思路数据范围很小，可以考虑回溯的方法。从1开始向n搜索，直到待选个数为0或者已经超出范围时停止，同时维护路径，如果满足条件则将当前路径加入答案中。因为要求字典序，所以我们优先选择保留当前数字的路径。AC code（C++） class Solution { public: /** ...

2023-07-28

0 320

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

知识点flood fill思路我们考虑什么B字符不能转化为A；我们从边缘的B的位置开始flood fill 访问到的位置说明不是被A包围的B则不能变为A，我们将剩余的B都转化为A即可。时间复杂度每个点最多访问一次，时间复杂度为AC code（C++） class Solution { public:...

2023-07-27

0 254

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

知识点哈希表思路遍历整个数组，用哈希表维护每次可能成为众数的数是谁，如果出现了更好的位置更新。时间复杂度为AC Code（C++） #include <unordered_map> class Solution { public: /** * 代码中的类名、方法名、参数...

2023-07-27

0 263

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

知识点哈希表最大公因数gcd思路我们如果按照一般的直线方程y=kx+b的形式会产生k和b是浮点数的情况，这样会产生精度问题。我们换这样一个思路，遍历整个数组，枚举一个点作为直线的起点；现在已经选定好一个点做起点后，我们再遍历整个数组（这次取起点以外的n-1个点），分别计算他们之间的横纵坐标的差值...

2023-07-27

0 302

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

知识点区间合并思路由于原序列已经有序且无重叠，我们只需要找到和新加入的序列有重叠部分的区间后把他们合并即可，没有重叠的部分直接加入答案。遍历一遍数组，时间复杂度为AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经...

2023-07-27

0 255

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

知识点区间合并贪心思路经典区间合并问题，按照左端点排序，相等的话按照右端点排序。维护当前加入段的左右端点，只有下一段的左端点在当前段的右端点右边，不能并入同一段，把当前段加入后，重置加入的段。剩下的情况都是可以加入的。时间复杂度主要瓶颈在排序上，AC code（C++） #include <...

2023-07-27

0 240

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

知识点DFS 回溯知识点经典八皇后问题，从上到下一行一行填入，枚举填在哪一列，同时开三个布尔数组分别代表某列、某对角线、某副对角线是否被使用。回溯后记得恢复现场。时间复杂度为AC code (C++) class Solution { public: /** * 代码中的类名、方...

2023-07-26

0 259