Rstln-CSDN博客

原创【前缀合】【二进制状态】个人练习-Leetcode-1371. Find the Longest Substring Containing Vowels in Even Counts

题目链接：https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/description/思路：一开始以为是DP，但这样似乎必须要有一个状态来表示是否取某一位。然而发现，即便如此，如果。表示的是最长长度的话，依然没法确定这个最长长度的子串是怎么样的。表示取最后一个，最大长度也是1。表示不取最后一个，最大长度是。题目大意：给一个字符串。

2025-03-22 23:01:51 159

原创【DFS】个人练习-Leetcode-646. Maximum Length of Pair Chain

刚开始还想着用一个二维数组存区间之间的连接关系，后来发现，如果按照左端点排序的话，那么这些区间有两个特点。但是我们发现，因为最后的区间必然是不可能连接到其他区间的，而其他靠后的区间也更少可能连接到后面的区间，因此实际上如果从后往前遍历的话，所有的。因此，对每个区间，我们首先找到最近的下一个能连接的区间（因为这样才能让串起来的区间最长），存在。都可以正确顺利地求出来，也就不用什么DFS了（或者说相当于从搜索树的底部往上爬）用来存如果当前串接了后续的区间后最长的之后的串长。求能够串起来的区间的最大长度。

2024-11-26 21:38:54 501 1

原创【DP】个人练习-Leetcode-2019. The Score of Students Solving Math Expression

因为每个基础的【可能的部分答案】是从【两个数和一个操作符】得来的，因此遍历时要先把所有长度为3的子串先遍历了，而不是单纯地枚举左右端点。在代码中的体现就是遍历的最外层从。的数学表达式，以及一串学生们给出的答案。对于每个答案如果分数正确，加5分；如果错误，但是是因为搞错加法乘法的顺序的错误答案，加2分；求这串答案的总分数。思路：DP做，将一个表达式从某个operator中间分开，可能的结果就是左边的结果（operator）右边的结果。得到所有可能的结果后，错误答案每个+2，正确答案每个+5即可。

2024-11-22 13:23:40 281

原创【字典树Trie】个人练习-Leetcode-421. Maximum XOR of Two Numbers in an Array

题目链接：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/description/往左子树走代表下一位是0，往右子树走代表下一位是1。不过有趣的是主函数中的遍历，可以把。思路：两两异或必然超时，因为二进制位就是0或1，可以用字典树来存储。去和Trie里的树找对应，得到可能得到的最大值。每一次check操作也是如此，因此复杂度为。时间复杂度的话，插入操作是。存进Trie里，然后用。题目大意：给一个数组。

2024-11-11 13:39:58 379

原创【贪心】【哈希】个人练习-Leetcode-1296. Divide Array in Sets of K Consecutive Numbers

题目链接：https://leetcode.cn/problems/divide-array-in-sets-of-k-consecutive-numbers/description/不过我开始做时，因为要从小到大遍历剩余元素，就用了。虽然通过了，但速度有点慢。看了题解，发现用的是。中，每个最小的元素都需要被归入一个子列中。，这些元素的剩余量都减1即可。思路：比较简单，贪心就行，找到当前剩下的元素中最小的。，然后（如果合法）它必然属于某个子列，那么就找。这也是OK的，因为排序后，个元素的连续的子列。

2024-11-09 14:00:09 338

原创【lambda表达式】【DP】个人练习-Leetcode-1039. Minimum Score Triangulation of Polygon

先想着的是一共有3n-6个数，其中n个数必然是凸多边形的顶点。剩下的2n-6个数是重复一遍的，也就是n-3个数。对一条凸多边形的边i-j来说，最终的最优值就是i-j-k（三角形）+ i-k（凸多边形）+ k-j（凸多边形）。题目链接：https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/description/将其三角化，每个三角形的值是三个顶点值的乘积，一个三角化方法的值是所有三角形的值的和。求三角化方法最低取得的值。

2024-11-08 13:48:14 237

原创【负二进制】个人练习-Leetcode-1073. Adding Two Negabinary Numbers

思路：重要的点是考虑进位是如何做的，因为是负二进制，那么当上一位的和是大于等于2的时候，先%2，然后进位的时候应该进的是-1；而当上一位的和是-1时（考虑两位是0，进位为-1的情况），应该把本位置1，再进位1。剩下的情况就是正常的0和1，直接写入就好。题目链接：https://leetcode.cn/problems/adding-two-negabinary-numbers/description/求两个数组的和，格式与前相同。因为不能有前导0，所以最后需要循环判断一下去掉前导0.

