JZX 轻语

LeetCode 2079 - 给植物浇水

模拟浇水的流程即可，使用一个变量维护当前的水量，如果当前的植物浇水量大于当前水量，则加上折返的步数，否则加1即可。直观的做法： class Solution: def wateringPlants(self, plants: List[int], capacity: int) -> int: cur_cap = capacity ans...

Posted by Jeza Chen on May 8, 2024

LeetCode 786 - 第K个最小的质数分数

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

一般求解第k小的问题都可考虑使用堆来解决，首先最小的分数为最小的质数/最大的质数，先将它加入到堆中。每次从堆中处理当前最小的分数时，将其分母左移一位or分子右移一位，再将这两个数放在堆中。直至处理第k个数即可。由于期间可能会有重复的添加，因此需要引入一个记录上次处理的分子/分母数据，以去重。 import heapq class Solution: def kthSmall...

Posted by Jeza Chen on May 6, 2024

LeetCode 787 - K站中转内最便宜的航班

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

一开始使用了Dijkstra算法，后面发现不太适用，因为最多K次中转不代表最多K次循环。后面改用了队列+BFS的做法，队列维护节点、从源节点到该节点的路径总开销以及中转站数量，在每次循环中，从队列取出队首，更新节点的最小开销，如果该节点的中转站数量达到k后则不再进行松弛，否则松弛其后继节点并将松弛后的开销加入到队列中。由于一开始没考虑到稠密图的情况，因此可能会出现队列迅速膨胀导致MLE的问题...

Posted by Jeza Chen on May 5, 2024

LeetCode 784 - 字母大小写全排列

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

一般这种全排列题目都可用回溯法解决，在每次递归中，如果遇到数字则直接处理下一个字符；否则，如果是字符则额外进行大小写转换后再处理一次。为减少递归次数，可以在一次递归中直接跳过数字。原做法： 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 2079 - 给植物浇水

LeetCode 786 - 第K个最小的质数分数

LeetCode 787 - K站中转内最便宜的航班

LeetCode 784 - 字母大小写全排列

LeetCode 1652 - 拆炸弹

LeetCode 1235 - 规划兼职工作

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

LeetCode 763 - 划分字母区间

LeetCode 594 - 最长和谐子序列

LeetCode 752 - 打开转盘锁

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04