JZX 轻语

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

结合多种情况的解法，涉及到最大前缀和、最大后缀和以及最大子数组和。由于数组允许重复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 1144 - 递减元素使数组呈锯齿状

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

一开始想复杂了，其实只能递减元素。分情况讨论即可：对于arr[0] < arr[1] > arr[2] < ...这种情况，只能递减arr[1], arr[3], arr[2k + 1]，每个元素的只需要递减到两侧元素最小者 - 1即可，累加这些元素的最少递减次数；对于另一种情况，继续上文的步骤，最后取两种情况的最小值即可。 class Solution: d...

Posted by Jeza Chen on June 24, 2024

LeetCode 520 - 检测大写字母

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

比较简单的题目，但看了下以前的做法比较复杂。其实最简单的做法是先统计大写字母的个数，然后判断是否全大写(大写字母个数为字符串长度)或者全小写（大写字母个数为0），或者只有首字母大写（大写字母个数为1，且是首字母大写）。 class Solution: def detectCapitalUse(self, word: str) -> bool: capita...

Posted by Jeza Chen on June 23, 2024

LeetCode 1140 - 石子游戏II

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

零和博弈中极小化极大算法的应用。我们寻求的是Alice的最大优势分数，可以将其作为递归函数的返回值，然后通过记忆化搜索来优化递归过程。在Alice层的递归中，我们尽可能的让Alice的分数最大化，而在Bob层的递归中，我们尽可能的让Alice的分数最小化。这样，我们就可以得到Alice至少能获得的分数(即如果双方都采取最优的策略，Alice的分数)。 from functools im...

Posted by Jeza Chen on June 23, 2024

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

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

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

LeetCode 1177 - 构建回文串检测

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

LeetCode 503 - 下一个更大元素II

LeetCode 1145 - 二叉树着色游戏

LeetCode 1144 - 递减元素使数组呈锯齿状

LeetCode 520 - 检测大写字母

LeetCode 1140 - 石子游戏II

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04