2024-10-26 10:33:46 312

原创【滑动窗口】个人练习-Leetcode-3171. Find Subarray With Bitwise OR Closest to K

思路：按位或只会把二进制上的0变为1，也就是只会增加，因此要固定区间的一个端点，像滑动窗口一样遍历做。从左往右遍历的话，相当于固定区间的右端点。先找出二进制的32个bit位里，在当前范围内，每个bit位最右的位置（在。中位置，bit位）这样的pair进行排序，从大到小（这样排序的原因是：我们希望结果尽可能接近。，找一个子列，使得这个子列区间内的元素的按位或操作后得到的数和。中位置大，靠右）】和【bit位高（数值大）】的先考虑）。中最右位置可能是相同的】，我们需要一个。指针来记录上一个所考虑的最远位置。

2024-10-13 16:23:26 287

原创【线段树】个人练习-Leetcode-3161. Block Placement Queries

思路：一开始时看见题目写的"anywhere"以为是【区间内每处都能放下物品】，寻思着那不是整个区间都没有障碍物才行吗，好像判断有点简单了。区间内，被障碍物隔开的各个区间中，能存储的最大长度。这种涉及区间查询的，应该用线段树来解决。看了很多题解，还是灵神的比较清晰。题目链接：https://leetcode.cn/problems/block-placement-queries/description/插入和查询操作交替进行，返回每次查询的结果。左边的最大的障碍物位置）之间，要么在。来说，要么最大长度在。

2024-10-10 15:57:55 423

原创【差分数组】个人练习-Leetcode-3229. Minimum Operations to Make Array Equal to Target

题目链接：https://leetcode.cn/problems/minimum-operations-to-make-array-equal-to-target/description/考虑到这样一个事实：对于数组的某个区间的统一操作，相当于对于差分数组的两个区间端点做操作。那么只需要找正的元素个数即可，这就是最佳的方案。非最佳的方案对应着的是，在。从全0变为别的样子的时候，也是一对对加减上去的，因此实际上。的某个元素上+1又-1，这样必然会让操作次数增多。的两个端点，一个+1，一个-1。

2024-10-09 18:16:02 324

原创【DP】个人练习-Leetcode-3129. Find All Possible Stable Binary Arrays I

题目链接：https://leetcode.cn/problems/find-all-possible-stable-binary-arrays-i/description/一看题解是DP，昏了。不过看了题解后还是比较清晰的，毕竟重点是搞清楚状态转移方程。在任何时候都是不合法的，因为违背了定义要以。，这是OK的，因为这时上一个数组的结尾是。，那么要排除这种情况：前面已经连续出现了。还回去，找上一个状态。来找，因为上一个数组必然是包含。，必然可以直接转移，全部加上。，因为这时只有1种方法，就是全。

2024-10-09 12:13:12 246

原创【几何】个人练习-Leetcode-1453. Maximum Number of Darts Inside of a Circular Dartboard

思路：几何上，如果一个圆能够覆盖N个点，那么在这N个点中，一定存在两个点，使得这个圆移动一下使得这两个点在圆上后，依然能够覆盖这原来N个点（详细的证明看网站上的题解，感觉还是比较intuitive的）。因此只需要遍历点对，寻找过这两个点，半径为。的圆的圆心，再计算这个圆覆盖的点数，求最大即可。注意两个点一个半径并无法确定圆心，因为这个圆心可能有两个，对称的，在纸上画画就能看出来。于是修改了一下boundary，才通过。题目大意：给出一系列点和一个圆的半径，（寻找一个圆心）求这个半径的圆最多能覆盖多少个点。

2024-09-25 15:45:41 325

原创【前缀和】【异或】【三元组】个人练习-Leetcode- 1442. Count Triplets That Can Form Two Arrays of Equal XOR

题目链接：https://leetcode.cn/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/思路：这题没思路的一个原因可能是对【异或运算的性质】不太熟悉。异或是有结合律和交换律的，因此看到这种【连异或】，可以想到【连加】的类似操作，就是求前缀和。那么很明显这个三元组代表的区间的第一段异或第二段是等于0的。还是将三重循环改为二重循环，都用到了异或的性质。，如果有两个相等的元素（意味着他们会异或为0），那么。

