JZX 轻语

LeetCode 893 - 特殊等价字符串组

可以通过观察发现，每个等价字符串组里面的字符串都满足一个特征：对其里面的字符按奇数位、偶数位分别排序，所得到的字符串都是一样的，而不同的组根据上述步骤所得到的特征字符串不一样。因此，可以使用一个set记录不同的特征，返回集合的大小即可。 class Solution: def numSpecialEquivGroups(self, words: List[str]) ->...

Posted by Jeza Chen on May 21, 2024

LeetCode 890 - 查找和替换模式

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

哈希表的应用题，对于每个单词word，使用一个哈希表记录同个位置word字母到pattern字母的映射，如果发现某个字母已存在映射且先前指向不一样的字母，则不满足要求。此外，由于要求双射，即word中的不同字母也不能指向同一个pattern字母，可以比较哈希表中键与值的非重复值数量，如果相同，意味着是一对一的双射，否则存在多对一的情况，不满足要求。 class Solution: ...

Posted by Jeza Chen on May 21, 2024

LeetCode 889- 根据前序和后序遍历构造二叉树

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

类似于根据前序+中序遍历构造二叉树，不同之处在于仅根据前序和后序则不能构建一棵唯一的二叉树，即如果只有一个孩子的情况下，仅根据前序和后序遍历是无法得知其为左孩子还是右孩子。在每次递归下，如果当前子数组的长度为1，则此时子树仅只有一个节点，直接返回该节点即可；否则，该子树的根的值为前序遍历子数组的第一个元素，亦是后序遍历子数组的最后一个元素；而其第一个孩子(左孩子)的值为前序遍历子数组的第2个...

Posted by Jeza Chen on May 21, 2024

LeetCode 886 - 可能的二分法

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

这种与关系相关联的题目一般而言可以使用图来建模，本题目的厌恶关系可以使用无向图连接起来，然后使用染色法对节点进行染色：节点和其相邻的节点不能处在同一个颜色中。我们可以使用DFS递归染色：邻接节点的期望颜色和当前节点的颜色相反，如果邻接节点已经染色且和当前节点处在同一个颜色，则无法进行二分，不满足题意。 class Solution: def possibleBipartitio...

Posted by Jeza Chen on May 21, 2024

LeetCode 885 - 螺旋矩阵III

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

可以通过模拟的方式，使用迭代器的方式计算下一个位置，然后判断该位置是否有效，若有效则加入到结果中，直至结果列表的大小为行 x 列。位置的产生规律不难得知：首先右1步，然后下1步，左2步，上2步，右3步，下3步，左4步，上3步…对于同一个步数，只对应两个方向。我们只需对同一个步数，计算两个方向的逐个位置信息，然后再累加步数，再计算后两个方向的逐个位置信息即可。位置的切换则按右->下-&g...

Posted by Jeza Chen on May 20, 2024

LeetCode 1542 - 救生艇

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

可使用贪心算法解决：先将people按体重排序，对于还没上船的人群中，选择其中体重最大的人，如果加上当前体重最小的人还没有超出船的承载量，则两个一起乘坐；否则，只承载最重的那个人。如此往复，直至全部人上船。上述过程可以使用双指针维护状态：左指针维护还没上船的人中最轻的人，右指针则指向最重的人。 class Solution: def numRescueBoats(self, p...

Posted by Jeza Chen on May 20, 2024

LeetCode 1542 - 找出最长的超赞字符串

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

相当有挑战性的题目。朴素的前缀和做法是使用一个数组pre，其中pre[i] = (c0, ..., c9)是指数组arr前i个元素中，0-9的计数，所以子数组arr[i..j]的计数信息可通过pre[j + 1] - pre[i + 1]计算可得。若子数组满足超赞字符串(重排后满足回文)，则计数信息需要满足仅存在零个或一个奇数计数位。因此，遍历所有的位次，计算前缀信息后再遍历以该元素结尾的子...

Posted by Jeza Chen on May 20, 2024

LeetCode 1535 - 找出数组游戏的赢家

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

从左到右模拟每个元素能连赢多少次即可，如果连赢次数达到k后则返回当前赢家，否则处理完所有元素后，此时的赢家即数组的最大值，此时后面都是它一直赢，此时直接返回最大值即可。 class Solution: def getWinner(self, arr: List[int], k: int) -> int: cur_max = arr[0] b...

Posted by Jeza Chen on May 19, 2024

LeetCode 853 - 车队

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

首先对所有的车按位置从大到小排序，以获得有序的位置信息。不难得知，每个车队的速度都以车头(即距离更大者)为准，也即车和车队之间的比较只要以车头为准。因此，可以使用两个变量分别维护当前所处理车队的车头起始位置和速度，按位置顺序遍历所有的车辆，如果当前车辆能在target之前赶上该车队(的车队)，则将其合并在同一个车队中；否则(要么速度不够，要么追上时已经在target之后了)，以该车作为车头新...

Posted by Jeza Chen on May 16, 2024

LeetCode 1953 - 你可以工作的最大周数

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

这种任务规划题基本可以考虑利用贪心解决，通过观察发现，可以完成所有工作的充要条件为max_ <= rest + 1，其中mex_为耗时最长的工作量，而rest则为其他的工作量。最优的安排即为将分配工作时间的过程转化为在[1,longest+rest]闭区间内分配整数的过程，其中每个整数代表对应的一周时间。在分配整数的过程中，首先按照从小到大的顺序分配所有的奇数，然后按照从小到大的顺序分...

Posted by Jeza Chen on May 16, 2024

LeetCode 893 - 特殊等价字符串组

LeetCode 890 - 查找和替换模式

LeetCode 889- 根据前序和后序遍历构造二叉树

LeetCode 886 - 可能的二分法

LeetCode 885 - 螺旋矩阵III

LeetCode 1542 - 救生艇

LeetCode 1542 - 找出最长的超赞字符串

LeetCode 1535 - 找出数组游戏的赢家

LeetCode 853 - 车队

LeetCode 1953 - 你可以工作的最大周数

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04