leetcode weekly contest 402

100304. 构成整天的下标对数目 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] <= 109

地址

https://leetcode.cn/contest/weekly-contest-402/problems/count-pairs-that-form-a-complete-day-i/

题意

直接枚举

思路

最直接的方法进行枚举所有的数对即可。
复杂度分析：

时间复杂度：$O(n^2)$。
空间复杂度：$O(1)$。

代码

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        ans = 0
        for i in range(len(hours)):
            for j in range(0, i):
                if (hours[i] + hours[j]) % 24 == 0:
                    ans += 1
        return ans

100301. 构成整天的下标对数目 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 * 105
1 <= hours[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-402/problems/count-pairs-that-form-a-complete-day-ii/

题意

哈希统计

思路

我们知道对于给定的数 $x$ ，它一定可以与 $24 - (x\mod 24)$ 的数配对从而构成整天，此时题目就变得非常简单了，我们统计所有数对 $24$ 取模的结果，并分别凑对计算即可，需要注意的是 $0，12$ 只能与本身进行凑对，此时需要特别注意的是重复计算的问题。
复杂度分析：

时间复杂度：$O(n )$，其中 $n$ 表示给定数组的长度。
空间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。

代码

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        cnt = [0] * 24
        for v in hours:
            cnt[v % 24] += 1
        return cnt[0] * (cnt[0] - 1) // 2 + cnt[12] * (cnt[12] - 1) // 2 + sum(cnt[i] * cnt[24 - i] for i in range(1, 12))

impl Solution {
    pub fn count_complete_day_pairs(hours: Vec<i32>) -> i64 {
        let mut cnt = vec![0; 24];
        for x in hours.iter() {
            cnt[(x % 24) as usize] += 1;
        }
        let mut res = 0 as i64;
        for i in 1..12 {
            res += cnt[i] * cnt[24 - i] as i64;
        }
        res += cnt[0] * (cnt[0] - 1) / 2 as i64;
        res += cnt[12] * (cnt[12] - 1) / 2 as i64;
        return res;
    }
}

100316. 施咒的最大总伤害

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

给你一个数组 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 <= 105
1 <= power[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-402/problems/maximum-total-damage-with-spell-casting/

题意

动态规划

思路

典型的动态规划，如果选择了 $x$ 就不能选择 $(x-2,x-1,x+1,x+2)$ 这四个元素，此时我们需要将数组按照从小到大排序且按照数组元素的大小进行分组，假设 $dp[i]$ 表示前 $i$ 个元素选择部分元素所有能构成的魔法值的最大值，此时可以知道如果我们选择了 $power[i]$ ，则不能选择 $power[i-1],power[i-2]$，此时我们可以推理如下：
- $dp[i] = \max(dp[i-1], cnt[i] * power[i] + dp[j]), power[i] - power[j] > 2$;
- $dp[i] = power[i] * cnt[i]， if \quad i = 0$;
复杂度：

时间复杂度：$O(n \times \log n)$，其中 $n$ 表示给定数组的长度；
空间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度；

代码

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        cnt = Counter(power)
        arr = [(k, v) for k,v in cnt.items()]
        arr.sort()
      
        dp = [0] * len(arr)
        j = 0
        for i, (x, c) in enumerate(arr):
            dp[i] = c * x
            while x - arr[j][0] > 2:
                j += 1
            if i > 0:
                dp[i] = max(dp[i], dp[i - 1])
            if j > 0:
                dp[i] = max(dp[i], dp[j - 1] + c * x)
        return max(dp)

3187. 数组中的峰值

数组 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 <= 105
1 <= nums[i] <= 105
1 <= queries.length <= 105
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] <= 105

地址

https://leetcode.cn/contest/weekly-contest-402/problems/peaks-in-array/

题意

线段树

思路

基本上看到范围查找基本上就会想到了线段树或者树状数组，比较简单的模板题目了。首先我们计算出每个索引 $i$ 是否为峰值元素，如果该位置为峰值元素，则标记为 $1$ ，否则标记为 $0$，此时我们建立线段树，对于查询范围 $[l,r]$ 中峰值元素的数目即等于查询数组 $[l,r]$ 范围内元素的和。此时如果我们修改元素 $nums[i]$ 时，此时它会影响 $i-1, i, i + 1$ 这三个位置中峰值元素的变化，最简单的直接的办法：
- 将 $i-1,i,i+1$ 三个位置全部标记为 $0$；
- 然后分别判断 $i-1, i, i +1$ 三个位置是否为峰值元素，再进行标记即可，使用线段树的单点更新即可；
- 总体来说比较模板的题目，使用线段树的范围查找与单点更新即可，连范围更新都不需要；
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 表示给定数组的长度;
空间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度；

代码

class Solution:
    def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        tree = [0] * 4 * n
        arr = [0] * n
        for i in range(1, n - 1):
            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
                arr[i] = 1
            
        def buildTree(idx, l, r):
            if l > r:
                return
            if l == r:
                tree[idx] = arr[l]
                return
            mid = (l + r) // 2
            buildTree(idx * 2, l, mid)
            buildTree(idx * 2 + 1, mid + 1, r)
            tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]
        
        def update(idx, l, r, x, val):
            if x < l or x > r:
                return
            if x == l and x == r:
                arr[x] = val
                tree[idx] = val
                return
            
            mid = (l + r) // 2
            if x <= mid:
                update(idx * 2, l, mid, x, val)
            else:
                update(idx * 2 + 1, mid + 1, r, x, val)
            tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]
        
        def query(idx, l, r, left, right) -> int:
            if right < l or left > r:
                return 0
            if l >= left and r <= right:
                return tree[idx]
            
            mid = (l + r) // 2
            if right <= mid:
                return query(idx * 2, l, mid, left, right)
            elif left > mid:
                return query(idx * 2 + 1, mid + 1, r, left, right)
            else:
                return query(idx * 2, l, mid, left, mid) + query(idx * 2 + 1, mid + 1, r, mid + 1, right)
        
        res = []
        buildTree(1, 0, n - 1)
        print(tree)
        for q in queries:
            if q[0] == 1:
                l, r = q[1] + 1, q[2] - 1
                res.append(query(1, 0, n - 1, l, r))
            else:
                index, val = q[1], q[2]
                nums[index] = val
                update(1, 0, n - 1, index, 0)
                if index - 1 >= 0 and index + 1 < n and nums[index] > nums[index - 1] and nums[index] > nums[index + 1]:
                    update(1, 0, n - 1, index, 1)
                if index - 1 > 0:
                    update(1, 0, n - 1, index - 1, 0)
                    if index - 2 >= 0 and nums[index - 1] > nums[index - 2] and nums[index - 1] > nums[index]:
                        update(1, 0, n - 1, index - 1, 1)
                if index + 1 < n:
                    update(1, 0, n - 1, index + 1, 0)
                    if index + 2 < n and nums[index + 1] > nums[index] and nums[index + 1] > nums[index + 2]:
                        update(1, 0, n - 1, index + 1, 1)
        return res

欢迎关注和打赏，感谢支持！

关注我的博客: https://mike-box.github.io/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 哪些奋斗者

Tags: 题解力扣周赛赛

← leetcode weekly contest 401 leetcode biweekly contest 133 →

扫描二维码，分享此文章