leetcode_summary.md

#2024.5.16

今日主题：链表
常用技巧 设置一个哑节点
、、、 ListNode* pre = new ListNode(val,head)
、、、

新算法：快慢指针： 1.通过设置一个慢指针，一个快指针，初始化快指针在慢指针前一步，慢指针一次走一步，快指针一次走两步，当他们再次相遇时，说明出现环； 2.通过设置一个慢指针和一个快指针，判断前后元素，实现数组重复元素的删除；

买卖股票的最佳时机：
动态规划思想，只遍历一次数组，维护一个价格最小值和利润最大值，每次假设以prices[i]卖出，更新最大利润；
注意：需要先更新利润最大值，再更新价格最小值；

#2024.5.21

每日一题：
2769：找出最大的可达成数字，简单数学题，每次靠近两个单位，故答案为num+2*t;

#2024.5.22

每日一题 2225：找到输掉零场或者一场比赛的玩家，思路很简单，用哈希表记录每个玩家胜利和失败的场次，再遍历所有玩家，将符合条件的分别加入answer数组。小问题：注意数组的初始化为0，动态数组要标注维度

189:轮转数组：核心思想为新数组的第（i+k）%n项为原数组的第i项，复制数组：
nums.assign(answer.begin(),answer.end());
小问题：当需要使用动态数组的未加入的长度时，初始化时需要先规定长度。

#2024.5.25

每日一题 2903：找出满足差值条件的下标，通过题意用下标关系控制循环，再用值来判断条件即可，最后记得特判

122.买卖股票的最佳时机Ⅱ，因为买卖机会无限，所以所有上升趋势的利润均可获得，差值大于0加上即可

55.跳跃游戏，遍历数组，维护能跳到的最大值，若遍历的值大于了最大值，则返回false

45.跳跃游戏Ⅱ，一层循环遍历数组，一层循环遍历可跳到的地方，更新每个最小次数
dp[i+j]=min(dp[i+j],dp[i]+1);
小问题：发现在类中不适合用memset，最好用动态数组 vector a(n,int_max);

274.H指数，该题的思想为h是符合条件数目和引用次数共同的参数，所以先排序，通过从引用次数最高的开始判断，往低遍历，符合条件的数目也同时增长，当遍历到的不再大于h，就停止。

#2024.5.28 每日一题 2951.找出峰值：正解为从1~n-1遍历一次数组，当元素同时大于两端元素时，即为峰值。刚开始想法为遍历数组，上升则继续，遇到下降时标记，当遇到再次上升时加入峰值并重新遍历，该方法边界难判定。

283.移动零：双指针题，left指针代表处理完毕的标志，left往左的都为非零元素，right一直往右移动，每次遇到非零元素时都会和left交换，直到遍历完毕。开始阶段可以理解为，若遇到非零元素，左右指针同时移动，则为自交换不改变，遇到零元素时右指针开始移动得更快。 该题型可理解为数组处理问题，可利用标记处理进度的方式解题。

136.只出现一次的数字；先排序，再遍历数组，若和两侧的都不相同，则为答案；因为要防止数组越界，所以需要特殊判断第一个和最后一个元素；最后还需要一个特判，当只有一个元素时直接输出。

#2024.5.29

238.除自身以外数组的乘积，一看到这道题O(n)的时间复杂度就想着要用前缀积处理，用前缀积除以当前元素，但是题目明显指出不能用除法，故放弃。既然如此，可以顺着前缀积的思路，预处理每个元素的左边的前缀积和右边的后缀积，这样用两边相乘即可得到答案。但是题目有要求O(1)的空间复杂度，所以只能利用答案数组，答案数组可以先存前缀积，在循环遍历的同时动态更新后缀积，即可实现。

28.找出字符串中第一个匹配项的下标，思路很简单，遍历主字符串，当遇到首字母相同时，判断接下来的一定长度内每个字母是否都相同，若出现不同则验证下一个，若都相同则可以输出答案。初始化答案为-1.

#2024.5.30

58.最后一个单词的长度，逆向思维，从字符串尾部往前遍历，找到第一个不为空的字符即为最后一个单词的尾部，往前找到第一个为空的下标，之间即为长度。

53.最大子数组和，最开始想到利用前缀和的方法，但是时间复杂度过高，所以我们借用其思想，思考更优的方法，即通过O(n)的时间复杂度，预处理或者维护一个最大值。最后选择了动态维护一个最大前缀并且动态维护答案。主要代码如下： 、、、
cnt = max(cnt+nums[i],nums[i]); ans = max(ans,cnt); 、、、

2024.5.31

每日一题 2965.找出缺失和重复的数字，最简单思路即为哈希表，遍历数组，记录出现的频次，再次遍历哈希表找出值为0和2的下标即可，该方法时间复杂度和空间复杂度都为O(n²)。所以我们应该思考更优的方法，刚看到这道题时，其实就想到了矩阵求和有什么性质，假设a出现了两次，b出现了零次，此时矩阵的和减去数列1n²的和，差值为a-b;得到了一个式子还不足以解出答案，所以我们应该寻找另一个表达式的值，所以我们想到了利用矩阵元素的平方和，用当前矩阵的平方和减去数列1n的平方和，差值为a²-b²=(a+b)*(a-b),所以这时我们就可以联立方程组进行求解了。假设第一个差值为d1，第二个差值为d2，则a=(d2/d1+d1)/2,b=(d2/d1-d1)/2,顺利结束。这个算法只用了O(1)的空间。小问题：1.注意n²求和的范围，需要开longlong 2.数组长度为n，但是最大数为n².

2966.划分数组并满足最大差限制，看到这题的意思，就能想到是考虑相邻k个数的关系，所以我们选择先对数组排序，原数组肯定为3的倍数。之后就开始遍历数组，i每次+3，先判断两端数字的差是否满足条件，若满足，则将这三个数字作为一个数组插入到答案数组中，当然，我们还需要一个标记，当出现不满足的数字时，我们返回空数组。小问题：二维数组初始化可以只定义行数，也可以都定义。当我们定义了长度之后，相当于数组已经存在了n个0，所以这时进行替换操作更好，如果我们要在末尾加入，则原始的0还存在，所以这时不建议初始化长度。

2024.6.1

每日一题 2928.给小朋友们分糖果 Ⅰ，考虑到数据范围较小，本题可以直接通过枚举两个小朋友得到的糖果数，再判断第三个是否满足条件就可以。当然对于数据范围较大的情况下时，本方法就不适用。可以通过数学中的容斥定理求解。

2929.给小朋友们分糖果 Ⅱ，这时数据范围变大，我们需要改进枚举的方法，只能使用O(n)的时间复杂度，所以我们只枚举第一个小朋友得到的糖果数量，之后我们需要判断当前情况是否能继续分，当n-i>2*limit时，说明肯定不满足，continue;如果满足，我们则需要算出当前所有的方案数，因为确定第二个小朋友的糖果数量后第三个就自然确定，所以方案数就等于第二个小朋友可能获得的糖果数，所以我们找到肯能得到的最多糖果和最少糖果进行作差即可得出答案。 ans+=min(n-i,limit)-max(0,n-i-limit)+1;

2024.6.2

周赛题目 100307.候诊室中的最少椅子数，设置两个变量，ans代表一共需要的椅子，cnt代表现有可用的椅子，判断三个状态即可，当读取到'E'时，若cnt==0，ans++，若cnt>0,，cnt--; 当读取到'L'时,cnt--;最后返回ans即可。

100311.无需开会的工作日,思路为先排序数组，然后遍历时间数组，维护一个上次会议的结束时间，每次判断开始时间是否大于上次的结束时间，如果大于，则把他们的差值加上，然后重新更新结束时间，注意，最后一次会议需要再判断一次。

