JZX 轻语

LeetCode 3210 - 找出加密后的字符串

简单题目，对于字符s[i]，替换成s[(i + k) % n]即可。 class Solution: def getEncryptedString(self, s: str, k: int) -> str: n = len(s) ans = list(s) for i, ch in enumerate(s): ...

Posted by Jeza Chen on August 8, 2024

LeetCode 3218 & 3219 - 切蛋糕的最小总开销

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

问题I可以直接记忆化搜索/动态规划解决，即遍历所有可能的切法，递归计算各种切法的总开销，取最小值即可。即对于一个初始位置为(begin_r, begin_c)，大小为(width, height)的矩形，最小的开销记为dp(begin_r, begin_c, width, height), 则有如下递归关系：如果width == 1或height == 1，则返回0； ...

Posted by Jeza Chen on August 7, 2024

LeetCode 3217 - 从链表中移除在数组中存在的节点

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

模板题，直接使用两个变量prev和curr，分别表示当前节点和前一个节点，然后遍历链表，如果当前节点的值在数组中，则删除当前节点: prev.next = curr.next。注意删除节点后，prev不需要移动。 class Solution: def modifiedList(self, nums: List[int], head: Optional[ListNode]) -...

Posted by Jeza Chen on August 7, 2024

LeetCode 3216 - 交换后字典序最小的字符串

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

直接贪心地从左到右找到第一个相邻的、具有相同的奇偶性、且第二个字符比第一个字符小的字符对，然后交换这两个字符即可。 class Solution: def getSmallestString(self, s: str) -> str: for i in range(len(s) - 1): a, b = int(s[i]), int...

Posted by Jeza Chen on August 7, 2024

LeetCode 3111 - 覆盖所有点的最少矩形数目

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

该题目只涉及到x坐标，y坐标是无关紧要的(矩形无高度限制)。本质就是尽可能地使用最少的矩形，使得其宽度覆盖所有的点。可先对所有点的x坐标进行排序，然后使用贪心法，每次取出一个当前剩余的最大的x坐标(作为新矩形的右边界)，然后再取出尽可能多的x坐标填充在矩形内，使得其差值不超过w即可。 class Solution: def minRectanglesToCoverPoints(...

Posted by Jeza Chen on July 31, 2024

LeetCode 1343 - 大小为 K 且平均值大于等于阈值的子数组数目

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

本质就是求解和大于等于k * threshold的子数组数目。使用一个定长为k的滑动窗口，每次移动窗口时，只需要减去左边界的值，加上右边界的值，然后判断是否满足条件即可。 class Solution: def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int: cur_...

Posted by Jeza Chen on July 31, 2024

LeetCode 1339 - 分裂二叉树的最大乘积

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

分析可知，切分后的两个子树的和越接近，乘积就越大。此外，其中一棵子树就是原树中以某个节点为根的子树，另外一棵则是以原树的根节点为根的、剩余节点构成的树。因此，只需要求出所有子树的和，然后找到和最接近总和一半的子树即可。官解使用的是二次遍历的方法，首先第一次用于求和，然后第二次再找到最大的乘积。这里使用后序遍历的方法，一次遍历得到所有子树的和，然后再找到最接近总和一半的子树即可。 c...

Posted by Jeza Chen on July 31, 2024

LeetCode 1328 - 破坏回文串

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

由于是回文串，所以只需要遍历前半部分即可。如果遇到非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 3210 - 找出加密后的字符串

LeetCode 3218 & 3219 - 切蛋糕的最小总开销

LeetCode 3217 - 从链表中移除在数组中存在的节点

LeetCode 3216 - 交换后字典序最小的字符串

LeetCode 3111 - 覆盖所有点的最少矩形数目

LeetCode 1343 - 大小为 K 且平均值大于等于阈值的子数组数目

LeetCode 1339 - 分裂二叉树的最大乘积

LeetCode 1328 - 破坏回文串

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

LeetCode 699 - 掉落的方块

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04