LeetCode第402场周赛题解

type

status

date

slug

summary

📝 主旨内容

构成整天的下标对数目 I(模拟)

给你一个整数数组 hours，表示以小时为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成整天的下标对 i, j 的数目。

整天定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

示例 1：

输入： hours = [12,12,30,24,24]

输出： 2

解释：

构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]

输出： 3

解释：

构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

提示：

1 <= hours.length <= 100

1 <= hours[i] <= 10^9

💡

签到题，直接双重模拟即可

构成整天的下标对数目 II(哈希)

给你一个整数数组 hours，表示以小时为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成整天的下标对 i, j 的数目。

整天定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

示例 1：

输入： hours = [12,12,30,24,24]

输出： 2

解释：

构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]

输出： 3

解释：

构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

提示：

1 <= hours.length <= 5 * 10^5

1 <= hours[i] <= 10^9

💡

这题的范围与第一题相比数组的范围变成5*10^5，双重循环不了一点了，那就压缩成一层循环

💡

其实做多了就会知道一个套路，借助哈希表可以将往往本来需要双重循环的变成一层循环，每次枚举到当前元素都先将哈希表内记录之前元素的值在答案上累计，再更新当前元素到哈希表

💡

这道题需要统计不同的小时数是否是整天，可以很容易地想到将小时数对24取模，并用哈希表计数，每次只需要累计上与24互补的元素累计到答案即可

💡

注意算互补的时候需要再模上24，因为24-0=24，次数仍然需要统计0的个数

施咒的最大总伤害(DP)

一个魔法师有许多不同的咒语。

给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。

已知魔法师使用伤害值为 power[i] 的咒语时，他们就不能使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。

每个咒语最多只能被使用一次。

请你返回这个魔法师可以达到的伤害值之和的 最大值 。

示例 1：

输入：power = [1,1,3,4]

输出：6

解释：

可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。

示例 2：

输入：power = [7,1,6,6]

输出：13

解释：

可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。

提示：

1 <= power.length <= 10^5

1 <= power[i] <= 10^9

💡

很像打家劫舍，但是前者是对相邻位置的锁定，这题是对相邻的值域锁定，转移方法也可以类似地去考虑

💡

dp[i]表示从0~i中选能获得的最大总伤害，由于左右是对称的，选中了两边的都不能选，所以我们只需要考虑一边即可。两种状态选和不选，不选就从上一个状态转移，选就需要一个最大的状态转移过来

💡

注意这里值域是很大的，需要用哈希表而不是数组

数组中的峰值(树状数组)

数组 arr 中大于前面和后面相邻元素的元素被称为峰值元素。

给你一个整数数组 nums 和一个二维整数数组 queries 。

你需要处理以下两种类型的操作：

queries[i] = [1, li, ri] ，求出子数组 nums[li..ri] 中峰值元素的数目。

queries[i] = [2, indexi, vali] ，将 nums[indexi] 变为 vali

。

请你返回一个数组 answer ，它依次包含每一个第一种操作的答案。

注意：

子数组中 第一个 和 最后一个 元素都不是峰值元素。

示例 1：

输入：nums = [3,1,4,2,5], queries = [[2,3,4],[1,0,4]]

输出：[0]

解释：

第一个操作：我们将 nums[3] 变为 4 ，nums 变为 [3,1,4,4,5] 。

第二个操作：[3,1,4,4,5] 中峰值元素的数目为 0 。

示例 2：

输入：nums = [4,1,4,2,1,5], queries = [[2,2,4],[1,0,2],[1,0,4]]

输出：[0,1]

解释：

第一个操作：nums[2] 变为 4 ，它已经是 4 了，所以保持不变。

第二个操作：[4,1,4] 中峰值元素的数目为 0 。

第三个操作：第二个 4 是 [4,1,4,2,1] 中的峰值元素。

提示：

3 <= nums.length <= 10^5

1 <= nums[i] <= 10^5

1 <= queries.length <= 10^5

queries[i][0] == 1 或者 queries[i][0] == 2

对于所有的 i ，都有：

queries[i][0] == 1 ：0 <= queries[i][1] <= queries[i][2] <= nums.length - 1
queries[i][0] == 2 ：0 <= queries[i][1] <= nums.length - 1, 1 <= queries[i][2] <= 10^5

💡

思维难度感觉不是很大，就是维护一个可单点修改的前缀和即可，线段树就没必要了，树状数组就行

💡

可以先预处理峰值的位置，每次修改只可能改变自己和左右两个元素是否的峰值，计算好结果后更新数组数组即可

💡

这里更新的时候，先撤销峰值，修改后再加上，这样写可以避免很多if条件

💡

需要注意区间查询的时候左右端点是不包含的

🤗 总结归纳

虽然看到了第一第二题是一样的，但还是选择先去第一题暴力

第二题一眼两数之和变种哈希，忘记取互补了wa了一发

第三题一眼DP，打家劫舍，但是因为值域很大wa了一发

第四题一眼树状数组单点更新计算前缀和

上大分只能说

📝 主旨内容

构成整天的下标对数目 I(模拟)

构成整天的下标对数目 II(哈希)

施咒的最大总伤害(DP)

数组中的峰值(树状数组)

🤗 总结归纳

📎 参考文章