JZX 轻语

挖掘时光的细节

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 419 - 甲板上的战舰

Flash 此文章属于Flash闪念部分的短文
本来想通过DFS这些方法来扫描的，后面发现只要枚举每个战舰的起点即可：只要某个’X’的左边和上边都不是’X’，那么这个’X’就是一个战舰的起点。 class Solution: def countBattleships(self, board: List[List[str]]) -> int: ans = 0 for i in range...

Posted by Jeza Chen on June 11, 2024

LeetCode 1061 - 按列翻转得到最大值等行数

Flash 此文章属于Flash闪念部分的短文
不妨取个例子：如果通过多次列翻转后，数组[0, 0, 1]变为全0或者全1，那么通过相同的列翻转操作，数组[1, 1, 0](注意，110和011异或后为0)也可以变为全1或者全0，而其他排列的数组则不会变为全0或者全1(具有互斥性)。我们将这些两两异或后为0的行放在一个集合内，该问题本质就是求解最大的集合，其中集合内的行通过相同的列翻转操作可以变为全0或者全1。我们可以使用哈希表进行集合计...

Posted by Jeza Chen on June 11, 2024

FEATURED TAGS
LeetCode 数组 贪心 哈希表 动态规划 排序 前缀和 图论 字符串 模拟 双指针 Python 杂七杂八 滑动窗口 DFS BFS 递归 二叉树 单调栈 数学 栈 二分法 回溯法 并查集 构造 树 矩阵 记忆化搜索 链表 Python进阶 位计算 回溯 导入系统 最短路径 枚举 队列 集合 二分搜索 位运算 后序遍历 堆 密码学 数据结构 算法日记 调试 C++ Trie 元编程 分治 可搜索加密 差分 差分数组 拓扑排序 椭圆曲线 线段树 维护左枚举右 计数 论文相关 路由器 C LaTeX Linux PyQt Pytest Python测试 Qt ST表 TODO Ubuntu WSL
ABOUT ME

程式編一半

長橋起不過半

完成將很美滿

半途卻放下沒有管

RECOMMENDATIONS
MY REPOS
SSEPy

可搜索对称加密实现
Searchable Symmetric Encryption

[CGKO06]的实现
PyQtInspect

像Chrome元素检查工具一样检查PyQt/PySide程序元素
MendeleyDesktop For Ubuntu 22.04

Ubuntu 22.04下的Mendely重打包