100322.删除星号以后字典序最小的字符串,开一个大小为26的动态二维数组，负责存储每个字母出现的次数，以及每次出现的下标，遍历数组，如果遇到'*'，则遍历哈希数组，最小不为空的字符把最后一次出现的位置弹出，若没遇到，则把字符的下标存入。再定义一个答案字符串，遍历字符数组中出现的位置，将存在的下标对应的字母逐个加入到答案中。

每日一题

575.分糖果，根据题意，最多的数目肯定不会超过n/2，也不会超过所有糖的种类数。所以我们只需要比较两者的大小关系即可，关键是求出种类数。我们利用C++中的数据结构set， return min(unordered_set(candyType.begin(), candyType.end()).size(), candyType.size() / 2); set可以自动去除重复的元素，它的长度就代表了种类数。

2024.6.3

每日一题

1103.分糖果 Ⅱ，根据题意模拟即可，维护一个当前应发的糖果值，当糖果数不为0时，遍历数组，判断当前剩余和应发的大小关系，更新答案数组和剩余值及应发值。

1109.航班预订统计，该题考查的是大量的区间修改后查询区间的值。我们采用的是差分数组的方法，先初始化一个差分数组，由于刚开始原数组都为0，所以差分数组初始化也都为0。每当有一个修改操作进行时，传入三个参数l，r，w，执行以下操作： a[l]+=w; a[r+1]-=w; 即可得到差分数组，将区间修改操作时间复杂度降至常数级。 得到差分数组之后，进行前缀和操作即可恢复原数组。 做前缀和时，可以不用开新的空间，在原数组操作即可。

2024.6.4

每日一题

3069.将元素分配到两个数组中 Ⅰ，按照题意模拟即可，新建两个数组，依次判断加入，最后合并最终答案数组即可。

3070.元素和小于等于k的子矩阵的数目，根据题意，很明显想到前缀和的知识，这里其实是二位前缀和的模板，算出所有前缀和并判断条件即可。 sum[i+1][j+1]=sum[i][j+1]+sum[i+1][j]+grid[i][j]-sum[i]

2024.6.5

每日一题 392.判断子序列，利用双指针的思想，遍历主字符串，当遇到相等的字母，目标字符串下标+1.判断最后的下标，若刚好为字符串的长度，即为正确。

383.赎金信，利用哈希表的思想，先构建一个字符计数数组，负责统计ransomNote中字符出现的次数，然后再遍历magazine数字，如果每个字符对应的计数数组都够用，那么证明可以完成。

2024.6.6

每日一题* 2938.区分黑球和白球，刚开始没认真审题，没发现只能交换相邻的球，所以写了一个头尾的双指针，导致了错误，但是还是有两个收获，第一个是利用while写头尾双指针的题目时，一定要加上边界判断，及时跳出循环，否则会一直超时;第二个是对于一个数字字符串赋值或者判断值时，一定要用引号，不能直接给出数字。弄清楚题意之后，可以利用贪心的思想，我们发现从左遍历字符串，每次遇到一个0，就要把它移动到左边，移动的次数为它左边1的个数，因为1肯定要越过最右边的0，所以我们只需要维护一个当前状态下遇到1的个数，再维护一个当前移动的次数，每次遇到1时，sum++，遇到0时，ans+=sum.

209.长度最小的子数组，该题最差的算法为循环暴力求解，每次更新最小值；再其次到前缀和+二分查找的方法，该方法也需要每次从起点开始遍历;最优算法为滑动窗口，从0开始，累加至>=target，此时开始判断，若start往前还是满足和的条件，则不断尝试更新当前子数组的和以及最小长度，若不满足和的条件，则数组末尾继续往前，一直延申至数组末尾。

2024.6.7

每日一题 3038.相同分数的最大操作数目 Ⅰ，该题为简单模拟题，先计算出前两个元素的和，依次往后遍历两个元素，若它们和与之前的相同，则答案++，若不同则直接跳出，结束。

134.加油站,该题最开始想到令每个加油站作为起点遍历一次数组，若能回到原点，则证明它为答案；但是该方法时间复杂度过高，我们需要进行优化，我们可以进行数学推导，若从i出发，到达j时不满足条件，不能继续前进，那么从i-j之间任何一个加油站出发都无法满足条件，所以我们直接从j+1个开始向前判断，降低了时间复杂度。每次遍历一个节点时，新建一个cnt向前，当向前超过数组最大数量时，我们需要用取余代表取回前面的节点。

135.分发糖果，从题目出发，刚开始理解为找到数组中最大的值，依次往两边递减，但是不好实现，所以作罢;后面又考虑到可以通过计算左边的上升子序列的长度和右边下降子序列的长度，再求其中的最大值求解，为了降低时间复杂度，所以我们可以通过两次遍历数组来代替二重循环;第一次从左到右遍历，算出每个元素连续左边上升序列的长度，第二次从右往左，算出每个元素右边连续下降序列的长度。同时，可以只开一个数组，第二次遍历用一个变量储存当前值，可以降低空间复杂度。

2024.6.8

每日一题 3040.相同分数的最大操作数目 Ⅱ，通多题意可知，该题最多有三种操作分数，分别是前两个，最后两个，以及第一个和最后一个的和。从这里也可以看出一共有三种状态转移方式，所以我们可以利用DP或者记忆化搜索的方式来求解。对三种操作分数分别求最大次数，再求他们的最大值。依次判断三个状态，当前区间的前面两个，最后两个，以及第一个和最后一个，直到遍历区间长度为1就可以求出整个区间的答案。

516.最长回文子序列，该题是一个区间求最值问题，我们自然地想到可以通过小区间转移到大区间来进行求解，状态转移就对应着动态规划或者搜索算法。在本题中我们使用DP思想，从尾部开始遍历字符串，对于每个字符再遍历它之后的元素，一共有三种状态，当i==j时，令数组为1;当s[i]==s[j]时，我们还要分情况讨论，如果i==j-1，此时直接令数组为2，因为下一个状态i>j;如果i！=j-1，那么f[i][j]=f[i+1][j-1]+2; 最后一种情况是，当两个字符不构成回文子串时，我们选择上一个状态下最大的一端继续前进，
f[i][j]=max(f[i+1][j],f[i][j-1]);

2024.6.9

每日一题 312.戳气球，根据题目的意思，我们需要依次戳破区间内的所有气球，得出最后的答案，那么我们可以看出本题的思想为动态规划的状态转移，枚举每个可能作为最后一个戳破的气球k，ij为区间的两个端点，每次区间的长度从3开始往后枚举，模拟从戳破最后一个气球开始往回倒推的过程。刚开始时需要新建一个数组加入前后两个端点值。状态转移方程如下： f[i][j]=max(f[i][j],f[i][k]+f[k][j]+cnt[i]*cnt[j]*cnt[k]);

周赛题： 100325，找出K秒后拿着球的孩子，本题为简单模拟，我们只需要遍历时间，每次更新当前拿着球的孩子即可，但是传球的方向会改变，所以我们需要定义一个方向变量，当回到第一个时方向为1，到达最后一个时方向为-1.

双周赛题： 100324，清楚数字，本题为简单模拟题，可以理解为当遇到字母时就将该元素入栈，遇到数字时就出栈，模拟完成即可。

定义栈： std::stack charStack; 判断元素是数字或字母：isdigit(),isalpha() 栈相关操作：Stack.pop(),Stack.empty(),Stack.push() 最后需要将栈转为字符串，定义一个空字符串，将Stack.top()依次加上

2024.6.10

每日一题 881.救生艇，依据题意可以看出这道题是一道贪心的题目，即越多地安排两个人坐一艘船更好，所以我们想到每次都用最小和最大的组合，判断是否能够合并，故需要先进行排序，然后利用双指针的特性，如果前后两个可满足，那么就共同向中间靠近，如果不满足，就后面的往前一个单位。最后需要注意的是，需要判断当最后只剩一个人的时候 ，再加上一条船。

125.验证回文串，依据题意模拟即可，首先新建一个字符串，将原字符串的数字元素保留，字母元素转为小写之后保留，再利用双指针方法逐次向中间靠拢，只要有一组不相同，直接返回false，直到遍历整个字符串。

