复盘|第336场周赛
统计范围内的元音字符串数
重排数组以得到最大前缀分数
【排序+贪心】从大到小排序后,一开始前缀和加到最大,后面能够减的空间就越大,可以一边遍历一边计算大于0的前缀和数量。
统计美丽子数组数目
【前缀和+哈希表】每次操作要把nums[i]和nums[j]同一个比特位的1改成0等同于每次修改两个1,题中说执行若干次修改后,子数组能变成全为0的数,显然这个子数组每个有1的比特位上都有偶数个1,执行偶数次的1 ⊕ 1 = 0后,该比特位才能全零。把所有比特位合起来看,美丽子数组这等价于子数组的异或和等于 0(子数组每个数的每个比特位异或0等价于子数组异或为0)。问题转换为求异或和为0的子数组的个数。子数组的异或和等于两个前缀异或和的异或,异或为0说明两个前缀和是相等的,即求前缀异或和数组中所有相同的数对。
完成所有任务的最少时间
【排序+贪心】为了尽可能让多个任务同时运行,应该尽量延迟任务的执行,所以按照右端点排序,对于task[i]来说,它右侧的任务要么和它没交集,要么包含它的区间后缀。遍历排序后的任务,先统计区间内电脑运行时间点,如果小于duration,就尽量把运行时间安排在区间[start, end]的后缀上。