JZX 轻语

LeetCode 1104 - 二叉树寻路

本质就是完全二叉树寻父节点计算方法(该计算在二叉堆里经常使用到，即，如果节点从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

LeetCode 1020 - 飞地的数量

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

该题目的本质就是求解和边界不相通的陆地单元格数量。可以使用BFS就地对和边界相连的陆地单元格进行标记(将其改为2即可)，然后再次遍历整个矩阵，统计未被标记的陆地单元格数量。这里有两个注意点：避免重复标记，可以在遍历边界时，避免重复标记。在移动的时候就标记为2，而非在出队的时候标记，避免重复入队浪费时间。 class Solution...

Posted by Jeza Chen on June 4, 2024

LeetCode 1019 - 链表中的下一个更大节点

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

一般而言，求解下一个更大元素的题目可以考虑单调栈。在此类题目中，可以使用栈来存储当前右侧还没有更大元素的链表节点(必然单调递减，否则和前提矛盾)。遍历链表节点，如果当前节点的值大于栈顶节点的值，则弹出栈顶节点并设置其结果为当前节点的值，直至栈为空或栈顶节点的值大于当前节点的值。最后将当前节点入栈。在这里需要注意一点的是，由于遍历完毕前并不清楚链表的长度，在遍历每个节点时，需要先追加一...

Posted by Jeza Chen on June 4, 2024

LeetCode 1011 - 在D天内送达包裹的能力

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

此类求解满足条件的最小值的题目，且满足小于该值时均不满足条件，大于该值时均满足条件，可考虑使用二分法来解决。首先确定二分的上下界[货物最大值, 货物总量](小于货物最大值必然不满足条件, 大于货物总量必然满足条件)，然后使用二分法来逼近满足条件的最小值。 class Solution: def shipWithinDays(self, weights: List[int], d...

Posted by Jeza Chen on June 4, 2024

LeetCode 1104 - 二叉树寻路

LeetCode 1094 - 拼车

LeetCode 419 - 甲板上的战舰

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

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

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

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

LeetCode 1020 - 飞地的数量

LeetCode 1019 - 链表中的下一个更大节点

LeetCode 1011 - 在D天内送达包裹的能力

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04