if(isdigit(s[i])) ans+=s[i]; if(isalpha(s[i])) ans+=tolower(s[i]);

167.两数之和Ⅱ-输入有序数组，该题数组已经排序好了，且答案只有一种可能，那么我们只需要遍历数组，找到一个正确的答案就退出即可。为了降低时间复杂度，我们可以通过二分查找或者双指针的方法来求解。利用二分查找的方法时，我们只需要遍历一次数组，定义一个low，一个high指针，分别判断每次和的结果，如果等于目标则直接输出，若大于，则high=mid-1，若小于，则low=mid+1，可以快速完成数组的查找，最后如果都没有找到就返回-1。当我们使用双指针方法时，我们只需要定义头尾两个指针，依次向中间靠拢，如果等于目标值就返回，如果大于就后者往前，小于就前者向后，注意题目中下标从1开始，所以答案需要+1再输出。

2024.6.11

每日一题 419.甲板上的战舰，一看题目，就感觉是用dfs来求解，但是再想想更简易的方法。我们可以看到战舰是一个特殊的连通块，即一列或者一行，并且没有相邻的战舰，所以我们可以通过枚举战舰起点的方式来求解。遍历二维数组，如果找到'X',只需要判断其左边或者上面是否有'X'就可以判断出它是否是战舰的起点，如果是起点，那么答案加一。

15.三数之和，这一题我的方法是利用三种循环实现，但是最后会超时，于是我增加了一些剪枝操作，当一些情况下提前退出循环，但是始终无法通过，于是我发现了自己对于双指针的理解还没有很彻底。我认为我的代码实现了双指针，双循环枚举起点和终点，用while不断将mid向前，但是分析一下逻辑，这实际上还是三重循环，并没有真正实现双指针，所以这告诉我们，实现双指针不是用特定的代码结构就可以，而是真正的代码逻辑层面实现。所以我们应该通过枚举起点，固定终点，再枚举中间点，逐步寻找满足条件的三元组即可。

2024.6.12

每日一题 2806.取整购买后的账户余额，这题是个简单模拟题，我们只需要，算出两个数一个是购买金额除10，一个是除10后的余数，再判断余数的大小，如果大于等于5就需要购买(n+1)10,否则购买n10.

2810.故障键盘，简单模拟，新建一个字符串，遍历原字符串，当不为'i'时，字符加入新字符串，若读取到'i'，则反转字符串
reverse(ans.begin(),ans.end());

104.二叉树的最大深度：本题的用意是学习递归和二叉树结构，在函数中，只有传递的节点为空时，我们才会返回，否则我们会继续往下寻找，并且每次递归时答案+1，只有最后一步才处理，答案在过程中递增。

70.爬楼梯，递归模板，动态规划模板，初始化第一和第二的答案，后续的答案为前两个相加即可。

242.本题为简单哈希表题目，先判断两字符串的长度是否相同，若不同，则直接返回false，如果相同，我们先统计s的字符哈希表，再遍历t字符串，如果不够用了，则返回false，否则返回true.

2024.6.13

每日一题 2813.子序列最大优雅度，本题利用了贪心的思想，首先将items按照profit从大到小进行排序，当子序列为前k个项目时，子序列的利润总和最大，但是总优雅度不一定最大，所以此时我们向后遍历，当下一个元素的类别出现两次以上，取利润最小的项目进行替换即可增加总优雅度，用栈来维护整个序列。

2879.显示前三行，这个是python中pandas库的使用，直接返回.head(n)即可

2894.分类求和并作差，这个是一个简单模拟题，遍历1到n，刚开始可能想到用两个变量来存，后面发现用一个变量也能完成，不整除的加上，整除的减去即可。

2024.6.14

每日一题 2786.访问数组中的位置使分数最大，看到这题就想到动态规划的思路，遍历数组，每次选择移动该元素时能获得到的最大值，分别考虑最后一个的元素为奇数/偶数的最大值，用长度为2的数组来储存这两个值，每次遍历到一个值就更新。

2652.倍数求和，该题一看就是简单模拟题，遍历一次当能整除就加上即可。但是这样时间复杂度太高，所以考虑数字中的容斥原理。只考虑整除一个数时，答案数列是一个等差数列。根据容斥原理，最后答案为三个数的答案，减去两两结合的答案，再加上三个一起的答案。

2024.6.16

周赛题目 100304.构成整天的下标对数目 Ⅰ，简单模拟题，遍历数组，若找到两个下标对应的数加起来为24的倍数，那么ans++.

100301.构成整天的下标对数目 Ⅱ，上题的数据增强版，这里我们考虑查询和维护即可，遍历数组，当每次加上能满足条件的数组的下标个数，再更新当前的数组值 ans += cnt[(24 - t % 24) % 24]; cnt[t % 24]++;

每日一题 521.最长特殊序列 Ⅰ，脑筋急转弯，其实这里的特殊序列只要是自己的字串即可，那么我们直接取本身就是最长，如果两个字符串不相等，直接取两者的长度最大值就好，如果相等，就返回-1.

221.最大正方形，二维前缀和模板，先处理出二维前缀和数组，再进行二分查找降低复杂度。

2024.6.17

每日一题 522.最长特殊序列 Ⅱ，本题为前者的升级版，从两个字符串变成一个字符串序列了，所以我们需要依次枚举字符串来进行判断。先写一个判断两字符串是否相等的函数，然后枚举字符串逐个判断是否相等，若不相等则更新长度。

326.3的幂，简单模拟题，不断判断是否为3的倍数将数除3，判断最后是否为1，若不是则输出false.

389.找不同，本题为哈希表的简单应用，只需要先统计s字符串的哈希表值，再遍历t字符串，当遇到哈希值为的字符就返回.

455.分发饼干，简单排序+双指针的题目，首先对两个数组进行排序，之后利用双指针分别指向两个数组的起点，若满足条件，则一起前进，若不满足，则S数组的指针前进。

2024.6.18

每日一题 2288.价格减免，这是一道纯字符串的题目，我们的目标是识别出字符串中的价格并将它替换为折扣后的数字。这道题利用了一些字符串的关键字： stringstream 是C++标准库中的一个类，属于 头文件。它提供了一种方式来处理字符串，就像使用流一样，可以轻松地将数据读入或写出到字符串。 #include stringstream ss; // 创建 stringstream 对象 ss << "Some data"; // 向 stringstream 对象写入数据 string data; ss >> data; // 从 stringstream 对象读取数据

all_of 是C++算法库中的一个函数，位于 头文件。它用于检查给定范围内的所有元素是否都满足特定的条件。 #include string s = "12345"; if (all_of(s.begin() + 1, s.end(), ::isdigit)) { // 从 s.begin() + 1 开始到 s.end() 所有的元素都满足 ::isdigit 条件 }

fixed：指定浮点数应该以固定的小数点格式输出。 setprecision(2)：设置小数点后保留两位数字。 stoll(w.substr(1))：将字符串 w 去掉第一个字符后的剩余部分转换为长长整型（long long）

219.存在重复元素，这道题的本质上是滑动窗口的模板题，我刚开始的想法是遍历数组再同时向前遍历k个元素来判断，此时时间复杂度为N*K，为了降低，应使用set结构。 set的基本语法： unordered_set s 定义初始化 s.emplace(nums[i]) ：插入元素 s.erase(nums[i - k - 1]) ： 删除元素 s.count(nums[i]) ：判断s中是否已经存在该元素

2024.6.19

每日一题 2713.矩阵中严格递增的单元格数，这题是一道动态规划问题，因为可以跳转到同一行同一列的任意位置，所以我们不需要记录前一个状态，只需要记录更新到每个位置能得到的最大值即可，同时更新每列和每行的最大值。

