力扣第331场周赛题解
rank | T1 | T2 | T3 | T4 |
---|---|---|---|---|
331 / 4256 | 0:01:46 | 0:06:18 (1) | 0:11:58 | 0:57:29 (4) |
T1 从数量最多的堆取走礼物
模拟题,每次操作找出最大值$maxx$并将其变成$sqrt(maxx)$,$k$次操作后求和。
数据范围很小,可以暴力模拟,更好的方法是使用优先队列模拟。
时间复杂度 $O(max(n,k)log(n))$
空间复杂度 $O(n)$
参考代码
1 | class Solution { |
T2 统计范围内的元音字符串数
给定一个字符串数组,每次询问区间$[l,r]$内,首尾字母都是元音字母的字符串数量。
预处理前缀和,差分询问。
时间复杂度 $O(n+q)$
空间复杂度 $O(n)$
参考代码
1 | const int N = 1e5 + 10; |
T3 打家劫舍 IV
要求最大值最小,经典二分答案+ $check$
$check$ 思路:二分出 $mid$,贪心地线性检查能否取出 $k$ 个价值 $<=mid$ 的房屋即可。
时间复杂度 $O(nlog(m))$
空间复杂度 $O(n)$
参考代码
1 | const int N = 1e5 + 10; |
T4 重排水果
如下考虑:
判断原数组是否合法:两个数组排序后相同,则直接返回0。
判断是否存在解:将两个数组的元素混合在一起,如果某个元素为奇数个,那么一定无解。
剩下来的是必定有解,但需要交换的情况。
首先去除他们的交集元素,现在数组 $a$ 和数组 $b$ 分别多了某些元素。根据每个元素的总数量,容易计算得到他们分别多出来 $x_i$ 个 $y_i$,维护 $outa$和 $outb$,$outa[x]=y$表示数组 $a$的 $x$元素多了 $y$个。
考虑如何交换最优:
① 用数组 $a$中的最小值和数组 $b$中的最大值交换,花费为$min(a_{minn},b_{maxx})$
② 用数组 $a$中的最大值和数组 $b$中的最小值交换,花费为$min(b_{minn},a_{maxx})$
③ 容易遗漏的一种情况,利用所有元素的最小值作为中间者,间接的交换$ab$中的元素:swap(a,c); swap(b,c);
,因为 $c$必定为最小值,且被用到了两次,因此花费为 $minn*2$
贪心地,如果数组 $a$中的最小值$<$数组 $b$中的最小值,则选用方案①③的组合,否则选用方案②③的组合。
时间复杂度 $O(nlog(n))$
空间复杂度 $O(n)$
参考代码
1 | const int N = 1e5 + 10; |