JZX 轻语

LeetCode 1542 - 救生艇

可使用贪心算法解决：先将people按体重排序，对于还没上船的人群中，选择其中体重最大的人，如果加上当前体重最小的人还没有超出船的承载量，则两个一起乘坐；否则，只承载最重的那个人。如此往复，直至全部人上船。上述过程可以使用双指针维护状态：左指针维护还没上船的人中最轻的人，右指针则指向最重的人。 class Solution: def numRescueBoats(self, p...

Posted by Jeza Chen on May 20, 2024

LeetCode 1542 - 找出最长的超赞字符串

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

相当有挑战性的题目。朴素的前缀和做法是使用一个数组pre，其中pre[i] = (c0, ..., c9)是指数组arr前i个元素中，0-9的计数，所以子数组arr[i..j]的计数信息可通过pre[j + 1] - pre[i + 1]计算可得。若子数组满足超赞字符串(重排后满足回文)，则计数信息需要满足仅存在零个或一个奇数计数位。因此，遍历所有的位次，计算前缀信息后再遍历以该元素结尾的子...

Posted by Jeza Chen on May 20, 2024

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

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

从左到右模拟每个元素能连赢多少次即可，如果连赢次数达到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 1542 - 救生艇

LeetCode 1542 - 找出最长的超赞字符串

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

LeetCode 853 - 车队

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

LeetCode 851 - 喧闹和富有

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

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

LeetCode 848 - 字母移位

LeetCode 846 - 一手顺子

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04