35.搜索插入位置，本题为二分查找模板题，目的是掌握二分的正确写法，这里就列出三种区间下的二分写法： // 闭区间写法 int lower_bound(vector &nums, int target) { int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right] while (left <= right) { // 区间不为空 // 循环不变量： // nums[left-1] < target // nums[right+1] >= target int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; // 范围缩小到 [mid+1, right] else right = mid - 1; // 范围缩小到 [left, mid-1] } return left; // 或者 right+1 }

// 左闭右开区间写法
int lower_bound2(vector<int> &nums, int target) {
    int left = 0, right = nums.size(); // 左闭右开区间 [left, right)
    while (left < right) { // 区间不为空
        // 循环不变量：
        // nums[left-1] < target
        // nums[right] >= target
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1; // 范围缩小到 [mid+1, right)
        else
            right = mid; // 范围缩小到 [left, mid)
    }
    return left; // 或者 right
}

// 开区间写法
int lower_bound3(vector<int> &nums, int target) {
    int left = -1, right = nums.size(); // 开区间 (left, right)
    while (left + 1 < right) { // 区间不为空
        // 循环不变量：
        // nums[left] < target
        // nums[right] >= target
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid; // 范围缩小到 (mid, right)
        else
            right = mid; // 范围缩小到 (left, mid)
    }
    return right; // 或者 left+1
}

2024.6.20

每日一题

2748.美丽下标对的数目，这道题可以通过暴力求解，也可以使用哈希表来求解，同时通过本题，我发现了C++的gcd函数可以直接调用.暴力方法为两重循环遍历，判断他们的gcd是否为1；哈希表的方法为，不提前处理出哈希表的值，而是遍历数组的同时，对于每个当前数字的第一个，寻找哈希表中互质的数字是否存在，若存在则把所有答案加上，做完这个操作后再将当前的数字加入哈希表(即哈希表中存的是当前元素之前的元素最后一个数字的相应出现次数，保证了有序性),从这题可以得出一个启示，在一些需要保证顺序的题目里，我们可以在遍历的途中同时更新表值，gcd函数:gcd(x,y)

118.杨辉三角，这是一道动态规划的入门题目，依题意每个元素等于它上面的两个元素求和，所以我们首先规定每行第一个和最后一个元素为1，然后再依次遍历这一行每一个元素，令其为它左上角和右上角元素的和即可，注意控制数组的大小。

2024.6.22

每日一题

2663.字典序最小的美丽字符串，该题考察了回文串的性质，一个回文串去掉首尾字母后，仍然是回文串，可以根据这一性质得到如果没有长度为m-2的回文串，那么就不会有长度为m的回文串.由答案取的是最小字典序进一步推论得，不可能存在s[i]==s[i-1]以及s[i]==s[i-2].

560.和为K的子数组，该题中的子数组是连续的，所以可以看做是滑动窗口的模板，在这我们使用的是哈希表+前缀和的思想，两个下标的前缀和数组相减即为他们之间元素的和，我们只需要遍历依次数组，同时检查哈希表中是否有符合条件的键值，若存在，则把对应的值加上，同时更新哈希表的值.

2024.6.23

每日一题

520.检测大写字母，本题是简单模拟题，考察了ASCLL码相关的知识，根据题意，本题对于字符串有三种正确的用法，所以我们分三类来讨论，先根据首字母的大小写来分类，如果首字母大写我们计数剩下字母串大写字符的数量，如果为0或者为n-1就成立;对于首字母小写的情况，我们同样计数，若后续大写字母为，则符合.判断大小写可以用用字符-'a'的数值来判断，也可以直接和字符判断 if(word[i]>='A'&&word[i]<='Z') ans++;

周赛题目 100342.最小元素和最大元素的最小平均值，这道题本来想用简单数学的方法来求解，认为最后两个移除的元素肯定是最小值，也就是答案，后面才发现自己的想法出问题了，会有特殊情况，所以必须依次比较。设置头尾双指针，依次计算平均值取最小，计算后两端向中间靠拢，最后输出答案。注意数据格式。

2024.6.24

每日一题 503.下一个更大元素 Ⅱ，刚开始思考时，会想到坐标变换，进而想到每个数字追多遍历数组的两倍长度，即我们可以把数组整体往后复制一遍，遍历查询即可，但是时间复杂度太高，考虑其他算法;使用单调栈，单调栈中保存的是下标，该下标数组在原数组对应的值是单调不升的，每次我们移动到数组中的一个新的位置 iii，我们就将当前单调栈中所有对应值小于 nums[i] 的下标弹出单调栈，这些值的下一个更大元素即为 nums[i]（证明很简单：如果有更靠前的更大元素，那么这些位置将被提前弹出栈）。随后我们将位置 iii 入栈。 但是注意到只遍历一次序列是不够的，例如序列 [2,3,1][2,3,1][2,3,1]，最后单调栈中将剩余 [3,1][3,1][3,1]，其中元素 [1][1][1] 的下一个更大元素还是不知道的。

2024.6.25

每日一题

2723.找到矩阵中的好子集，该题考察了一定的数学推导能力，如果答案只有一行，那么必须全0，如果是2-3行，那么每列只能有一个1，如果答案超过四行时，每一行的和最多是k/2，任意两行的AND均不为0，每一行的1的个数的平均值是n/2。遍历每行，算出一个二进制数，去重保存到哈希表中，如果有一行全为0，则返回该行的行号，否则写一个二重循环，枚举哈希表中选两个数的所有组合，若出现AND等于0，那么返回行号。

20.有效的括号，这题是一个栈的模板题，我们先用map储存相应的括号对应情况，只存后括号，前面的不需要匹配，直接入栈即可，判断的时候需要判断栈顶元素是否和相应的键值匹配。

2024.6.26

每日一题

526.优美的排列，该题考察的是状压dp的知识，用一个n位的二进制数表示排列中的数被选取的情况，若为1，则表示该位被选取，若为0，则表示该位没有被选取，用一个数组来存储当前情况下的排列数，当前的状态应该由以下所有情况转移而来:枚举当前二进制数中1的位置，若该位置往后一位满足题目的条件，那么就加上这个状态的排列数，遍历所有，最后输出f[(1<<n)-1]; __builtin_popcount(mask) 该函数的作用是返回该二进制数中1的个数.

2741.特别的排列，这题跟上题有些相似，不过这些数字不是依次增大的，利用递推的方法，不断寻找前一个状态的值，并且累加。

2024.6.27

每日一题

2734.执行子串操作后的字典序最小的字符串，根据题意，只会出现一次操作，令一个区间内的字符变成自己的前一个字母，所以只有'a'是特例，其他都符合条件，那么我们先判断字符串是否为全a，如果是那么就只用把最后一个a换成z即可；如果不是全a，我们就需要找到第一个不为a的字母，开始遍历，直到找到下一个a字母，这之间都需要改变，对于该题中的字母变换，只需要s[i]--即可完成变换。

50.Pow(x,n),本题考察的是快速幂算法，利用了递归的思想，计算x的n次方时，可以先计算出y=n/2次方，判断N是奇数还是偶数，如果是偶数就是yy，奇数则为yy*x.递归边界为N=0.

2024.6.28

每日一题

2742.给墙壁刷油漆，根据题意，可以得出几个结论，首先是付费刷墙的总时间要大于等于免费刷墙的个数，其次是付费刷墙个数与免费刷墙个数之和为n，结合之后得到付费刷墙时间之和大于等于n-付费刷墙个数，即[付费刷墙时间+1]之和大于等于n，所以我们把这个看作一个01背包的题目，时间+1作为体积，花费作为价值。

190.颠倒二进制位，本题考察的是基础的位运算性质，相关解释如下： uint32_t rev = 0; uint32_t 这个是用来定义一个32位的二进制串 rev|=(n&1)<<(31-i); n>>=1; 上述代码的意思是每一取n中的最低位，并且将它移动到最前面，用答案字符串进行或运算，因为它本身为全0，所以答案的每一位全部取决于原二进制位，每次操作之后将原字符串右移一位，表示最低位处理完毕，舍弃之后对下一位 继续处理。

