JZX 轻语

LeetCode 784 - 字母大小写全排列

一般这种全排列题目都可用回溯法解决，在每次递归中，如果遇到数字则直接处理下一个字符；否则，如果是字符则额外进行大小写转换后再处理一次。为减少递归次数，可以在一次递归中直接跳过数字。原做法： class Solution: def letterCasePermutation(self, s: str) -> List[str]: ans = [] ...

Posted by Jeza Chen on May 5, 2024

LeetCode 1652 - 拆炸弹

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

固定长度的滑动窗口题目，可以使用left和right维护一个左闭右开的滑动窗口，每次遍历的时候，该窗口向右移动一个元素即可。也可以不用上述两个变量，毕竟是固定长，可以根据遍历的数组位置计算出来。维护窗口左右两侧指针的版本： class Solution: def decrypt(self, code: List[int], k: int) -> List[int]: ...

Posted by Jeza Chen on May 5, 2024

LeetCode 1235 - 规划兼职工作

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

会议安排题目的带权重版本。在会议安排普通版本的dp解法中，先按结束时间排序，然后令dp[i]为前i个会议中最多能安排的会议数，则有dp[i] = max(dp[i - 1], dp[k] + 1)(即，要么选取第i个会议，要么不选，使用前i - 1个会议的结果)，其中k是指前k个会议的结束时间小于等于第i个会议的开始时间。在带权重的版本中，可以改写成dp[i] = max(dp[i - 1]...

Posted by Jeza Chen on May 4, 2024

LeetCode 792 - 匹配子序列的单词数

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

朴素想法是，每遍历s的一个字符时，分别更新words中每个单词的匹配指针(一开始从0开始，可视作为下一个期望的指针)位置：如果匹配上，则往右移动指针。上述朴素做法会超时，因为需要遍历每一个单词，而往往不匹配的情况非常多。因此，使用一个哈希表来缓存每个单词下一次期望字符的信息，其中键为下一次期望字符，而值为单词列表，其中这些单词的下一次期望字符为对应键。当遍历s中的字符时，从哈希表中取出下一次...

Posted by Jeza Chen on May 3, 2024

LeetCode 763 - 划分字母区间

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

首先遍历一遍数组，得到每个字母最后出现的位置。不难得到，某个字母的最后出现位置也必定需要在同一个区间内。因此，可以使用双指针来分别指向当前元素（一个一个向右移动）、该元素所在区间的最后位置（左指针遍历到一个元素时，使用其最后一次出现位置尝试向右扩展）。如果两个指针指向同一个位置，说明该区间可以作为一个独立的结果，加入到结果数组中。 class Solution: def par...

Posted by Jeza Chen on May 2, 2024

LeetCode 594 - 最长和谐子序列

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

使用哈希表记录每个数组的个数，然后再遍历哈希表的键key，如果key + 1也在哈希表里，则使用其和更新结果(取两者最大值)；此外，也可以先排序，然后再遍历计数，维护最近两个数字的计数，如果这两个数字相邻，则使用其和更新结果。基于哈希表： class Solution: def findLHS(self, nums: List[int]) -> int: ...

Posted by Jeza Chen on May 2, 2024

LeetCode 752 - 打开转盘锁

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

BFS的应用，使用BFS模拟可能的所有转法(从第1位开始，往上拨or往下拨，直至第4位)。如果某个转法已经处理过or锁死，则不加入队列中。 from collections import deque class Solution: def _roll(self, cur_lock: str): for i in range(4): y...

Posted by Jeza Chen on April 29, 2024

LeetCode 1329 - 将矩阵按对角线排序

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

不难得知，在每个对角线的元素中，列号和行号的差值是恒定的，可以根据行号确定某个对角线元素的列号。按行/列其中一个维度斜着就地快速排序即可，需要注意边界条件。 class Solution: def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]: def partition(lo: ...

Posted by Jeza Chen on April 29, 2024

LeetCode 743 - 网络延迟时间

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

本质就是求单源最短路径，然后返回节点K到其他节点的路径中的最大者即可。普通的Dijkstra算法： from collections import deque class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: adj_...

Posted by Jeza Chen on April 28, 2024

LeetCode 735 - 小行星碰撞

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

使用栈来维护存活的小行星(不难推出，这个数组中，往左走的小行星必定在所有往右走小行星的前面，否则会继续发生碰撞)。从左往右处理小行星，如果小行星往左走、仍存活、且栈顶的小行星(存活的小行星中最靠右的)往右走，则处理碰撞，直至不满足上述条件。 class Solution: def asteroidCollision(self, asteroids: List[int]) -&g...

Posted by Jeza Chen on April 28, 2024

LeetCode 784 - 字母大小写全排列

LeetCode 1652 - 拆炸弹

LeetCode 1235 - 规划兼职工作

LeetCode 792 - 匹配子序列的单词数

LeetCode 763 - 划分字母区间

LeetCode 594 - 最长和谐子序列

LeetCode 752 - 打开转盘锁

LeetCode 1329 - 将矩阵按对角线排序

LeetCode 743 - 网络延迟时间

LeetCode 735 - 小行星碰撞

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04