JZX 轻语

LeetCode 1209 - 删除字符串中的所有相邻重复项II

从左往右遍历字符串，使用一个栈来维护已遍历字符的连续计数，如果当前字符与栈顶字符相同，则将计数加一，否则将当前字符入栈，并将栈顶计数计为1。如果栈顶字符计数超过了k，则需要出栈。最后拼接栈中尚存的字符即可。 class Solution: def removeDuplicates(self, s: str, k: int) -> str: stack = ...

Posted by Jeza Chen on July 7, 2024

LeetCode 1202 - 交换字符串中的元素

Flash 此文章属于Flash闪念部分的短文

一开始没啥思路，以为是贪心算法之类的。后面想了下可以用图来建模，将字符串的index视作为节点，如果某两个位置的字符可以交换，则将这两个位置的节点连接起来(如果a和b可以交换，b和c可以交换，则a和c可以交换，具有传递性，这和连通分量的特性一致)。由于连通分量里面对应的字符可通过交换排成任意的次序，因此，对于每个连通分量，将其内部的字符排序后，再按照index从小到大的顺序填回去即可。连通分...

Posted by Jeza Chen on July 7, 2024

LeetCode 3101 - 交替子数组计数

Flash 此文章属于Flash闪念部分的短文

比较简单的动态规划题目，使用dp[i]表示以A[i]结尾的交替子数组的个数，那么状态转移方程为dp[i] = dp[i - 1] + 1 if A[i] != A[i - 1] else 1。最后的结果累加dp数组即可。 class Solution: def countAlternatingSubarrays(self, nums: List[int]) -> int:...

Posted by Jeza Chen on July 6, 2024

LeetCode 1191 - K次串联后最大子数组之和

Flash 此文章属于Flash闪念部分的短文

结合多种情况的解法，涉及到最大前缀和、最大后缀和以及最大子数组和。由于数组允许重复k次，需要考虑前后拼接的情况。结果取自以下几种情况的最大值： (如果k > 2) 最大前缀和 + 最大后缀和 + (k - 2) * 数组和 – 第一个数组的最大后缀 + 中间的k - 2个数组 + 最后一个数组的最大前缀 (如果k > 2) 最大前缀和 + 最...

Posted by Jeza Chen on July 5, 2024

LeetCode 1190 - 反转每对括号间的子串

Flash 此文章属于Flash闪念部分的短文

本质就是将括号里面的字符串反转，由于括号支持嵌套的，即可能会有多次的翻转操作。直观的做法就是先将最里层的括号里面的字符串反转，然后再将外层的括号里面的字符串反转，以此类推。可以使用一个数组来维护上述的层次信息：如果遇到左括号，则说明有新的层次，新建一层推入到数组中；如果遇到字符，则将字符加入到最顶层的字符串中；如果遇到右括号，意味着层次结束，则将当前层的字符串反转后加入到上一层的字符串中，并...

Posted by Jeza Chen on July 5, 2024

LeetCode 1186 - 删除一次得到子数组最大和

Flash 此文章属于Flash闪念部分的短文

最大和子数组的变种题目，新增了一个允许删除一个元素的条件。对于最大和子数组，其中以第i个元素结尾的子数组最大和为dp[i] = max(dp[i-1] + nums[i], nums[i])。对于本题，我们可以使用二维n * 2的dp数组，其中dp[i][0]和dp[i][1]分别表示以第i个元素结尾的非空子数组，不删除元素和删除一个元素的情况下的最大和。对于不删除元素的情况，dp[i][0...

Posted by Jeza Chen on July 5, 2024

LeetCode 1177 - 构建回文串检测

Flash 此文章属于Flash闪念部分的短文

一开始理解错题目了，题目原意是可以打乱子数组的。因此，我们仅需统计子数组内各个字符出现的次数。如果字符串是回文的，则最多只有一个字符的出现次数为奇数。此类的区间查询题目可使用前缀和的方式解决，维护前缀各个字符出现的次数，通过相减快速计算任意子数组内各字符出现的次数。该题目有两个关注点：1. 字符串是否回文仅关注每个字符出现次数的奇偶性，我们可以将前缀的字符计数信息压缩为一个整数，通过位异或运...

Posted by Jeza Chen on July 5, 2024

LeetCode 2065 - 最大化一张图中的路径价值

Flash 此文章属于Flash闪念部分的短文

Hard难度题目，但解法相对简单一些。可以使用DFS回溯，暴力枚举所有可能的有效路径即可，记录路径所经过节点的值之和(重复经过节点只累加一次)，取其中的最大值即可。所谓的有效路径，是指能在剩余的时间内回到起始节点。因此，我们需要事先使用Dijkstra算法求出起始节点到其他节点的最少时间，以便在DFS回溯过程中判断是否能回到起始节点。 from functools import lru...

Posted by Jeza Chen on July 1, 2024

LeetCode 503 - 下一个更大元素II

Flash 此文章属于Flash闪念部分的短文

单调栈模板题，差异点在于循环数组。我们可以将数组复制一份，然后将其拼接到原数组的后面，这样就可以将循环数组转化为普通数组。然后按照单调栈的模板进行处理即可。 class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: ans = [-1] * len(nums) ...

Posted by Jeza Chen on June 24, 2024

LeetCode 1145 - 二叉树着色游戏

Flash 此文章属于Flash闪念部分的短文

该题目要求的是作为第二个选手，如何选择起始节点，使得必得节点数大于对手(该游戏为零和博弈，因此需要大于节点总数/2)。所谓得必得节点是指对手无法选择的节点。由题意不难推断，选手2的起始节点最优解在选手1的起始节点的父节点、左孩子或右孩子之中(可从源头尽可能阻断对手的选择)。当然为了递归的简洁，我们也可以通过后序遍历计算所有的必得节点数，取其中最大值即可。如何计算子树的必得节点数： ...

Posted by Jeza Chen on June 24, 2024

LeetCode 1209 - 删除字符串中的所有相邻重复项II

LeetCode 1202 - 交换字符串中的元素

LeetCode 3101 - 交替子数组计数

LeetCode 1191 - K次串联后最大子数组之和

LeetCode 1190 - 反转每对括号间的子串

LeetCode 1186 - 删除一次得到子数组最大和

LeetCode 1177 - 构建回文串检测

LeetCode 2065 - 最大化一张图中的路径价值

LeetCode 503 - 下一个更大元素II

LeetCode 1145 - 二叉树着色游戏

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04