前缀和④Manacher#

第 509 场周赛 - 力扣（LeetCode）

https://www.wolai.com/3pmBJmhrQpNaYijzj3Avkr

Q1-枚举#

题意#

给你一个整数数组 nums。

一个整数的数字范围 定义为其最大数字与最小数字之间的差。

例如，5724 的数字范围为 7 - 2 = 5。

返回 nums 中所有数字范围 等于数组中最大数字范围 的整数之和。

枚举#

1
class Solution:
2
    def maxDigitRange(self, nums: list[int]) -> int:
3
        def f(num):
4
            s = str(num)
5
            return int(max(s)) - int(min(s))
6
        max_ = max(f(num) for num in nums)
7
        return sum(num for num in nums if f(num) == max_)

Q2-状态机DP/前后缀分解#

题意#

给你两个由小写英文字母组成的字符串 s 和 t。

你最多可以选择 s 中的一个下标，并将该下标处的字符替换为任意小写英文字母。

如果可以使 s 成为 t 的一个 子序列，则返回 true；否则返回 false。

子序列 是指通过删除另一个字符串中的某些字符或不删除任何字符，并且不改变剩余字符相对顺序后得到的字符串。

前后缀分解#

枚举修改的下标 i=0,1,2…,∣s∣−1，我们需要知道：

看左边，设 s 的前缀 [0,i−1] 是 t 的前缀 [0,pre[i−1]] 的子序列。看右边，设 s 的后缀 [i+1,∣s∣−1] 是 t 的后缀 [suf[i+1],∣t∣−1] 的子序列。如果 pre[i−1] 和 suf[i+1] 之间至少有一个下标 j，也就是 suf[i+1]−pre[i−1]>1，那么就可以把 s[i] 改成 t[j]，使 s 是 t 的子序列。所以 pre[i−1] 越小越好，suf[i+1] 越大越好。

1
class Solution:
2
    def canMakeSubsequence(self, s: str, t: str) -> bool:
3
        n, m = len(s), len(t)
4
        suf = [0] * (n + 1)
5
        suf[n] = m
6
        j = m
7
        for i in range(n - 1, -1, -1):
8
            j -= 1
9
            while j >= 0 and t[j] != s[i]:
10
                j -= 1
11
            suf[i] = j
12
        if suf[0] >= 0:
13
            return True
14
        pre = -1
15
        for i, ch in enumerate(s):
16
            if suf[i + 1] - pre > 1:
17
                return True
18
            pre += 1
19
            while pre < m and t[pre] != ch:
20
                pre += 1
21
        return False

音乐

音乐

509周赛-①Q1-枚举②Q2-状态机DP/前后缀分解③枚举质因子/线段树/前缀和④Manacher#

Q1-枚举#

题意#

枚举#

Q2-状态机DP/前后缀分解#

题意#

前后缀分解#

状态机DP#

Q3-枚举质因子/线段树/前缀和#

Q4-Manacher#

音乐

目录