2024.6.29

每日一题

2710.移除字符串中的尾随零，本题是一个简单模拟题，考察一些字符串的基本操作，最直接的思想就是从后往前遍历，标记第一个不为0的下标，然后取这个下标之前的数即可。 return num.substr(0, num.find_last_not_of('0') + 1);

substr的作用是只保留范围内的字符，find_last_not_of的作用是找到最后一个不为0的位置，也可以手写循环代替。 string res(num,0,i+1) 这个和以下代码等效 num.substr(0,i+1);

2024.6.30

周赛题目

100340.三角形的最大高度，本题是一个简单模拟题，根据题意，一共有两种情况，分别是蓝球和红球在第一层的情况，所以我们只需要分别执行这两种情况来计算高度，答案是这两种情况下的更大的一方，通过判断层数的奇偶性来判断即可。

每日一题

494.目标和，利用动态规划的思想，假设neg是所有添加负号元素的和，那么可推出，如果整个数组的元素的和减去目标元素不是偶数就直接返回零;现在问题就转变为通过从数组中选取若干元素作为添加负号的元素，他们的和要与全部元素的和减去目标值再除以2相等，所以就转换为动态规划问题，dp[i][j]表示从前i个数种选取元素使得与j相等的方案数，最终答案为dp[n][(sum-target)/2];

2024.7.1

每日一题

2065.最大化一张图中的路径价值，本题可以从数据范围得到思路的参考，根据总最大时间和单个最小时间得到最多可以有十条边，即搜索树有11层，每个节点最多有4个儿子，可视为一棵层数至多为11的四叉树上递归。本题还可以利用Djikstra最短路算法进行剪枝，提前处理好起点到每个节点的最短路，同时也是每个节点到起点的最短路，在递归到下一个节点之前，判断下一个节点在走最短路的前提下，能否在maxTime时间内回到起点0，若不能，则不递归。

11.盛最多水的容器，本题是一个双指针的题目，依据题意得，水量等于两边高度更小的一边乘上下标之差，所以我们只需要利用双指针遍历一次数组即可得出最终答案，每次更新当前最大值，并且令两端更小的向中间靠拢，本质上是一个贪心的思想。

380.O(1)时间插入、删除和获取随机元素，本题是利用unordered_map数据结构来存储对应值和下标的键值对，该数据结构可用来当作哈希表，插入为insert，删除为erase，并且用末尾元素填充。获取随机元素的函数：rand()

2024.7.2

每日一题

3115.质数的最大距离，本道题是一个简单的模拟题，题意是找到数组中第一个质数和最后一个质数，可以通过写一个质数筛来预处理标记质数再输出即可;由于本题的数据范围较小，所以我们只需要用最简单的指数判断方法即可，每个数都遍历到它的根号范围，然后分别通过正向和反向遍历找到第一个和最后一个质数，输出他们的下标差即可。

1441.用栈操作构建数组，本题是一个简单模拟题，遍历n，当我们的目标数字在target中就只用Push，否则需要先Push再Pop，维护一个prev记录上一次操作时栈顶的索引值。

2024.7.3

每日一题

3099.哈沙德数，简单数学题，我们的目的是计算出每一位数的和，所以我们每次取数模10的结果，然后令其除10，最后判断是否能整除即可。

205.同构字符串，本题是考察哈希表的知识，根据题意，同构的条件是s的字符都按照某种映射关系得到t，所以我们通过构建两个哈希映射，分别代表s到t和t到s的映射，然后遍历字符串，如果出现映射不同的情况，则不满足条件，直接退出。

31.下一个排列，本道题考察的是双指针，题目的意思是找到下一个字典序更大的排列，所以我们的任务是把一个数组右边的一个较大数与数组左边的一个较小数交换，并且它们的距离应当尽量近，所以算法的步骤就是首先从后往前查找第一个顺序对，不满足降序的关系，标记为i.然后在i+1到n从后往前查找第一个下标j满足后数大于前数，然后交换两个数，并且将i+1到n之间的序列反转.

2024.7.4

每日一题

3086.拾起k个1需要的最少行动次数，在这道题我们可以把0看成空位，第二种操作相当于把一个1移动到和它相邻的空位上，而第一种操作则是贪心地把和当前下标相邻的0变成1;当maxchanges较大时，优先使用第一种操作+第二种操作;maxchanges较小的情况是，几所所有长为k-maxchanges的子数组的货仓选址问题，再取最小值。

78.子集，这道题用的是回溯的算法，也可以说是深度优先搜索。通过设置一个当前遍历的元素个数和需要遍历的数组来维护dfs函数，维护一个当前的集合和答案集合，当个数达到原数组大小时返回，遍历时包含两种情况，分别是考虑当前元素和不考虑当前元素，每次都先达到了最大元素个数，再依次返回。

2024.7.5

每日一题

3033.修改矩阵，本题为简单模拟题，题意是找到每列的最大值，然后把值为-1的更换即可，所以我们需要遍历两次数组，第一次把不是-1的点写入并且维护列的最大值，第二次把-1的点用列最大值更换即可。

228.汇总区间，这道题可以看作一个双指针的题目，任务是遍历数组，当找到不是逐个递增的元素时就把此前的范围按规则加入字符串，所以我们需要标记左指针和遍历找到右指针，找到右指针后更新字符串并且更新左指针。这道题要注意一个细节，当我们判断相邻元素是不是相差1时，不要用减法，而是用加法，因为减法会导致数据范围越界的问题。

202.快乐数，这道题直接看就是通过判断一个数通过规则变换能不能最终回到1或者是进入无限循环，如果我们根据路线就可以得出是判断有没有环的题目，所以我们可以使用快慢指针的方法，若循环，即出现环时，快指针会追上慢指针。初始化为快指针在慢指针前面一步，然后每次快指针走两步，慢指针走一步，如果追上了，证明有循环，否则快指针会回到1.

2024.7.6

每日一题 3101.交替子数组计数，这道题刚开始看到时想用双循环遍历数组以及位运算来判断是否为交替子数组，但是数据范围不允许，所以只能考虑一个循环，先考虑数学推导看看规律。经过数学分析发现，只需要枚举数组的右端点，维护一个当前子数组值的变量，当前数和前一个数不一样时，我们就令子数组的元素个数+1，如果相同，我们就令变量重新为1，然后每次循环结束都把当前的值加到答案中，保证能计算到每个右端点代表的子数组的值。

365.水壶问题，这个是一道搜索题，这里我们使用dfs进行求解，先设置一个栈，来储存当前两个水壶中的水量，再定义一个哈希函数，用来计算两个数的哈希值，保存在哈希表中，作为他们的唯一标识。一个哈希表来存两个水壶，一个哈希表用来存键值对和它们的哈希值。然后依次判断是否已经储存，如果有就弹出继续;如果没有，就放入，判断是否满足条件，如果不满足，再依次把六种可能的情况放入，分别是把 X 壶灌满，把 Y 壶灌满，把 X 壶倒空，把 Y 壶倒空，把 X 壶的水灌进 Y 壶，直至灌满或倒空，把 Y 壶的水灌进 X 壶，直至灌满或倒空。

2024.7.10

每日一题

2970.统计移除递增子数组的数目 Ⅰ，这道题是一个考察双指针的题目，也考察了数组的基本性质。题目的意思是要统计有多少个子数组能满足移除后剩下的元素为严格递增的关系，刚开始没考虑到移除的元素要是连续的，所以出错了。考虑到这个问题之后，我们可以分类来讨论;首先，我们可以先统计一下数组的最大前缀， 如果整个数组都是递增的，那么我们就不用再算其他情况了;如果不是，那我们就先加上只考虑所有递增前缀的答案，是最大递增前缀的下标加2;然后我们再考虑一般情况，即移除中间数组，这样的情况会造成一个递增前缀和一个递增后缀，且连接处前面的小于后面的。对于这种两边都需要枚举讨论的题目，我们可以只枚举一边，然后判断另外一边的数值，所以我们选择枚举后缀，只要后缀满足往前递减的关系，我们就进行计算，我们先让最大递增前缀往回，直到连接处满足关系，然后此时答案就是最大前缀的下标加2，剩下的任务就是模仿这个过程完成循环，直到后缀不满足情况就结束。

