数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用 Python 查找大小为 M 的最新分组的程序
假设我们有一个数组 arr，它包含从 1 到 n 的数字排列。如果我们有一个大小为 n 的二进制字符串，并且最初所有位都设置为零。现在，在从 1 到 n 的每个步骤 i（二进制字符串和 arr 的索引都从 1 开始），位置 arr[i] 的位设置为 1。我们还有另一个值 m，我们需要找到存在大小为 m 的 1 的分组的最新步骤。这里，1 的分组指的是连续的 1 的子字符串，不能向任何方向扩展。我们必须找到存在长度正好为 m 的 1 的分组的最新步骤。如果找不到这样的分组，则返回 -1。
因此，如果输入类似于 arr = [3,5,1,2,4] m = 3，则输出将为 4，因为初始二进制字符串为“00000”，然后按照以下步骤进行：
“00100”，分组：["1"]
“00101”，分组：["1", "1"]
“10101”，分组：["1", "1", "1"]
“11101”，分组：["111", "1"]
“11111”，分组：["11111"]
这里，存在大小为 3 的分组的最新步骤是步骤 4。
为了解决这个问题，我们将遵循以下步骤：
n := arr 的大小
num := 0
ans := -1
l := 一个大小为 n 的数组，并填充 0
r := 一个大小为 n 的数组，并填充 0
对于 i in range 0 到 n - 1，执行：
cur := 1
idx := arr[i] - 1
如果 r[idx] 等于 m，则：
num := num - 1
如果 l[idx] 等于 m，则：
num := num - 1
cur := cur + l[idx] + r[idx]
num := num + (cur 等于 m)
如果 num > 0，则：
ans := ans 和 i + 1 的最大值
如果 idx - l[idx] > 0，则：
r[idx - l[idx] - 1] := cur
如果 idx + r[idx] < n - 1，则：
l[idx + r[idx] + 1] := cur
返回 ans
让我们看看下面的实现以更好地理解：
示例
def solve(arr, m): n = len(arr) num = 0 ans = -1 l = [0] * n r = [0] * n for i in range(n): cur = 1 idx = arr[i] - 1 if r[idx] == m: num -= 1 if l[idx] == m: num -= 1 cur += l[idx] + r[idx] num += cur == m if num > 0: ans = max(ans, i + 1) if idx - l[idx] > 0: r[idx - l[idx] - 1] = cur if idx + r[idx] < n - 1: l[idx + r[idx] + 1] = cur return ans arr = [3,5,1,2,4] m = 3 print(solve(arr, m))
输入
[3,5,1,2,4], 3
输出
4
142 次查看
