知识点遍历数组思路求单峰的最大值的话，我们可以用二分解决，但是多峰的话二分无法解决。hack数据：[1,2,4,2,3,11][1,2,4,3,2,11]峰值中最高的牛，其实也就是最高的牛。遍历数据即可。时间复杂度AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param heights int整型vector * @return int整型 */ int findPeakElement(...

知识点贪心 堆思路我们按照cost的大小进行排序，每一次饲养可以选取当前cost允许养的利润最大的牛。实现上我们用一个指针来维护一下加入的位置，用一个堆来选每次最大利润的牛。一共进行k轮，k不大于n。时间复杂度为AC Code（C++） #include <numeric> #include <queue> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param k int整型 * @param w in...

知识点堆 多路归并思路如果直接维护一个堆来维护最大的k组数对，遍历每一对数，时间复杂度是，显然超时，不做讨论。我们考虑把每个priceA的位置当做一个组，然后每个组的起点位于priceB的末尾，建立一个堆选出那个组是最大的。首先我们把每个priceA的位置和priceB的末尾元素组成的组入堆。之后每次选出当前的最大元素后，我们看这一组是不是后继有人（意思是能不能把该组对应的priceB的指针往前走），如有把该候选数对入堆。因为每次出堆一个，入堆最多一个，堆的大小最多也就和priceA的大小一样。时间复杂度为AC Code（C++） #include <queue> #define...

知识点bfs思路每个点的应该放牧的值实际上是左右两侧最长上升路径的节点个数。可以找出最低的点，做多源bfs从而找到每个点的最长上升路径，这一步可以用bfs或者dijkstra算法。因为每个点在左右两侧的大小关系是固定的，每个点最多入堆常数次，时间复杂度为。AC Code (C++) #include <numeric> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param ratings int整型vector *...

知识点区间DP思路我们定义 f[i][j] 为s[i:j] 之中的最长回文子序列的长度，那么转移分为两种情况：两端相等， 可以从f[i+1][j-1] + 2 转移过来两端不等，可以舍弃一端，从max(f[i+1][j], f[i][j-1])转移过来最后的答案是f[0][n-1]时间复杂度 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型...

知识点区间DP思路我们定义 f[i][j] 为下标s[i:j] 是否是回文串。那么假如字符串两边相等的话，则可以从 f[i+1][j-1] 传递过来如果为回文串的话则更新答案。时间复杂度 AC Code（C++） #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ string longes...

知识点哈希表 模拟思路用哈希表记录一下每个字母对应的数值，模拟计算一下对应的数字，通过比较前面的数值和现在的数值来判断是加还是减。时间复杂度 AC Code（C++） #include <unordered_map> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cowsRomanNumeral string字符串vector * @return int整型 */ unordered_m...

知识点二分思路先二分找到可能存在的行，之后再二分找到可能存在的位置，进行判断即可。时间复杂度 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix int整型vector<vector<>> * @param target int整型 * @return bool布尔型 */ bool searchMatrix(vector<...

知识点字符串思路对每个字符串的字符统计计数，如果完全相同则为真。实现上对字符串排序即可。AC Code（python） # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string字符串 # @param t string字符串 # @return bool布尔型 # class Solution: def areHerdCompositionsEqual(self , s: str, t: str) -> bool: return sorted(s) == sorted(t)

知识点哈希思路首先统计每个字符串的每个字符的个数，如果两个字符串是同一类的，那么这个26个数所表示的状态就是一样的。因此我们只需要用一个哈希表来记录相同状态有哪些字符串再连接即可。实现上有两点，一是由于没有现成的哈希函数，unordered_map用不了，可以用map代替。第二点就是输出的格式很麻烦，要的是同一状态的字符串用逗号连接起来的结果中按字典序排序的结果。AC Code（C++） #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 ...

知识点计数思路从左到右遍历整个数组，维护当前元素和个数，当出现的元素和当前元素不一致时更新答案，注意个数为1不加入数字。时间复杂度AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param chars char字符型vector * @return char字符型vector */ vector<char> compress(vector<char>& ch...

知识点双指针思路我们将数组排序之后，枚举前两个元素，剩下的两个元素用双指针来得到，这样的时间复杂度是如果当前元素和上一次的元素是相等的，我们就可以跳过达到去重的目的。AC Code (C++) #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型vector&...

知识点贪心思路首先，grass的总和必须要比cost大，否则是不存在解的，一定走不完一圈。然后我们考虑从前往后模拟这一个过程，如果遇到累积的前缀和为负数，可以认为对结果没有贡献，可以舍弃，从当前的位置开始往后面走。时间复杂度为AC Code（C++） #include <numeric> #define all(x) (x).begin(), (x).end() class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param grass...

知识点二分答案思路类似H-index的定义，我们可以二分答案，然后进行验证即可。二分的时间复杂度为，每次验证是，总体时间复杂度为。AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param milk_production int整型vector * @return int整型 */ int cow_hp(vector<int>& milk_production) { ...