63.不同路径 Ⅱ，这道题是一道简单动态规划题目，主要目的是训练我们的DP思想。根据题意，机器人往右走或者往下走，所以每一步的方法数是上面一步的方法数加上左边一步的方法数。但是我们注意到有障碍物，所以当遇到障碍物时，我们令其的总方法数为0即可。本题还需要进行初始化，先判断起点，然后再初始化第一排和第一列，初始化也需要判断障碍物。

2024.7.11

每日一题

2972.统计移除递增子数组的数目 Ⅱ，这道题和昨天的前置题目思路完全一样，只是数据范围变大了。我们还是先处理最大上升前缀，并且加上答案。然后从最后一个元素开始遍历，直到出现非下降元素就终止，每遍历一个元素，就找出最大的前缀满足连接处的大小关系，然后再叠加答案。

160.相交链表，这道题用的是哈希表来存储链表的节点，我们先遍历A链表，将所有节点加入哈希表中，然后再遍历链表B，如果在哈希表中找到了对应值，那么就返回该值，否则返回空指针。

206.反转链表，本题考察的是链表的基本性质，在反转操作时，我们可以看作是将当前节点的后继节点改为前驱节点，遍历一次即可完成。每次我们需要先记录后继节点，然后再把后继改为前驱，再更新前驱为当前节点，再将当前节点往前。这个操作就相当于先确定最后一个节点，然后依次往前确定节点。

2024.7.12

每日一题

2974.最小数字游戏，这道题是一个简单模拟题，我们只需要根据题意完成即可，题目的意思是每次从数组中选出最小的两个元素，然后先放入第二小的，再放最小的，所以我们只需要先对数组排序，然后再依次取出两个元素放进去即可。

457.环形数组是否存在循环，这道题是一个考察快慢指针的题目，将数组中的n个点看作图中的n个节点，再将i+nums[i]看作每个节点延伸出去的单向边，所以现在题目变成判断有无环路的题目，这时我们就可以遍历数组，初始化快慢指针，快指针在慢指针前面一步，然后每次快指针走两步，慢指针走一步，直到他们相遇。我用的并不是这种方法，而是通过一直根据规则往前遍历来寻找，其实是一个暴力做法，但是可以根据题目条件进行剪枝，首先题目说了满足条件的数组元素要么全正要么全负，那么我们可以标记第一个元素的正负，如果后面出现符号不同的元素就直接退出。还需要标记一个已经走的步数，最后判断答案时，步数需要大于1才是有效的答案，并且在走的过程中，需要设置步数大于一定值自动退出，否则会出现runtime error.

42.接雨水，这道题是一个经典的动态规划问题，根据题意可以有很多种解题方法，可以按行也可以按列来求解，这里我们选用的是按列来求解。 每一列能接到的雨水取决于左右两侧的高度最大值的更小值和自身的高度，所以我们从前往后和从后往前遍历两次数组，分别处理出每列的左边最大值和右边最大值。然后我们再遍历数组加上答案即可。注意最大值数组需要初始化第一个和最后一个，更新最大值公式应该是用前一个值来更新，因为当前还没有数值。

2024.7.13

每日一题

3011.判断一个数组是否可以变为有序，这道题是一个简单的排序模拟题，首先我们需要写一个函数来判断一个十进制数在二进制下1的个数，我们用的方法是，每次将最小的1删除并且计数加1，具体做法是每次用x&x-1.r然后我们做一个排序模拟，遍历数组，如果该元素比右边元素大，那么我们就要先判断它们1的个数是否相同，不相同直接输出false，否则交换位置。但是遍历一遍不够，所以我们就遍历n次。

94.二叉树的中序遍历，这道题是一个简单的栈辅助遍历的题目，我们首先需要初始化一个答案数组和栈来辅助。然后根据中序遍历的意思，只要当前节点不为空或者栈不为空，就说明还有节点未遍历，我们就一直将root节点移动到它的左节点，直到变为空指针，这时候我们就可以将栈顶弹出，将该值加入答案数组，然后访问右节点，这样就实现了永远优先访问左节点，直到为空指针再访问中节点，再访问右节点，而当出现右节点也为空指针时，就会继续弹出栈顶的节点，继续向上遍历。栈里面只存放了所有左节点，而右节点需要手动遍历。

2024.7.14

每日一题

807.保持城市天际线，这是一道简单的矩阵和数学问题，题目的意思是增加那些高度较小的建筑，不影响四面的视图，所以我们很快就能明白限制的因素是该建筑所在行和所在列的最大值，取它们两者之间的更小值减去原始高度即为所求。刚开始看到这道题时，还以为需要预处理出四个面的结果，但是仔细一想发现，左右和上下的视图是相同的，所以只需要处理两个面的结果就可以，即每行和每列的最大值。

9.回文数，这道题一看就想到将数字转为字符串，然后每次判断头尾两个字母，不断向中间遍历，直到遍历完毕。但是题目要求不让用转为字符串这个方法，所以我们想到用数学的方法来解决，刚开始可能会考虑用每次除10和模10的方法来判断，但是这个太麻烦了，每步都要判断，所以我们考虑整体操作后再判断。可以把整个数字反转然后判断与原数字是否相同，但是这个可能会出现范围过大的问题，所以我们可以考虑只反转一半的数字，如果与剩下一半相同，那么就是回文数。先处理特殊情况，当数字小于0或者个位是0时肯定不满足，然后就通过一个变量每次自身乘上10，再加上原数字模10，原数字每次除10，直到大小关系反转再判断它们是否相等或者刚好相差10倍。

226.翻转二叉树，这道题是一道典型的递归题目，我们需要先翻转叶子节点，然后再整体把整个左右子树调换，所以需要从最下层开始翻转，符合递归的条件。

2024.7.15

每日一题

721.账户合并，这道题考察了并查集和哈希表的知识，本质上是判断哪些邮箱地址属于同一个人，需要用两个哈希表分别记录每个邮箱的编号和每个邮箱对应的名称，然后用并查集将每个账户的邮箱进行合并，题目要求输出地址按照ASCLL顺序，可以直接用sort.

100.相同的树，这道题考察的是树的遍历相关知识，可以选择用深搜或者广搜，这里选择用递归也就是深搜的方法。深搜的一般模板就是先写出特殊情况或者终止退出的条件，然后再继续调用函数本身，在这道题中，特殊情况有几种，首先是pq均为空，pq有一个为空，和pq的值不相同。如果都不是这三情况，那么就继续递归调用，返回的是左子树情况和右子树情况的与。

101.对称二叉树，这道题考察的是树的相关遍历知识，包含递归和搜索。可以考虑迭代的思想，用一个队列来存储需要判断的节点，刚开始存储的是根节点的左右节点，每次从队列中取出两个节点，然后先判断特殊情况，空指针和值不相等的问题。然后分别将两个节点的四个子节点放入队列中，注意对应关系，因为是镜像对称，所以应该是左的右对应右的左。 也可以使用递归的方法，写一个check函数，先判断特殊情况，即两个节点都为空或只有一个为空时。然后再返回递归结果，同时判断两个节点的值是否相等且两个节点的四个子节点是否为镜像对称，依次将左左右右，和左右右左放入函数判断。

112.路经总和，这道题考察了深搜和广搜在树上的应用，我们使用递归解决本题。对于一个节点，只要左节点往下走或者右节点往下走有一条路是成功的，那么就返回true，所以递归的思路就明确了，还需要再写出结束条件，如果节点为空，那么就返回false,如果节点左右节点均为空，则需要判断当前节点值和剩下的目标值是否相等，递归的时候我们就是用当前root的左右节点两种情况来判断，而且目标值每次需要减去当前节点的值，这个是关键。