2024-09-25 14:08:22 227

原创【三元组枚举中点】【树状数组】个人练习-Leetcode-1395. Count Number of Teams

看了题解还有用树状数组的写法。树状数组建议看这个视频（https://www.bilibili.com/video/BV1ce411u7qP/）了解下，就能明白三个相关函数。【三元组】中，中间的点总是特殊的，可以考虑枚举中点。，为1表示这个下标的数字出现过，为0表示没出现过。然后对这个桶数组求前缀和得到一个数组，这个数组就是。，找出两边的大于和小于中间点的数量，然后【左小✖️右大 + 左大✖️右小】就是答案。但知道树状数组了，该怎么应用到这个题目呢？，这样就可以知道，在某个位置。的数目，也就是潜在的。

2024-09-09 17:22:03 454

原创个人练习-Leetcode-1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

题目链接：https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/description/但数据结构上自己写的一直很冗杂，主要原因是因为最大值和最小值可以重复，【修改。看了题解才发现用STL的multiset最简单。思路：实际就是保存子列的最大值和最小值，保证差不超过。，求最长的子列，使得数组中任意两个数的差不超过。一直增加，遇到不行的就修改。

2024-08-28 14:06:37 305 1

原创【阶乘】个人练习-Leetcode-LCP 22. 黑白方格画

思路：虽然是简单题，但还想了一会的。因为【最终图案数】并不是【操作方法数】。比如2*2的格子，【先涂一行再涂一列】和【先涂一列再涂一行】得到的图案是一样的。我们发现涂的行列具体是哪几行哪几列并不影响最终黑格子的数目，因此可以先得出【需要涂黑。题目链接：https://leetcode.cn/problems/ccw6C7/description/，每一次操作可以把方格的某一整行或者某一整列涂黑，求使得黑色格子数字为。求阶乘的话可以用一个数组来保存结果，避免重复计算。的【最终图案】的个数。

2024-07-15 13:37:03 318 1

原创【哈希表】个人练习-Leetcode-2025. Maximum Number of Ways to Partition an Array

等于某个值的「位置」的数量】，也就是说，两个哈希表中存的都是“左半边的和”，因为只要【左半边的和=全部和/2】实际上就是【左半边和=右半边和】了。看题解时我其实绕了好久，这里理解的重点是，分清楚【所谓的“左右”是谁的左右】。的左右”已经无关紧要了，因为问题已经转换成了找满足【左半边的和=某个前缀和=全部和/2】的。】来定义两个哈希表的，这两个哈希表代表的“左右”，是【改变的位置。因此题解中的“左右”、两个哈希表所代表的“左右”，都是指改变位置。求改变/不改变后的数组中，能够找到的最大的下标。

2024-07-08 16:22:58 432

原创【大顶堆】个人练习-Leetcode-2170. Minimum Operations to Make the Array Alternating

思路：很明显贪心就行，保留奇数下标元素中，出现次数第一大和第二大的元素及其次数（保留至第二大是因为要满足奇偶下标元素不等）。同样保留偶数下标元素中，出现次数第一大和第二大的元素及其次数。主要还是写起来比较麻烦，刚开始自己维护了个保留第一大和第二大的方法，虽然过了，但看着太丑陋了，就换成了用一个大顶堆来维护的方法。此外，考虑到数组只有一个元素的情况，特殊处理。，要求将其变为alternating数组，即其所有奇数下标的元素相等，所有偶数下标的元素相等，且奇数元素下标的元素不等于偶数下标的元素。

2024-07-07 15:11:20 421

原创【3维BFS】个人练习-Leetcode-LCP 79. 提取咒文

看了题解才知道有一种“3维BFS”的存在。类似于一个魔方，在每一层进行BFS，上面一层满足了条件（找到下一个字母）后才能往下一层转移。转移了并不会终止上一层的BFS，这样就避免了遗漏可能的最小的其他路径。位置开始，可以移动（上下左右）或者提取字母，求组成字符串的最小【移动+提取次数】思路：显然是BFS，然而BFS无法保证结果“最小”。一个例子就是，如果要找。，那么如果在BFS时先按行找，就会陷入陷阱，因为明显按列找才是最短的。并且还学到了新的【上下左右偏移】的写法，只用到一个长为5的一维数组。

