JZX 轻语

LeetCode 1328 - 破坏回文串

由于是回文串，所以只需要遍历前半部分即可。如果遇到非a的字符，将其替换为a并返回即可。如果前半部分全是a(意味着后半部分也全是a，注意如果字符串长度为奇数的话，中间那个字符不一定为a，但也不能修改，因为改了之后还是回文)，则将最后一个字符替换为b即可。 # 0 1 <2> 3 4 # 0 1 2 <3> 4 5 # 0 1 2 <3> 4 5 6 c...

Posted by Jeza Chen on July 29, 2024

LeetCode 1325 - 删除给定值的叶子节点

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

简单的后序遍历题目，首先递归遍历左右子树，子树遍历完毕后再判断当前节点是否为叶子节点且值为target，如果是则删除该节点。最后返回操作后的子树根节点(如果被删除了则返回空)。 class Solution: def is_leaf(self, node: TreeNode): return node.left is None and node.right is...

Posted by Jeza Chen on July 29, 2024

LeetCode 699 - 掉落的方块

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

线段树的应用题，由于之前没系统实现过线段树，所以这次从头学了一遍线段树的简单实现和应用。该题目就是在一个二维的坐标轴上，不断添加方块，并将每次添加后所有方块的最大高度添加到结果中。本质上，每次添加边长为sideLength的方块时，首先需要找到该方块所在x轴区间[left, left + sideLength - 1]的最大高度h，然后将该区间的最大高度更新为h + sideLength。不...

Posted by Jeza Chen on July 28, 2024

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

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

本质上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 1328 - 破坏回文串

LeetCode 1325 - 删除给定值的叶子节点

LeetCode 699 - 掉落的方块

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

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

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

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

LeetCode 1310 - 子数组异或查询

LeetCode 1306 - 跳跃游戏 III

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

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04