507周赛-①贪心②前缀和+暴力枚举/前缀和+三指针滑动窗口③分层图最短路④二分答案#

Q1-贪心#

题目#

给你一个由字符 'U'、'D'、'L'、'R' 和 '_' 组成的字符串 moves。

从原点 (0, 0) 出发，每个字符表示二维平面上的一次移动：

'U'：向上移动 1 个单位。
'D'：向下移动 1 个单位。
'L'：向左移动 1 个单位。
'R'：向右移动 1 个单位。
'_'：可以独立地替换为 'U'、'D'、'L' 或 'R' 中的任意一个字符。

返回执行完所有移动后，能够达到的距离原点的 最大曼哈顿距离 。

两点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离为 |x1- x2| + |y1- y2|。

贪心#

1
class Solution:
2
    def maxDistance(self, moves: str) -> int:
3
        x = y = 0
4
        ans = 0
5
        for ch in moves:
6
            if ch == 'U':
7
                y += 1
8
            elif ch == 'D':
9
                y -= 1
10
            elif ch == 'L':
11
                x -= 1
12
            elif ch == 'R':
13
                x += 1
14
            else:
15
                ans += 1
16
        return abs(x) + abs(y) + ans

Q2-前缀和+暴力枚举/前缀和+三指针滑动窗口#

题目#

给你一个整数数组 nums 和一个整数数字 x。

如果一个 子数组 nums[l..r] 的元素和同时满足以下两个条件，则认为该子数组是有效子数组：

该和的首位数字等于 x。
该和的末位数字等于 x。

返回有效子数组的数量。

子数组是数组中一个连续 、非空 的元素序列。

前缀和+暴力#

枚举子数组的左右端点。

在枚举右端点的同时，维护子数组的元素和 s。

1
class Solution:
2
    def countValidSubarrays(self, nums: list[int], x: int) -> int:
3
        n = len(nums)
4
        pre = [0]*(n+1)
5
        for i in range(n):
6
            pre[i+1] = pre[i] + nums[i]
7
        ans = 0
8
        for l in range(n):
9
            for r in range(l,n):
10
                sub = pre[r+1] - pre[l]
11
                last = sub%10
12
                if last != x:
13
                    continue
14
                firs = int(str(sub)[0])
15
                if firs == x:
16
                    ans += 1
17
        return ans

1
class Solution:
2
    def countValidSubarrays(self, nums: list[int], x: int) -> int:
3
        ans = 0
4

5
        # 枚举子数组的左右端点
6
        for i in range(len(nums)):
7
            s = 0
8
            for v in nums[i:]:
9
                s += v
10
                # 计算 s 的最低位
11
                if s % 10 != x:
12
                    continue
13
                # 计算 s 的最高位
14
                t = s
15
                while t > 9:
16
                    t //= 10
17
                if t == x:
18
                    ans += 1
19

20
        return ans

前缀和+三指针滑动窗口#

灵神题解地址：

3969. 求和后首尾数字相同的有效子数组 I - 力扣（LeetCode）

1
class Solution:
2
    def countValidSubarrays(self, nums: list[int], x: int) -> int:
3
        pre = list(accumulate(nums, initial=0))
4
        ans = 0
5

6
        # 枚举子数组和的十进制长度
7
        low, high = x, x + 1
8
        while low <= pre[-1]:
9
            # 计算子数组和在 [low, high-1] 中，且子数组和模 10 为 x 的子数组个数
10
            cnt = [0] * 10
11
            left1 = left2 = 0
12
            for s in pre:
13
                # 随着 s 的增大，<= s-high 的前缀和离开窗口，<= s-low 的前缀和进入窗口
14
                while pre[left1] <= s - high:
15
                    cnt[pre[left1] % 10] -= 1
16
                    left1 += 1
17
                while pre[left2] <= s - low:
18
                    cnt[pre[left2] % 10] += 1
19
                    left2 += 1
20
                ans += cnt[(s - x) % 10]
21
            low *= 10
22
            high *= 10
23

24
        return ans

Q3-分层图最短路#

