知识点 单调栈 思路 我们可以使用一个单调栈维护weights数组的下标。遍历weights数组时，当weights[i]比栈的顶部对应的质量大时，更新答案数组ans[st.top()]=i-st.top()，并且将对应下标弹出栈。在栈顶下标对应的质量不大于当前weights[i]时，再将当前i入栈. 思路类似动态规划的最大上升子序列的单调栈优化 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param weights int整型vec...

知识点 模拟，排序 思路 每次在price中询问到第i个点，我们就将price[0~i-1]排序（注意数组下标从0开始） 若i+1为奇数，则说明当前的中位数是由两位数的平均值得来。 若i+1为偶数，则说明当前的中位数由区间[0,i]中间那一位数得来 初步判断算法时间复杂度为O(nLOGn),因为每次排序，只有第i位是变的，前i-1位已经有序。不过在此题中，使用sort也能通过，可能是数据范围比较小。 此外，可以考虑使用set来维护有序性，每次插入一个值的时间复杂度为LOGn 代码c++ public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规...

知识点 数组，模拟，STL（vector） 思路 不断更新区间片段的末尾，若出现不连续区间，则将当前区间的首尾更新至答案中，并且更新新的区间的首，详解看代码注释。 注意两个情况： ①初始化队头，末尾区间在循环结束后需要再更新到答案中一次。 ②对一个数单独成区间的情况，判断返回时，临时区间数组的size是否为1，若是，则说明当前区间只有一个数，再插入一个自己作为尾即可。 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param gr...

知识点 思维，数组函数 思路 首先我们假设数组长度为n，现将k%=n，因为可以先除去周期性。 我们知道，k次移位代表着前k个数的相对位置和后n-k个数交换，且内部次序不变。对数组的部分片段翻转2次，不会改变内部的相对顺序，对两个部分进行1次翻转，既会改变内部顺序，也会改变两个部分的相对顺序。 所以我们可以先对两个部分分别翻转，再整体反转，将内部次序保持一致，外部次序保持逆序。 例：对ABCDE FGHIJ 先翻转两个部分：EDCBA JIHGF 再整体反转： FGHIJ ABCDE 得到了想要的东西 代码 #include <iterator> class Solution ...

知识点 思维，模拟 思路 由题意，必然存在那个半数以上的数，所以我们理解成互相攻击问题即可。维护当前次数以及当前的编号，当出现不同编号时，次数--，如果次数小于等于0，那么更新编号。最后留下来的那个编号即为出现次数半数以上的数。 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int majority_cow(vector&l...

知识点 双指针 思路 用i和j分别维护当前遍历到的位置以及当前放置的位置。 当nums[i]!=nums[i-1]时，将其放在nums[j]处，同时j++。否则j不变。i始终保持右移。 最后数组中就去除了所有重复数字，并且j即为数组的大小。 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int remove_dupli...

知识点 双指针 思路 用i和j分别维护当前遍历到的位置以及当前放置的位置。 当nums[i]!=vals时，将其放在nums[j]处，同时j++。否则j不变。i始终保持右移。 最后数组中就去除了所有vals，并且j即为数组的大小。 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param val int整型 * @return int整型 */ ...

知识点 哈希，枚举 思路 首先，我们使用map<int,vector>来建立点的编号到对应编号所在的位置之间的映射（有序）： 对样例：1 2 3 1 int(编号) vector(所在位置集合) 1 0，3 2 1 3 2 然后，对每个相同编号的vector进行遍历，若存在vector[i]-vector[i-1]<=K,则说明题意所求存在，返回true。否则不存在，返回false 代码 #...

知识点 暴力 思路 观察到时间复杂度为O(n*n)，所以直接暴力枚举任意两个数，判断二者之和是否为目标值即可 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param breeds int整型vector * @param target_sum int整型 * @return int整型 */ int countMatchingPairs(vector<int>& br...

知识点 双指针 思路 我们可以假设连续递增的子序列左端点为i，右端点为j。对于ij，假设一开始位于下标为0处，不断右移j，若ids[j]>ids[j-1]则当前序列仍然为合法连续递增序列，否则需要更新i到j处，进行新的判断。 代码c++ #include <algorithm> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param ids int整型vector * @param n int整型 ...

知识点 哈希 思路 使用map构建标号到对应数量之间的映射，每新加入一个数，就更新这个数对应的哈希值（map[v]++）。 若此次加入的数v的map[v]比上一次的最大值max大，则更新最大值max与最大值对应标号idx，并且将标号加入答案数组中。 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector */ vector...

知识点 双指针 思路 由题意，标签的编号是不受原位置影响的，所以我们可以先排序，然后用类似双指针的思路，用l代表序列的左端点，i代表序列的右端点。我们先假设i位于下标为0的位置，然后向右递推i，显然连续的标签序列至少为1. 我们检查a[i]-a[i-1]==1，若为真，则i可以继续尝试向右移动，否则说明这个连续序列已经不合法了，将左端点l移动至当前的i位置。 使用ans维护最大的区间长即可，区间长度为i-l+1 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * ...

知识点 hash，STL(MAP,SET) 思路 首先，我们建立map用于记录从体重到对应体重数量的映射，遍历arr数组来维护map的value值。 然后，我们使用set来去重集合，若某个体重的牛的数量未出现在set中过，则加入set，否则返回false 最后，若没有返回false，则返回true 代码c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param arr int整型vector * @return bool布尔...

知识点 模拟，STL(SET判断存在性) 思路 我们可以发现，如果出现n按照操作变不成1的情况，那一定是陷入了循环。所以我们可以使用set来维护n出现过的所有变化情况，若出现重复出现的情况，则返回FALSE 否则返回TRUE。 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return bool布尔型 */ bool isHappy(int n) { // ...