JZX 轻语

LeetCode 503 - 下一个更大元素II

单调栈模板题，差异点在于循环数组。我们可以将数组复制一份，然后将其拼接到原数组的后面，这样就可以将循环数组转化为普通数组。然后按照单调栈的模板进行处理即可。 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 2786 - 访问数组中的位置使分数最大

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

此类单向转移+寻找分数最大化的问题可以考虑使用动态规划做法。最朴素的dp是定义dp[i]为转移到第i个元素的最大分数，其中dp[i] = max(dp[j] + nums[i] - (x if nums[i] % 2 != nums[j] % 2 else 0))，j < i，这样需要双重循环，需要考虑优化：仅使用两个变量odd_max和even_max表示已遍历的数组元素中，转移到奇...

Posted by Jeza Chen on June 14, 2024

LeetCode 1109 - 航班预订统计

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

今天做的第二道差分数组题，上一道是1094-拼车，本质做法和上一道是一样的，只不过这道题左右都是闭区间。最后通过累加就地恢复为原数组即可。 class Solution: def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]: diff = [0] * n ...

Posted by Jeza Chen on June 14, 2024

LeetCode 1105 - 填充书架

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

放置/分类且求某最小值的题目，可以考虑动态规划。本题中使用dp[i]表示放置前i本书所需的最小高度。在遍历书i时，需要考虑最后一层 + 前面层的最小值，可以遍历书i放在最后一层的所有可能情况，计算当前情况的总高度(最后一层高度+前面层次的高度，后者可以直接取上一层最后一本书的dp结果)，取其中的最优解(因此就满足了最优子结构)。状态转移方程为dp[i] = min(dp[j] + line_...

Posted by Jeza Chen on June 14, 2024

LeetCode 1104 - 二叉树寻路

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

本质就是完全二叉树寻父节点计算方法(该计算在二叉堆里经常使用到，即，如果节点从1开始计数，则节点i的父节点为i // 2)的变体，只是这里的完全二叉树中，层次(从1开始计数)为偶数时，需要左右翻转过来编号。因此，可以先计算出当前节点的层次，然后根据层次的奇偶性，计算出当前节点的原始编号，再按原始的计算方法，根据原始编号计算出父节点的原始编号，然后再翻转回来即可，一直迭代到根节点即可。由于是镜...

Posted by Jeza Chen on June 14, 2024

LeetCode 1094 - 拼车

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

一开始以为这种区间查询和更新问题需要使用线段树or树状数组的结构，没想到可以利用前缀和的逆形式 - 差分数组来解决，差分数组本质也是个前缀和，但区别在于其维护的是元素间的差值，而不是元素本身。这样，对于区间[l, r]的更新操作add(l, r, val)可以转化为diff[l] += val和diff[r + 1] -= val，而每个元素本身的值可以累加前面的差分值得到。这样，对于add...

Posted by Jeza Chen on June 14, 2024

LeetCode 503 - 下一个更大元素II

LeetCode 1145 - 二叉树着色游戏

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

LeetCode 520 - 检测大写字母

LeetCode 1140 - 石子游戏II

LeetCode 2786 - 访问数组中的位置使分数最大

LeetCode 1109 - 航班预订统计

LeetCode 1105 - 填充书架

LeetCode 1104 - 二叉树寻路

LeetCode 1094 - 拼车

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04