2024.7.16

每日一题 2956.找到两个数组公共的公共元素，这道题是一个哈希表的简单题目，根据题意，我们需要统计的是每个数组在另外一个数组中也存在的元素个数，所以我们建立两个哈希表，分别统计两个数组中出现的元素的情况，数据范围很小，这里选用数组模拟哈希表或者用STL的哈希表都可以完成，统计完之后再分别遍历两个数组找出答案即可。

2024.7.19

每日一题

3096.得到更多分数的最少关卡数目，这道题是一个考察前缀和的题目，根据题意我们需要先把数组的0转为-1，然后计算两个部分的数组和，所以我们可以现预处理出前缀和数组，然后枚举每个点作为切分点，除了最后一个点，然后判断是否符合条件，否则输出-1.

124.二叉树中的最大路径和，这是一道考察递归的题目，从根节点出发，类似于dfs，分别递归寻找左右节点的路径和，直到叶子节点再返回，从叶子节点往上更新以每个节点为根节点的最大路径，直到返回根节点，用一个变量来维护答案.

543.二叉树的直径，这道题是一道考察递归的题目，按照树的一般算法，维护一个最大直径答案值，定义一个递归函数，开头是递归返回条件，即当前节点为空节点就返回0，否则分别往左和往右递归，维护每个节点的最大深度为左右最大深度中的最大值再加一，答案用左右节点的最大深度的和再加一来维护.

2024.7.28

每日一题

699.掉落的方块，这道题最优解应该是用线段树的方法来解决，这里只给出最暴力的枚举解法。遍历原数组，每次记录左右两个端点的值，并且记录当前的高度。根据重叠的情况分析，如果方块出现重叠，那么当前高度至少为它们的和，所以每次取最大值即可。

102.二叉树的层序遍历，这道题用的是广度优先搜索算法，用一个二元组来表示状态，表示每个节点和它所在的层数。步骤如下，当前根节点入队，当队列不为空时，求当前队列的长度s，依次从队列中取s个元素进行拓展，然后进行下一次迭代。

560.和为k的子数组，这道题考察的是前缀和的知识，但是如果我们直接用枚举前缀和相减来求解，时间复杂度就会很高，所以我们考虑用哈希表来辅助求解。首先我们需要先预处理出前缀和数组，根据前缀和的性质，我们需要在原来的数组长度上加一，储存第一位为0，方便后续的计算。然后我们开一个哈希映射map，用来储存对应的值出现的次数。从零开始枚举遍历前缀和数组，对于每个元素我们都要判断哈希表中是否存在K减去当前元素的值，如果有，那么就加上对应的次数，如果没有，就不更新答案，无论是否出现，我们都需要在哈希表中令当前前缀和元素对应的次数加1。按顺序遍历数组即可完成本题。

215.数组中的第k个最大元素，这道题考察的是数组排序，由快速排序改进算法，还有堆排序，这里使用的是堆排序思想。首先建立一个大根堆，做k-1次删除操作之后，堆顶元素就是要求的答案。首先定义一个转化为大根堆的函数，每次从最后一个非叶节点开始向上遍历，判断当前节点和左右节点的大小关系来建立大根堆，然后再更新当前索引，即递归的思想，每次以当前节点为根节点往下交换节点，maxHeapify函数的作用是将当前节点作为根节点实现大根堆，buildMaxHeap函数的作用是建立初始大根堆，从数组大小的一半作为索引开始往上建立。先建立初始大根堆，然后循环n-k+1次，每次先把堆顶和堆尾节点交换，然后数组大小减一，代表把堆尾元素删除，即原来的堆顶元素，然后继续建立新的大根堆，直到取出第k大的元素。

2024.7.29

每日一题

682.棒球比赛，这道题是一道简单的模拟题，用栈模拟题中的四个操作就可以了，操作一是将x加到列表末尾，操作二是将列表的后两项之和加到列表末尾，操作三是把列表最后一项的两倍加到列表末尾，操作四是去掉列表最后一项。

LCR 100.三角形最小路径和，这道题是一道入门的动态规划题目，当然也可以用dfs来求解。我们只需要用一个数组来记录到达每个点需要的最小路径，然后再把最后一行取一个最小值即可。

2024.8.23

每日一题

198.打家劫舍，这道题是一道简单的入门动态规划问题，根据题目意思，我们不能取数组中相邻的元素然后还必须满足总结果最大，所以我们可以维护一个数组，用来保存在数组每个位置之前能取到的最大值，然后最后输出第n-1个元素的值即为答案。 转移公式如下: dp[i]=max(dp[i-2]+nums[i],dp[i-1]);

279.完全平方数，这道题考察的是动态规划的知识，依题意得，我们需要找到最少的平方数之和使得等于要求的数，我们首先会想到用离该数最近的完全平方数来考虑，但是这样不方便枚举和遍历，所以我们采用动态规划的一般方法，先处理前面的数，再遍历到后面的数。本题需要维护一个到当前位置需要最少完全平方数的数组，然后开始从1遍历到n,这期间需要枚举所有小于i的完全平方数用来找到最小的答案，每次循环起点将dp[i]设置为i，因为这是最多的情况，然后依次比较取最小值，转移方程如下: dp[i]=min(dp[i],dp[i-j*j]+1);

322.零钱兑换，这道题是考察动态规划的知识，本题也是仿照一般的动态规划的状态转移的思想来完成。首先我们需要维护一个数组表示达到每个金额需要的最少硬币数目，然后遍历求值，第一个状态为金额，从1遍历到n，第二个状态是用的硬币种类，从0遍历到数组末尾，如果当前金额一直低于硬币面额就继续，否则就更新当前所需数目最小值，最后输出所需金额的数目： dp[i]=min(dp[i],dp[i-coins[j]]+1);

2024.8.24

每日一题

3146.两个字符串的排列差，这道题是一道简单的模拟题，考察的是哈希表的知识，题目给出了两个字符串，我们只需要先将第一个字符串的对应字符和下标存到哈希表中，再遍历第二个字符串，依次累加位置的差的绝对值即可。

239.滑动窗口的最大值，这道题考察的是滑动窗口和队列的知识，刚开始看错题目了，求成了滑动窗口可能出现的最大值和出现最大值的滑动窗口内容，但题目要求的是滑动窗口每次滑动中内部的最大元素。可以考虑采用优先队列(大根堆)和单调队列(双端队列)的算法来解决。这里用的是单调队列的方法，即可以实现两端的加入和退出队列。用一个双端队列来记录未退出的最大值的下标，每次加入一个元素时，都依次对比队列中下标所对应的元素，如果把小于当前元素所对应的下标全部弹出队列，再将当前的元素下标加入。之后还需要对队列前端的元素进行检验，如果该元素下标不在当前滑动窗口的范围之内，那么就从前面弹出该元素。完成这两个步骤之后，队列的最前面的元素对应原数组的元素即为所求，依次遍历到数组末尾即可。

300.最长递增子序列，这是一道非常经典的动态规划题目，一样是从前往后遍历更新状态，我们需要用一个数组来维护以每个元素结尾的最长上升子序列，结果最小是1，双循环遍历每个元素，如果在每个元素前找到比自己小的，那么就更新一次答案，最终答案为以每个元素为结尾的最长递增子序列中的最大值。

2024.8.31

每日一题

3127.构造相同颜色的正方形，这是一道简单的模拟题，我们只需要遍历所有2*2的矩阵，统计里面某个字符的个数，如果不等于2，那么就证明可以符合题目的条件，因为1，0，3，4，均可以通过不改变和改变一次来实现。

LCR 194.二叉树的最近公共祖先，这道题是一个经典的递归题目，一共需要考虑如下几种情况，当前节点是空节点或者当前节点是p或q，则返回当前节点，若左右子树都找到，则返回当前节点，若只有左子树找到，则返回递归左子树的结果，若只有右子树找到，则返回递归右子树的结果，若左右子树都没有找到，则返回空节点。

