JZX 轻语

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

题目有点绕，但由于等价关系具有对称性和传递性(即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 1015 - 可被K整除的最小整数

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

记r(i)为i个1组成的数字，不难得知r(i) % k = ((r(i-1) % k) * 10 + 1) % k。因此，我们可以不断累加i并计算r(i)的值，直到r(i) % k == 0为止。此外，我们还需要一个哈希表来存储r(i) % k的值，以便在遇到重复的r(i) % k时(意味着后面产生了循环的结果)，直接返回-1。此外，如果k为偶数或者5的倍数，那么不可能找到符合条件的i（所有...

Posted by Jeza Chen on June 2, 2024

LeetCode 1010 - 总持续时间可被60整除的歌曲

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

该题目本质是统计数对(a, b)的个数，其中(a + b) % 60 == 0。由于(a + b) % 60 == 0等价于(a % 60 + b % 60) % 60 == 0，我们可以使用一个哈希表来存储前面已处理的数字模60后结果的计数，然后遍历元素b，累加哈希表中(60 - b % 60) % 60的计数即可。也可以先计数后，再遍历哈希表中的1-29的数字，累加count[i] * ...

Posted by Jeza Chen on June 2, 2024

LeetCode 986 - 区间列表的交集

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

双指针典型题目。使用两个指针i和j分别指向A和B的区间，然后根据两个区间的交集(两个区间的最大左端点和最小右端点)来更新答案。指针的移动规则是：如果A区间的右端点小于等于B区间的右端点(A区间位于B左侧，说明A的下一个区间可能和B当前区间还是会有交集)，那么A区间的指针i向右移动；否则B区间的指针j向右移动。 class Solution: def intervalInters...

Posted by Jeza Chen on May 31, 2024

LeetCode 985 - 查询后的偶数和

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

挺简单的数组题目，首先累加一下数组中的偶数和，然后对每个查询进行偶数和的更新即可：如果查询前的数为偶数，那么需要减去原数值，如果查询后的数为偶数，那么需要加上新数值。 class Solution: def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]: ...

Posted by Jeza Chen on May 31, 2024

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

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

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

LeetCode 1020 - 飞地的数量

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

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

LeetCode 1015 - 可被K整除的最小整数

LeetCode 1010 - 总持续时间可被60整除的歌曲

LeetCode 986 - 区间列表的交集

LeetCode 985 - 查询后的偶数和

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04