题目#

给你一个整数 n，表示一个 有向加权图中的节点数量，节点编号从 0 到 n - 1。该图由二维数组 edges 表示，其中 edges[i] = [ui, vi, wi] 表示一条从节点 ui 指向节点 vi、权重为 wi 的有向边。

另给定一个长度为 n 的字符串 labels，其中 labels[i] 是分配给节点 i 的字符，以及一个整数 k。

返回一条从节点 0 到节点 n - 1 的路径的最小总边权，并要求该路径上所有节点标签按顺序拼接后，最多包含 k 个 连续相同字符。如果不存在有效路径，返回 -1。

分层图最短路#

定义 dis[x][cnt] 表示从节点 0 到节点 x 的最短路长度，且最后连续相同字母个数为 cnt。

初始值 dis[0][1]=0。

对于边权为 w 的边 x→y，分类讨论：

如果 labels[x]=labels[y]，那么重新计数，用 dis[x][cnt]+w 更新 dis[y][1] 的最小值。如果 labels[x]=labels[y] 且 cnt+1≤k，那么累加连续相同字母个数，用 dis[x][cnt]+w 更新 dis[y][cnt+1] 的最小值。注：根据 Dijkstra 算法的原理，当节点 n−1 首次出堆时，我们就算出了从节点0 到节点 n−1 的最短路，可以直接返回答案。

1
class Solution:
2
    def shortestPath(self, n: int, edges: List[List[int]], labels: str, k: int) -> int:
3
        g = [[] for _ in range(n)]
4
        for u,v,w in edges:
5
            g[u].append((v,w))
6
        lab = [ord(c) - ord('a') for c in labels]
7
        vis = set()
8
        pq = [(0,0,1,lab[0])]
9
        while pq:
10
            w,node,l,ch = heapq.heappop(pq)
11
            if node == n-1:
12
                return w
13
            st = (node,l,ch)
14
            if st in vis:
15
                continue
16
            vis.add(st)
17
            for ne,ne_w in g[node]:
18
                ne_ch = lab[ne]
19
                if ne_ch == ch:
20
                    n_l = l + 1
21
                    if n_l > k:
22
                        continue
23
                else:
24
                    n_l = 1
25
                n_st = (ne,n_l,ne_ch)
26
                if n_st not in vis:
27
                    heapq.heappush(pq,(w+ne_w,ne,n_l,ne_ch))
28
        return -1

Q4-二分答案#

题目#

给你两个整数数组 value 和 decay，以及一个整数 m。

value[i] 表示下标 i 的初始价值。
decay[i] 表示每次选择下标 i 后，该下标的价值会减少的数值。

你可以多次选择任意下标。所有下标的总选择次数不得超过 m。

如果重复选择下标 i，第 t 次（从 1 开始计数）获得的价值为 value[i] - decay[i] * (t - 1)。

返回你能够获得的最大总价值。由于答案可能很大，请返回其对 109 + 7 取模后的结果。

二分答案#

1
class Solution:
2
    def maxTotalValue(self, value: list[int], decay: list[int], m: int) -> int:
3
        def check(low: int) -> bool:
4
            left_m = m
5
            for v, d in zip(value, decay):
6
                if v >= low:
7
                    left_m -= (v - low) // d + 1
8
                    if left_m < 0:  # 提前跳出循环
9
                        return True
10
            return False
11

12
        left, right = 0, max(value) + 1
13
        while left + 1 < right:
14
            mid = (left + right) // 2
15
            if check(mid):
16
                left = mid
17
            else:
18
                right = mid
19
        low = left
20

21
        ans = 0
22
        # 计算价值严格大于 low 的价值和，以及这些价值的个数
23
        for v, d in zip(value, decay):
24
            if v > low:
25
                k = (v - low - 1) // d + 1
26
                m -= k
27
                ans += (v * 2 - d * (k - 1)) * k
28
        ans //= 2  # 把除以 2 提到循环外面
29
        ans += m * low  # 剩余 m 次选的价值都是 low
30
        return ans % 1_000_000_007

音乐

音乐