[算法训练] 509周赛-①Q1-枚举②Q2-状态机DP/前后缀分解③枚举质因子/线段树/前缀和④Manacher
533 字
3 分钟
[算法训练] 509周赛-①Q1-枚举②Q2-状态机DP/前后缀分解③枚举质因子/线段树/前缀和④Manacher
509周赛-①Q1-枚举②Q2-状态机DP/前后缀分解③枚举质因子/线段树/前缀和④Manacher
https://www.wolai.com/3pmBJmhrQpNaYijzj3Avkr
Q1-枚举
题意
给你一个整数数组 nums。
一个整数的数字范围 定义为其 最大数字与 最小 数字之间的差。
例如，5724 的数字范围为 7 - 2 = 5。
返回 nums 中所有数字范围 等于数组中最大数字范围 的整数之和。
枚举
class Solution: def maxDigitRange(self, nums: list[int]) -> int: def f(num): s = str(num) return int(max(s)) - int(min(s)) max_ = max(f(num) for num in nums) 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] 越大越好。
class Solution: def canMakeSubsequence(self, s: str, t: str) -> bool: n, m = len(s), len(t) suf = [0] * (n + 1) suf[n] = m j = m for i in range(n - 1, -1, -1): j -= 1 while j >= 0 and t[j] != s[i]: j -= 1 suf[i] = j if suf[0] >= 0: return True pre = -1 for i, ch in enumerate(s): if suf[i + 1] - pre > 1: return True pre += 1 while pre < m and t[pre] != ch: pre += 1 return False状态机DP
Q3-枚举质因子/线段树/前缀和
Q4-Manacher
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
[算法训练] 509周赛-①Q1-枚举②Q2-状态机DP/前后缀分解③枚举质因子/线段树/前缀和④Manacher
http://blog.7a7a68.xyz/posts/509周赛-q1-枚举q2-状态机dp-前后缀分解枚举质因子-线段树-前缀和-manache-1/ 相关文章 智能推荐
1
[算法训练] 186双周赛-①Q1-枚举②Q2-贪心/状态机DP③前缀和优化DP
算法训练 LeetCode186双周赛
2
[算法训练] 514周赛-①Q1-贪心②Q2-DFS③Q3-DP预处理+二分答案+二维前缀和④Q4-线段树
算法训练 LeetCode514周赛
3
[算法训练] 513周赛-①Q3-二分+前缀和Q2/Q4-树状数组+逆序对
算法训练 LeetCode513周赛
4
[算法训练] 512周赛-①Q1-贪心②Q2-双指针③Q3-组合数学
算法训练 LeetCode512周赛
5
[算法训练] 507周赛-①贪心②前缀和+暴力枚举/前缀和+三指针滑动窗口③分层图最短路④二分答案
算法训练 LeetCode507周赛
随机文章 随机推荐