知识点拓扑排序思路题目给定一些喂养关系，我们可以抽象为假设喂养a之前需要喂养b，我们建立一条从b到a的有向边，因此对整个图跑拓扑排序，如果所有点都可达，就说明能喂养完全。如果有一些点不能喂养（存在环），就不能喂养完全。时间复杂度假设点数为n，边数为m；建图和统计入度时间复杂度为跑拓扑排序（BFS）每个点只入队一次，时间复杂度为总体时间复杂度为AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param numCows int整型 * @param feedOrders ...

知识点对顶堆思路动态维护中位数。可以搞两个堆，一个是较小的一半数（大顶堆），一个是较大的一半数（小顶堆），较小元素的堆至多比较大元素的堆多一个元素。这样每次求中位数，要么是小数堆的堆顶，要么是小数堆和大数堆的堆顶的平均数，单次时间复杂度为。然后考虑如何维护这两个堆。每次我们加入一个新的元素，先加入大顶堆，然后假如大顶堆的堆顶大于小顶堆的堆顶元素（就是刚才加入那个数比较大），调换两个堆的堆顶。之后假如小数的堆个数比大数的堆多两个元素以上了，需要调一个元素过去。单次维护的时间复杂度是。一共进行n次，总的时间复杂度为。AC code（C++） #include <queue> class...

知识点单调栈思路题意是寻找右边第一个比当前值大的数，这可以用单调栈维护，时间复杂度为AC code （C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param weights int整型vector * @return int整型vector */ vector<int> weightGrowth(vector<int>& weights) { // 单调栈 int n = weights.size(); vector<int> r(n,...

知识点单调栈题意和思路这题题面太抽象了，不能加个图吗？？样例一是这样的：蓝色是这几个牛棚，橙色是那个盖布。因为盖布的长度和最短的牛棚一致，我们考虑每个位置作为“最小”时对答案的贡献，然后我们可以发现，当某个位置作为最小值是，盖布的另一条边的长度等于左右两侧第一个比当前长度短的距离。求左右两侧第一个比当前值小的位置，是单调栈的基本用法。之后遍历每个位置，计算它作为最短的边的贡献来统计答案即可。时间复杂度求左右最近的比当前小的位置的时间复杂度为总体时间复杂度为AC code（c++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接...

知识点利用翻转O(1)解决循环数组位移思路首先k对n取模，因为大于n的时候会循环回来，是没有意义的。假如要把前k个数循环移动，我们可以先翻转前n-k个数，再翻转后k个数。最后整个数组翻转即可实现。时空复杂度时间复杂度为AC Code （C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param k int整型 * @return int整型vector */ vector<int> rotateCows(vector&l...

知识点prev_permutation()函数思路prev_permutation()函数返回字典序上一个的排列AC code (C++) #include <algorithm> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cows int整型vector * @return int整型vector */ vector<int> nextPermutation(vector<int>& cows) { auto t = prev_p...

知识点计数思路对k个数字计数，然后一次对原数组赋值。时间复杂度为AC code （C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cows int整型vector * @param k int整型 * @return int整型vector */ vector<int> sortCowsIII(vector<int>& cows, int k) { vector<int> cnt(k); for (auto x : cows) ...

知识点计数 模拟思路遍历数组，对三种牛计数。然后依照计数个数对结果数组赋值。时间复杂度AC code （c++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cows int整型vector * @return int整型vector */ vector<int> sortCows(vector<int>& cows) { int n = cows.size(); vector<int> cnt(3); for (auto x : c...

知识点双指针思路双指针，一个指针指向合法子字符串的开头，一个指向末尾，末尾不断向后移动，开头指向合法的最靠后的位置，如果符合要求则更新答案。由于每个点只遍历一次，时间复杂度是线性的。时间复杂度AC code （C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param t string字符串 * @return string字符串 */ string minWindow(string s, string t) { const int m = ...

知识点单调队列思路需要维护一个窗口的最小值，是单调队列的应用场景。单调队列板子题。时间复杂度对于每个值只加入队列一次、出队列一次，时间复杂度为线性的，时间复杂度AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param k int整型 * @return int整型vector */ vector<int> minSlidingWindow(vector<int>& nums, int...

知识点模拟思路要统计有序数组中的线段，可以从左到右模拟，维护一个当前线段的起始位置，当不满足当前一对元素的差值为1的时候将当前元素加入答案，然后更新下一组线段的起始位置。时间复杂度只遍历一遍数组，时间复杂度为AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param groups int整型vector * @param n int整型 * @return int整型vector<vector<>> */ vector<vector&lt...

知识点双指针思路维护两个指针，i在左边，j在右边，i从左到右遍历，当遇到i指向的位置是1的时候，j向左移动找到最近的0，然后交换，如果i和j相遇则表示完成。时间复杂度双指针，每个节点只会访问常数次，时间复杂度为AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cows int整型vector * @return int整型vector */ vector<int> sortCows(vector<int>& cows) { i...

知识点哈希表思路用哈希表统计不同的体重的牛的个数，遍历所有的组，用一个布尔数组记录是否之前出现过。时间复杂度哈希表插入时间复杂度为总体时间复杂度为AC code (C++) #include <unordered_map> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param arr int整型vector * @return bool布尔型 */ bool uniqueOccurrences(vector<int>& arr) { unordered_m...

知识点快速选择思路要求时间复杂度为，我们可以使用快速选择算法解决。快速选择算法是在快速排序算法的基础上，选择整个数组中第k小的数。如果 那么结果一定出现在左半边，只需要递归left一共SL个数字如果 那么结果一定出现在右半边 ，只需要递归right一共k-SL个数时间复杂度AC code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param weights int整型vector * @param k int整型 * @return int整型 */ int findKthS...