JZX 轻语

LeetCode 901 - 股票价格跨度

本质问题就是对于每个元素，求解左边第一个比其大的元素下标，此时两个下标的跨度即所需结果。此类问题(1. 对于每个子问题(数组的每个元素)，求解元素单侧比它大/小的第一个元素; 2. 如果维护子问题的结果)，均可以使用单调栈来求解。 class StockSpanner: def __init__(self): self._stack = [] # typin...

Posted by Jeza Chen on May 22, 2024

LeetCode 2225 - 找出输掉零场或一场比赛的玩家

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

使用哈希表记录每个玩家的负场次数即可，然后再有序遍历(避免结果数组需要排序)哈希表的键输出即可。由于有些玩家从来没输过，如果哈希表仅保存负者的数据是不够的，因为不清楚到底有几个玩家，所以遍历比赛数据时，如果赢家没有在哈希表时，则显式将其初始化为0。 class Solution: def findWinners(self, matches: List[List[int]])...

Posted by Jeza Chen on May 22, 2024

LeetCode 893 - 子数组按位或操作

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

对于这种子数组的特征问题，一般来说可以考虑前缀和思路。但由于or操作并不满足差分性质，所以需要使用一个集合ans来维护所有的非重复结果，以及一个数据结构last来存储以上一个元素结尾的所有子数组的按位或结果，然后再将last中所有的结果和当前的元素再异或一次，放进ans中，并更新last(还需要往后追加当前元素，作为长度为1的子数组)。一开始使用的是列表，但随着数组的变大，循环的量会逐渐变多...

Posted by Jeza Chen on May 21, 2024

LeetCode 893 - 特殊等价字符串组

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

可以通过观察发现，每个等价字符串组里面的字符串都满足一个特征：对其里面的字符按奇数位、偶数位分别排序，所得到的字符串都是一样的，而不同的组根据上述步骤所得到的特征字符串不一样。因此，可以使用一个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 901 - 股票价格跨度

LeetCode 2225 - 找出输掉零场或一场比赛的玩家

LeetCode 893 - 子数组按位或操作

LeetCode 893 - 特殊等价字符串组

LeetCode 890 - 查找和替换模式

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

LeetCode 886 - 可能的二分法

LeetCode 885 - 螺旋矩阵III

LeetCode 1542 - 救生艇

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

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04