JZX 轻语

LeetCode 826 - 安排工作以达到最大收益

朴素做法是，对于每一个worker，遍历所有的工作，找到难度满足工人能力中收益的最大值，这样的复杂度为O(nm)。可以通过排序的方法降到O(nlogn + mlogm)：对工作按工作难度进行排序，以及对工人的能力进行排序，使用一个指针cur_valid_work_cnt维护当前有效的工作数量(即对于当前遍历的工人都能干的活)，并使用cur_valid_work_max_profit维护当前有...

Posted by Jeza Chen on May 12, 2024

LeetCode 825 - 适龄的朋友

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

通过整理条件可知，x加上y的条件满足0.5 * ages[x] + 7 < ages[y] <= ages[x]。因此，先对用户按年龄排序，然后从小到大遍历用户，使用二分法找到可添加的用户群即可。需要注意的是同年龄用户的处理，对于n个同龄用户，我们可以跳过前n - 1个同龄用户的处理，处理第n个用户后，将其结果乘以n即可。 class Solution: def n...

Posted by Jeza Chen on May 12, 2024

LeetCode 1553 - 吃掉N个橘子的最少天数

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

一个需要亿点证明的动态规划/记忆化搜索题目，朴素的状态转移方案为minDays(n) = 1 + min(minDays(n - 1), minDays(n // 2) if n % 2 == 0, minDays(n // 3) if n % 3 == 0)。但这样，对于特别大的n，不断-1很容易爆栈。因此，可以根据证明得到，每次-1的操作都是有限的，在每次递归中我们只要减到能被2或者3整...

Posted by Jeza Chen on May 12, 2024

LeetCode 2391 - 收集垃圾的最少总时间

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

还是模拟的题目，最理想的结果是每辆垃圾车都刚好停在对应垃圾所在的最后位置，不再往前开（没意义），因此最短时间为所有垃圾的处理时间（所有垃圾的数量）+ 三种类型的垃圾车到达该类型垃圾最终位置的用时。其中，前者可累加所有字符串的长度即可；后者则可使用前缀和的方法减少计算量（三次计算->一次计算）。 import itertools class Solution: def ...

Posted by Jeza Chen on May 11, 2024

LeetCode 809 - 情感丰富的文字

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

使用数组记录单词中连续字符的个数，然后再两两比对，不能扩展的情况有以下四种：1. word中出现了s中没有出现的字符；2. word中不连续字符个数和s不相等(如sass和sa)；3. s中某个字符连续次数不超过3, 但word中该位置的字符连续次数又不相等(如sass和sas)；4. word中某个位置的字符连续次数超过了s相应位置字符的次数(没办法缩)。 class Solutio...

Posted by Jeza Chen on May 9, 2024

LeetCode 807 - 保持城市天际线

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

通过观察得知，若需要保持四个方向的天际线不变，本质就是保持每行每列的最大值不变。因此，对于第i行第j列的建筑，其可以将高度扩展到第i行最大值和第j列最大值两者的最小值。 class Solution: def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int: n = len(gri...

Posted by Jeza Chen on May 9, 2024

LeetCode 802 - 找到最终的安全状态

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

三色标记法+DFS，使用一个数组维护每个节点可能的三种状态：未遍历，正在遍历，遍历完毕。然后使用DFS计算每个节点是否为安全节点：如果其为终端节点，即也是安全节点；否则，遍历所有的路径，如果所有的路径经过的节点皆为安全节点，则该节点也为安全节点；如果碰上一个正在遍历的节点(在递归栈中)，则存在环，说明该路径是走不到终端节点的。这道题其实也是一个比较典型的拓扑排序应用题(毕竟终端节点定义为...

Posted by Jeza Chen on May 9, 2024

LeetCode 2105 - 给植物浇水II

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

给植物浇水I的双指针扩展，同样也是模拟的方式，一个从左到右，另一个从右往左，直至两者相遇。需要处理的特殊情况是两者最后刚好落在同一个地方，此时只要双方其一有足够的水即可，否则需要结果+1。 class Solution: def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) ->...

Posted by Jeza Chen on May 9, 2024

LeetCode 799 - 香槟塔

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

可通过递归的方式，先假设所有的香槟都全部倒进第一层第一个杯子上再溢出，然后自底向上递归计算指定层指定杯子的（溢出前）香槟量。即第i层第j个杯子的香槟量champion[i][j] = 0.5 * champion[i - 1][j - 1] + 0.5 * champion[i - 1][j]（由上一层的两个方向的杯子等量分流）。为了减轻递归的重复计算，可以使用字典来记忆化搜索，当然也可以使...

Posted by Jeza Chen on May 8, 2024

LeetCode 797 - 所有可能的路径

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

回溯模板题，直接dfs回溯所有结果即可，由于是DAG，没必要维护一个visited数组。 class Solution: def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: n = len(graph) ans = [] de...

Posted by Jeza Chen on May 8, 2024

LeetCode 826 - 安排工作以达到最大收益

LeetCode 825 - 适龄的朋友

LeetCode 1553 - 吃掉N个橘子的最少天数

LeetCode 2391 - 收集垃圾的最少总时间

LeetCode 809 - 情感丰富的文字

LeetCode 807 - 保持城市天际线

LeetCode 802 - 找到最终的安全状态

LeetCode 2105 - 给植物浇水II

LeetCode 799 - 香槟塔

LeetCode 797 - 所有可能的路径

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04