2024-07-04 19:52:17 277

原创【哈希表】【字符串】个人练习-Leetcode-1814. Count Nice Pairs in an Array

题目链接：https://leetcode.cn/problems/count-nice-pairs-in-an-array/description/思路：一开始的思路是伪加法，取一个对，从低位开始加。看了题解才发现可以转换原等式为。，如果当前位不想等就返回。题目大意：给出一个数列。的值，这样复杂度就降为。

2024-07-04 13:43:37 1034

原创【遍历链表】个人练习-Leetcode-LCR 029. 循环有序列表的插入

（这个并非真正的头），这个链表从头到尾是非递减的，唯一可能出现递减的地方是【尾部连回头部】处。（3）有一种特殊情况是全链表的元素相同。此时我们无法找到（1）（2）中所谓的【尾部接到头部】处（因为不存在。相同，那么直接插到其后面就行。否则无论是大了还是小了，都得再往后递归。比尾部值大或者比头部值小，都可以直接插在尾部值后。，要求将该值插入链表中，保持非递减性质不变。思路：（1）先考虑正常的从头到尾非递减的情况，如果插入值。（2）如果刚好碰到尾部接头部处，那么如果。的情况了），因此单独做判断。

2024-07-03 22:50:28 387

原创【滑动窗口】个人练习-Leetcode-992. Subarrays with K Different Integers

题目链接：https://leetcode.cn/problems/subarrays-with-k-different-integers/description/刚好就是【新增子列数】，因为新增子列是连续的，并且必然包含。思路：主要是转换题意，可以先求【不同元素最多为。往右移动了，使得不同元素数只会增加或者不变，个】的子列数，两者相减就是【不同元素刚好为。个】的子列数，然后再求【不同元素最多为。可以作为下一轮的新起点，因为下一轮。区间里的不同元素个数刚好为。，求【不同元素刚好为。开始，只要从上一轮的。

2024-07-02 10:58:25 256

原创【字符串处理】【双指针】个人练习-Leetcode-777. Swap Adjacent in LR String

思路：操作中可以看出，这只不过是让L和X或R和X交换位置而已，L、R的相对位置不会变。因此先把所有X去掉，看看只剩下LR的两个字符串是否一致。题目链接：https://leetcode.cn/problems/swap-adjacent-in-lr-string/description/我原本以为这就到头了，但没想到还没过，看了题解才发现，这个交换中，只能右移】这个条件。这个步骤用双指针完成即可。中，相对位置对应的每个L和R，是否满足【只能右移，因此还要对比一下。，返回是否存在方法使得。

2024-07-01 21:00:35 300

原创【贪心】【哈希表】个人练习-Leetcode-846. Hand of Straights

做完一下就通过了，但时间不是很理想。于是改了一下，每轮找【残存次数大于0的最小的数】的下标可以复用，直接从上一轮的继承就行了。题目链接：https://leetcode.cn/problems/hand-of-straights/思路：因为题目的限制很死，如果能够分那么分的结果一定是确定的。然后从小到大遍历，每轮从【残存次数大于0的最小的数】开始（可以用一个。题目大意：给出一数列，求是否能刚好将它们分成若干组，每组的元素数量为。先排序，并记录每种元素出现的次数，用哈希表。一样的效果），然后往后。

2024-06-29 23:22:04 331

原创【BFS】【并查集】个人练习-Leetcode-815. Bus Routes

BFS

2024-06-28 19:47:43 403

原创【贪心】个人练习-Leetcode-2271. Maximum White Tiles Covered by a Carpet

然后遍历，考虑毯子覆盖每片连续瓷砖的右端点的情况。实际上我和题解想法是一样的，没想到题目的时间瓶颈其实并不在贪心…思路：贪心做，从左往右遍历的话，必然是将毯子的右端放在某片连续的瓷砖的右端点是最优的，因为如果再往右，只会碰到空的，瓷砖数。片连续瓷砖的右端），用二分法找到第一个右端点大于【毯子的左端点】的连续瓷砖片。，每个元素代表这个区间被瓷砖覆盖（左右都是闭合的）。来表示当前能覆盖的连续瓷砖块的和（只覆盖到一部分也算）。我的做法是，在遍历的每一轮时（毯子盖在。，求这块毯子能覆盖的最大瓷砖数。

2024-06-27 15:48:57 549