2024.9.1

每日一题

1450.在既定时间做作业的学生人数，这是一道简单的模拟题，我们只需要判断每个学生的作业时间是否包含询问时间即可，具体判断方法为开始时间小于等于访问时间，结束时间大于等于访问时间。

49.字母异位词分组，这道题是一个考察哈希表的题目，我们需要统计每一个单词中字母的出现情况，并且将字母情况相同的放在同一个组合里。这里我们利用了c++20的新特性，ranges::sort,这个表示将字符串按指定规则排序，我们对每一个字符串先生成一个副本然后进行排序，如果排序后的结果相同我们就放到同一个vector里面。最后输出时需要新建一个数组，将原来哈希表的值全部加进数组里面再输出。

128.最长连续序列，这道题考察的是哈希表和数组的相关知识。对于题目给出的未排序的数组，可能出现重复的情况，所以我们首先需要将数组中的元素都放进一个哈希集合里面来去重。然后对于哈希集合里面的每一个数，我们需要判断两种情况，第一种是这个数可以作为序列的开头，第二种是不能作为序列的开头，判断标准为这个数-1是否存在。如果可以作为序列的开头，那么以这个数为当前数，不断地寻找比这个数大1的数是否存在，如果存在就继续遍历，并且维护一个以当前数为开头的序列长度。当无法继续遍历的时候，更新答案的最长序列。

56.合并区间，这道题考察的是数组和排序的相关知识，根据题意，我们需要将区间重合的数组先合并再插入到答案数组中，那么我们自然想到，当数组中的元素左端点越小时，越有可能被合并，所以我们先按左端点排序。然后遍历每一个时间区间，第一个直接加入，然后对于后续每一个我们需要判断答案数组最后一个区间的右端点是否大于等于新区间的左端点，如果符合那么就更新答案数组的最后一个元素的右端点为新元素的右端点，代表区间被延长了。反之，如果没有包含，那么就直接将新区间加入到答案数组中。

周赛

Q1.检查棋盘方格颜色是否相同，这道题是一个简单的数学题，我们可以观察出，当棋盘行和列的奇偶性相同时，则为黑色， 否则为白色，那么我们就可以通过两个坐标来判断奇偶性了，字符要先转为ascll码。

2024.9.2

每日一题

2024.考试的最大困扰度，这道题考察的是滑动窗口的知识，我们不断向前枚举右端点，遇到不符合的字符就转换次数+1，当超过了k值之后就不断向前移动左端点，直到小于等于k，然后每次右端点向前都需要更新最大值，注意一共有tf两种情况，所以应该取两者中的最大值。

面试题

快速排序:参考分治的思想，每次找一个基准值，这里找的是arr[low]，每次从右往左找到第一个比基准值小的数，判断下标是否符合条件，是就交换;再从左往右找到第一个比基准值大的数，判断下标，符合就交换，否则不变;当i和j重合时，代表基准值不用再移动了。

2024.9.3

每日一题

2708.一个小组的最大实力值，这道题考察的是序列和数组相关的数学问题，从左往右遍历数组，考虑每个元素是否选择，如果不选，那么当前的最大实力值就是前面所有元素的乘积，如果选了，要么元素单独一个数，或者于前面所选的所有数相乘。所以本题的关键是维护一个最小乘积和最大乘积。

73.矩阵置零，这道题是一道矩阵有关标记和哈希的题目，题目的意思是当遇到一个元素为0时，我们需要把整行整列都变为0，如果在遍历的时候每个单独操作会造成非常复杂的计算量，所以我们的方法是先进行标记，先遍历一次矩阵，用两个数组分别代表行和列，将出现0的位置先进行标记，然后进行第二次遍历矩阵，每次判断相应的行和列数组是否标记过，如果标记了，那么就把它变成0.

54.螺旋矩阵，这道题是矩阵相关，我们可以按行列来模拟输出，每次遇到边界值或者访问过的就换方向，也可以按层来输出，从最外层到最内层来输出。也可以写四个方向的循环遍历输出，每输出一次就更新对应的参数。

48.旋转图像，这道题是对纯数学知识的考察，我们只需要推导出顺时针旋转90度之后的坐标变换公式即可，中间我们需要一个临时变量来存储有关的坐标。

234.回文链表，这道题考察的是链表的相关知识包括递归，我们需要写一个递归函数，令节点先找到指向尾节点，再往前判断，每次需要判断两个条件，第一个是当前链表往外的区域是否是回文的，第二个是当前节点的值和前面的节点的值是否相等，如果符合条件，那么将前面的节点往后一位然后再继续递归，直到递归完毕。

142.环形链表 Ⅱ，这道题考察的是链表和快慢指针的知识，这道题是Ⅰ的升级版，因为要输出入环的第一个节点。快慢指针即慢指针一次走一步，快指针一次走两步，当它们相遇的时候，证明有环，但是有个细节，即快指针每次走的时候，需要先判断下一步是否为空。根据快指针走的路程是慢指针的两倍以及一系列的数学推导可知，我们只需要新建一个头节点的副本，每次这个节点往前走一步，同时慢指针也往前走一步，当它们两个节点相遇的时候，该节点即为入环点。

2024.9.4

每日一题

2860.让所有学生保持开心的分组方法数，这是一道考察数学和排序相关的题目，当选择学生人数固定的时候，选择方案是唯一的。

110.平衡二叉树，平衡二叉树的定义是树的所有节点的左右子树的深度相差不超过1，所以判断的标准是要求出节点的高度。用一个自顶向下的方法求节点的深度，即左右子树中的更大值+1。最后主函数中需要判断的条件是左右子树的深度是否最大深度相差不超过1并且左右子树是否都满足条件，这个即是递归的条件。

LCR 145.判断对称二叉树，需要写一个判断两个子树是否对称的函数，如果两个节点其中一个为空，那就不是，两个都为空，就是。否则就返回两对子节点的检查情况。主函数只需要返回根节点的左右子树判断情况即可。

2024.9.5

每日一题

3174.清除数字，这是一道简单的模拟题，我们只需要用一个空字符串来模拟即可，如果遇到字母就放入新字符串，如果遇到数字就弹出一个。

108.将有序数组转换为平衡二叉搜索树，中序遍历，总是选择中间位置左边的数字作为根节点，以升序序列中的任一个元素作为根节点，以该元素左边的升序序列构建左子树，右边的升序序列构建为右子树，这样就能得到二叉搜索树了。

2024.9.6

每日一题

3176.求出最长好子序列Ⅰ，这道题考察的是动态规划的知识，记录以第i个元素为结尾，同时子数组中有j个元素不符合条件的情况，枚举数组长度和不满足条件的个数，每次枚举之后取最大值。

24.两两交换链表中的节点，这道题考察的是链表和递归，递归的终止条件是链表中没有节点或者链表中只有一个节点，若链表中有两个以上节点，那么就按顺序两两交换顺序。

98.验证二叉搜索树，这道题考察的是递归，二叉搜索树的定义是，左子树节点比当前节点值小，右子树节点比当前节点值大。所以我们需要写一个递归函数来判断，判断一个节点的值是否在一个区间内，左子树无下限，上限为根节点，右子树无上限，下限为根节点。

230.二叉搜索树中第k小的元素，这道题考察的是二叉搜索树的性质，因为节点的左子树只包含小于当前节点的数，右子树只包含大于当前节点的树，所以二叉搜索树的中序遍历是按照升序来遍历的，我们只需要做一次中序遍历找到第k个元素即可。

2024.10.8

每日一题

1436.旅行终点站，这道题是一道简单的哈希表的题目，我们只需要遍历一次数组，将所有出发的城市标记，然后再遍历一次数组，每次检查到达的城市是否被标记过，如果被标记过，证明能出发，如果没有，则为我们所求。