JZX 轻语

LeetCode 3106 - 满足距离约束且字典序最小的字符串

本质上k就是最多可以操作的次数，其中由字符c1变换到字符c2需要操作的次数为min((ord(c1) - ord(c2) % 26, (ord(c1) - ord(c2)) % 26)(要么顺着变化，要么逆着)。为了得到字典序最小的结果，需要从左往右尽可能地将前面的字符翻转成a(两种操作方法中选取代价最小的方法)，如果剩余的次数不足以翻转到a，则往前翻转ASCII序更小的字符。为什么...

Posted by Jeza Chen on July 27, 2024

LeetCode 1319 - 连通网络的操作次数

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

基于图论一个重要的定理：如果一个图有n个节点，至少需要n-1条边才能使得所有节点连通。如果边的数量小于n-1，那么一定有节点无法连通。此外，如果有k个连通分量，那么至少需要k-1条边才能使得所有节点连通。因此，首先需要判断边的数量是否足够，如果不够，直接返回-1。然后，使用并查集来统计连通分量的数量，最后返回最少操作次数(即需要将这些连通分量连接起来的最少边数)为连通分量数-1。 cl...

Posted by Jeza Chen on July 27, 2024

LeetCode 1318 - 或运算的最小翻转次数

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

可使用贪心法解决：从低位到高位逐位比较a、b和c的对应位，如果c的对应位为1，则a和b的对应位至少有一个为1，否则需要翻转1次即可。如果c的对应位为0，则a和b的对应位需要全为0，此时翻转次数为a的对应位 + b的对应位。因此，只需要逐位比较并累加需要翻转的次数即可。 class Solution: def minFlips(self, a: int, b: int, c: i...

Posted by Jeza Chen on July 26, 2024

LeetCode 2844 - 生成特殊数字的最少操作

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

类似于5的倍数，25的倍数中，后缀永远是00，25，50以及75，反之依然(即当且仅当满足上述后缀的数，可以被25整除)。因此，我们可以使用贪心的做法，从后往前找到包含上述任一后缀顺序(具体而言，以25为例，如果该子串包含2和5，且2在5的前面)的最短后缀子串suffix，然后需要删除的字符数即为len(suffix) - 2。 # 25, 50, 75, 00 class Solut...

Posted by Jeza Chen on July 25, 2024

LeetCode 1310 - 子数组异或查询

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

前缀异或满足查分的特性，记pre_xor[i]为数组前i个元素的异或值，即对于i > j，我们有pre_xor[i] ^ pre_xor[j] = (pre_xor[j] ^ arr[j+1] ^ ... ^ arr[i]) ^ pre_xor[j] = arr[j+1] ^ ... ^ arr[i]。我们可以采取类似于前缀和的方法，预处理出前缀异或数组pre_xor，然后对于每个查询...

Posted by Jeza Chen on July 25, 2024

LeetCode 1306 - 跳跃游戏 III

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

简单地通过BFS遍历即可，直到找到0后返回True。需要注意下边界条件，以及将遍历过的位置进行标记。 class Solution: def canReach(self, arr: List[int], start: int) -> bool: queue = deque([start]) visited = [False] * len(a...

Posted by Jeza Chen on July 25, 2024

LeetCode 3096 - 得到更多分数的最少关卡数目

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

由于Alice必须从0开始连续选择关卡完成，这本质就是前缀和的问题。于是问题可以转化为，找到一个最短的前缀，使得该前缀所得分数大于剩下的关卡所得分数，其中，possible[i] = 0的关卡所得分数为-1。因此，我们首先计算所有关卡的总得分(总得分是固定的)，然后从前往后第二次遍历，计算前缀和，如果前缀和大于剩下的关卡得分(总得分减去当前的前缀得分)，则跳出循环，返回当前关卡数目。 ...

Posted by Jeza Chen on July 19, 2024

LeetCode 3112 - 访问消失节点的最少时间

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

单源最短路径问题的变种，可使用Dijkstra算法解决。如果从节点0到某个节点i的最短路径大于等于disappear[i]，则该节点不可达，此外，该节点也不可参与松弛操作。因此，只需要在Dijkstra算法中加入这个判断条件即可。一开始基于优先队列的算法实现，注意这里的消失条件判断放在了松弛操作之前。 import heapq class Solution: def m...

Posted by Jeza Chen on July 18, 2024

LeetCode 2959 - 访问消失节点的最少时间

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

多源最短路径问题的变种，可使用Floyd算法解决。题意要求求解的是去掉某些节点后，所有节点之间的最短路径都不超过maxDistance的方案数。可以逆向思考，求解子集中所有节点之间的最短路径都不超过maxDistance的子集数量。因此，我们可以使用回溯法枚举所有子集，然后使用Floyd算法求解子集中所有节点之间的最短路径，最后统计满足条件的子集数量。需要注意的是，如果在每个枚举中都重新来一...

Posted by Jeza Chen on July 17, 2024

LeetCode 1283 - 使结果不超过阈值的最小除数

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

此类寻找满足某种条件中的最小值的题目，通常可以使用二分搜索来解决。对于本题，我们定义check函数为判断是否满足条件(即遍历数组，累加每个元素的除法取上界结果)的函数，然后使用二分搜索来寻找最小的满足check函数为True的值。 class Solution: def smallestDivisor(self, nums: List[int], threshold: int)...

Posted by Jeza Chen on July 16, 2024

LeetCode 3106 - 满足距离约束且字典序最小的字符串

LeetCode 1319 - 连通网络的操作次数

LeetCode 1318 - 或运算的最小翻转次数

LeetCode 2844 - 生成特殊数字的最少操作

LeetCode 1310 - 子数组异或查询

LeetCode 1306 - 跳跃游戏 III

LeetCode 3096 - 得到更多分数的最少关卡数目

LeetCode 3112 - 访问消失节点的最少时间

LeetCode 2959 - 访问消失节点的最少时间

LeetCode 1283 - 使结果不超过阈值的最小除数

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04