目录
100304. 构成整天的下标对数目 I
原题链接
思路分析
AC代码
100301. 构成整天的下标对数目 II
原题链接
思路分析
AC代码
100316. 施咒的最大总伤害
原题链接
思路分析
AC代码
100317. 数组中的峰值
原题链接
思路分析
AC代码
100304. 构成整天的下标对数目 I
原题链接
100304. 构成整天的下标对数目 I
思路分析
遍历+哈希
一次遍历，我们记录余数的出现次数即可
时间复杂度：O(N)
AC代码
class Solution:def countCompleteDayPairs(self, hours: List[int]) -> int:cnt = [0] * 24res = 0for x in hours:res += cnt[(24 - (x % 24)) % 24]cnt[x % 24] += 1return res100301. 构成整天的下标对数目 II
原题链接
100301. 构成整天的下标对数目 II
思路分析
和上一题一样
AC代码
class Solution:def countCompleteDayPairs(self, hours: List[int]) -> int:cnt = [0] * 24res = 0for x in hours:res += cnt[(24 - (x % 24)) % 24]cnt[x % 24] += 1return res100316. 施咒的最大总伤害
原题链接
100316. 施咒的最大总伤害
思路分析
树状数组+二分+线性dp
先将原数组排序去重记为st，记录每个咒语出现次数cnt[]
定义状态f[i]为以咒语i结尾的方案的最大伤害
那么我们可以从f[j]转移，其中 st[j] < s[i] - 2
那么我们只需要求出f[0, j]的最大值进行转移即可
求前缀最大值直接树状数组即可
快速找到j，二分即可
时间复杂度：O(nlogn)
AC代码
class Fenwick:def __init__(self, n: int):self.n = nself.tr = [0] * (n + 1)def add(self, x: int, k: int) -> None:n = self.ntr = self.trwhile x <= n:tr[x] = max(tr[x], k)x += x & -xdef query(self, x: int) -> None:res = 0tr = self.trwhile x:res = max(res, tr[x])x &= x - 1return resclass Solution:def maximumTotalDamage(self, power: List[int]) -> int:cnt = Counter(power)st = sorted(set(power))n = len(st)f = [0] * (n + 1)tr = Fenwick(n)for i in range(1, n + 1):lt = bisect_left(st, st[i - 1] - 2)f[i] = tr.query(lt) + cnt[st[i - 1]] * st[i - 1]tr.add(i, f[i])return max(f)100317. 数组中的峰值
原题链接
100317. 数组中的峰值
思路分析
树状数组+模拟
树状数组维护前缀山峰数目
考虑修改num[x]只会影响nums[x, x-1, x+1]三个位置的状态，我们每次修改操作最多涉及三次树状数组单点修改
我们用vis[i]表示i是否是山峰
然后修改后如果vis[i] != 新值，那么根据新值和原状态的关系来决定如何更新，是+1还是-1
需要注意的细节：查询[l, r]的山峰数目，l 和 r不算山峰
时间复杂度：O(nlogn)
AC代码
class Fenwick:def __init__(self, n: int):self.n = nself.tr = [0] * (n + 1)def add(self, x: int, k: int) -> None:n = self.ntr = self.trwhile x <= n:tr[x] += kx += x & -xdef query(self, x: int) -> None:res = 0tr = self.trwhile x:res += tr[x]x &= x - 1return resclass Solution:def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:res = []n = len(nums)cur = 0tr = Fenwick(n)vis = [False] * (n)for i in range(1, n - 1):if nums[i - 1] < nums[i] > nums[i + 1]:tr.add(i + 1, 1)vis[i] = Truedef upd(x: int) -> None:nt = (nums[x - 1] < nums[x] > nums[x + 1])if nt != vis[x]:vis[x] = ntif nt:tr.add(x + 1, 1)else:tr.add(x + 1, -1)for i, (op, x, y) in enumerate(queries):if op == 1:res.append(max(0, tr.query(y) - tr.query(x + 1)))else:nums[x] = yif 0 < x - 1 < n - 1:upd(x - 1)if 0 < x < n - 1:upd(x)if 0 < x + 1 < n - 1:upd(x + 1)return res
