JZX 轻语

LeetCode 724 - 寻找数组的中心索引

比较简单的前缀和题目，但有个优化点值得记录下。该题目可以套用前缀和模板做法，即计算双侧前缀和，先记录一遍前缀和，然后再反向遍历一遍数组，如果当前前缀和和后缀和相等，则返回当前索引即可。但是这样的时间复杂度是O(n)。有一个更好的做法，可以在前缀和计算的过程中直接判断是否满足条件，这样可以减少空间开销。具体做法是，先计算出数组的总和total，然后遍历数组，如果当前前缀和prefix(不包括当...

Posted by Jeza Chen on July 8, 2024

LeetCode 1958 - 检查操作是否合法

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

直接枚举八个方向，如果有一个方向满足要求，直接返回True即可。如何判断是否满足要求呢？先记目标颜色color为A，相反颜色为B，我们需要在至少一种方向的路径上满足AB..BA格式。从落点(rMove, cMove)出发，枚举八个方向，沿着方向一路检查，如果走出边界或者遇到空格，说明无法构成AB..BA的格式，不满足要求；如果遇到相反颜色，则判断B的个数是否大于等于1，如果是，则满足要求。 ...

Posted by Jeza Chen on July 7, 2024

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

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

从左往右遍历字符串，使用一个栈来维护已遍历字符的连续计数，如果当前字符与栈顶字符相同，则将计数加一，否则将当前字符入栈，并将栈顶计数计为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 724 - 寻找数组的中心索引

LeetCode 1958 - 检查操作是否合法

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

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

LeetCode 3101 - 交替子数组计数

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

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

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

LeetCode 1177 - 构建回文串检测

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

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04