JZX 轻语

挖掘时光的细节

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

LeetCode 1061 - 按字典序排列最小的等效字符串

Flash 此文章属于Flash闪念部分的短文
题目有点绕，但由于等价关系具有对称性和传递性(即a等价于b，b等价于c，则a等价于c)，因此可以使用集合来表示等价关系(即上述的a、b和c可以放在一个集合内)，而此类问题的解法通常是使用并查集。对于每个集合，我们需要找到集合内最小的字符，可适当修改下并查集的模板实现：每个集合的代表(即根节点)使用最小字符，在合并两个集合时，取两个集合内最小的字符作为合并后集合的最小字符。 import...

Posted by Jeza Chen on June 11, 2024

LeetCode 1053 - 交换一次的先前排列

Flash 此文章属于Flash闪念部分的短文
为了保证交换后的数字在小于原数字的要求下尽可能大，交换的位置应尽可能靠右。因此，我们从右往左扫描，找到第一个不满足升序的位置(即对于位置i有arr[i] > arr[i - 1])，然后在其右边找到最大的比它小的数（如果有重复值, 则交换最靠左的）arr[j]，交换这两个数即可。 贪心可行性的证明: 证明上述的待交换左侧位置i是最优的：如果存在一个更优的位置k，...

Posted by Jeza Chen on June 11, 2024

LeetCode 3067 - 在带权树网络中统计可连接服务器对数目

Flash 此文章属于Flash闪念部分的短文
其实没啥好的做法，需要枚举每个节点，计算其作为根节点时，每棵子树(每个方向)中路径长度为signalSpeed的倍数的边的数量。然后经过该节点的服务器对数目就是以该节点作为根时，不同子树中满足上述条件的边两两乘积的和。可以用BFS或DFS来实现。 两两乘积的和，可以利用后缀和来优化二次循环：先计算出各个方向结果的总和，然后每次遍历的时候减去当前的值，就可以得到剩下未遍历元素的总和，然后...

Posted by Jeza Chen on June 4, 2024

FEATURED TAGS
LeetCode 数组 贪心 哈希表 动态规划 排序 前缀和 图论 字符串 模拟 双指针 杂七杂八 DFS Python 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重打包