JZX 轻语

LeetCode 1535 - 找出数组游戏的赢家

从左到右模拟每个元素能连赢多少次即可，如果连赢次数达到k后则返回当前赢家，否则处理完所有元素后，此时的赢家即数组的最大值，此时后面都是它一直赢，此时直接返回最大值即可。 class Solution: def getWinner(self, arr: List[int], k: int) -> int: cur_max = arr[0] b...

Posted by Jeza Chen on May 19, 2024

LeetCode 853 - 车队

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

首先对所有的车按位置从大到小排序，以获得有序的位置信息。不难得知，每个车队的速度都以车头(即距离更大者)为准，也即车和车队之间的比较只要以车头为准。因此，可以使用两个变量分别维护当前所处理车队的车头起始位置和速度，按位置顺序遍历所有的车辆，如果当前车辆能在target之前赶上该车队(的车队)，则将其合并在同一个车队中；否则(要么速度不够，要么追上时已经在target之后了)，以该车作为车头新...

Posted by Jeza Chen on May 16, 2024

LeetCode 1953 - 你可以工作的最大周数

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

这种任务规划题基本可以考虑利用贪心解决，通过观察发现，可以完成所有工作的充要条件为max_ <= rest + 1，其中mex_为耗时最长的工作量，而rest则为其他的工作量。最优的安排即为将分配工作时间的过程转化为在[1,longest+rest]闭区间内分配整数的过程，其中每个整数代表对应的一周时间。在分配整数的过程中，首先按照从小到大的顺序分配所有的奇数，然后按照从小到大的顺序分...

Posted by Jeza Chen on May 16, 2024

LeetCode 851 - 喧闹和富有

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

首先使用图论将问题抽象出来，将人视作为节点。可以采用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 1535 - 找出数组游戏的赢家

LeetCode 853 - 车队

LeetCode 1953 - 你可以工作的最大周数

LeetCode 851 - 喧闹和富有

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

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

LeetCode 848 - 字母移位

LeetCode 846 - 一手顺子

LeetCode 845 - 数组中的最长山脉

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

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04