JZX 轻语

LeetCode 851 - 喧闹和富有

首先使用图论将问题抽象出来，将人视作为节点。可以采用DFS的方法解决问题：首先如果a比b富有，则添加有向边b -> a(注意是指向更富的人)，然后通过DFS的方法，求解节点a中，比a富有的人中，quiet值最小的人：首先初始化quiet最小者为自己，然后遍历子节点中quiet值最小者，更新自身的最优解，直至所有节点处理完毕。同样，此类涉及入度出度的问题可以转化为拓扑排序：如果a比b...

Posted by Jeza Chen on May 15, 2024

LeetCode 849 - 到最近的人的最大距离

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

一般这种考虑左右两侧的数组题目(如845)，都可以通过两次遍历(从左，从右)+前缀和思路维护局部数据，然后再遍历一次数组以组成结果。在这个题目中，这个局部数据就是左侧/右侧连续为0的个数，最后再遍历数组，其中第i个座位距离最近有人座位的距离为min(左侧连续为0的个数, 右侧连续为0的个数)。需要注意左/右侧没人的情况。此外，这种双侧题目，可以使用双指针+贪心的方式以减少空间开销。使用l...

Posted by Jeza Chen on May 15, 2024

LeetCode 2589 - 完成所有任务的最少时间

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

对于任务规划题目，一般都可以采取按结束时间排序 + 贪心的方法解决。在这个问题里，同样可以先按end排序，然后遍历所有的任务，首先优先寻找能够复用的时间段，即使用start对已经使用的时间occupied(离散时间点，如[1,2,3,5,6,7]表示时间[1-3]和[5-7]被使用，且可以复用)进行二分搜索，寻找大于等于start的元素下标位置i，此时可以复用的时间段数量为occupied....

Posted by Jeza Chen on May 15, 2024

LeetCode 848 - 字母移位

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

对于这种带有累加意味的题目，可以考虑前缀和思想，不过该题其实是后缀和，从右往左累加移位次数，然后再遍历一次字符串，一次完成移位操作即可。需要注意的是移位次数可能会比较大，需要取模；且小写字母的移位操作为chr(ord_a + ((ord(s[i]) - ord_a) + suffix_sum[i]) % 26). class Solution: def shiftingLett...

Posted by Jeza Chen on May 14, 2024

LeetCode 846 - 一手顺子

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

类似于题目2007，使用贪心法从小到大处理数字。先使用哈希表cnt_map对数字计数。然后从小到大遍历数字num，尝试抽取cnt_map[num]次组(num, num + 1, ..., num + groupSize - 1)，如果组内有个数字的计数小于cnt_map[num]，则无法完成题目要求，直接返回False，直至所有的牌处理完毕。 class Solution: ...

Posted by Jeza Chen on May 14, 2024

LeetCode 845 - 数组中的最长山脉

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

这种涉及两侧计算的数组问题一般都可以考虑使用双侧前/后缀和的思想来维护阶段信息，对于此问题，使用两个数组l2r_inc_cnt和r2l_inc_cnt分别维护某个元素左侧/右侧连续递增的最大长度(不包括该元素)。然后再重新遍历一次数组，对于下标i，取l2r_inc_cnt[i] + r2l_inc_cnt[i] + 1的最大者即可。进阶要求一次遍历+O(1)空间复杂度，可以考虑使用双指针...

Posted by Jeza Chen on May 14, 2024

LeetCode 2244 - 完成所有任务需要的最少轮数

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

本质思路就是遍历所有的任务，累加完成每一任务的最少轮数就行。而对于如果计算单个任务完成的最少轮数，一开始使用了动态规划，即完成i个相同任务的时间未MinRounds[i] = (MinRounds[i - 3], MinRounds[i - 2]) + 1；后面发现使用贪心即可：如果任务个数i满足被3整除，则最少轮数为i // 3；若i % 3 == 2，则先完成两个，然后再三个三个完成，即...

Posted by Jeza Chen on May 14, 2024

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

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

朴素做法是，对于每一个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 851 - 喧闹和富有

LeetCode 849 - 到最近的人的最大距离

LeetCode 2589 - 完成所有任务的最少时间

LeetCode 848 - 字母移位

LeetCode 846 - 一手顺子

LeetCode 845 - 数组中的最长山脉

LeetCode 2244 - 完成所有任务需要的最少轮数

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

LeetCode 825 - 适龄的朋友

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

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04