讨论/技术交流/🏆 第 238 场力扣周赛/
🏆 第 238 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - K 进制表示下的各位数字总和
4 分 - 最高频元素的频数
5 分 - 所有元音按顺序排布的最长子字符串
6 分 - 最高建筑高度

4

简易题解。

T1
短除法将十进制的n转化为k进制数。对n不断除以k,在这个过程中统计余数即可。
时间复杂度O(logn),空间复杂度O(1)

T2
不难发现调整后出现次数最多的数一定在原数组中。因此将nums排序后,对于每一个nums[i],我们需要从nums[i-1]开始一直往前统计,直到它们与nums[i]的差值之和刚好不大于k。这是一个滑动窗口的经典应用。
时间复杂度排序O(nlogn),滑动窗口统计结果O(n)。空间复杂度O(1)
个人认为此题难度高于T3。

T3
首先不考虑需要全部元音字母的条件,只考虑子串升序的条件。那么原串一定可以像这样分割:
aei/aaio/aaaaeiiiiouuu/oo/aauu/aeiu
不难发现当前字符小于前一个字符就是分割的条件,只需要用一个额外的变量储存子串长度。
而对于需要5种全部元音字母,只需要再用一个额外变量统计字母类型。如果当前字符大于前一个字符,说明引入了一个新字符。
时间复杂度O(n),空间复杂度O(1)

T4
根据贪心的思想,不难得出的结论是我们总是希望有限制的楼层高度等于它的限制值。我们按照限制的编号排序后,为了使这个过程中建筑的最大高度更大一些,我们一定选择如/\的建法,这个尖的高度根据前后的编号和高度限制很容易推算。
唯一的问题在于,可能有一些虚假的限制,例如我们限制编号12的楼层高度不大于100,但限制编号13的楼层高度不大于3。此时12号楼的限制是虚高的,它真实的限制应该为4,这样才能保证在12号高度为限制值时,13号的高度有可能达到3。
因此我们还需要根据限制高度排序,对于每一个限制向左查看是否存在限制虚高的情况。如果二者的限制高度差大于二者的编号差,则进行调整。
时间复杂度O(nlogn),空间复杂度O(n)
这题难度在周赛还可以,唯一的问题是,它是个老原题了。。。。。。

展开全部 74 讨论