使用 Python 查找大小为 M 的最新组的程序
假设我们有一个数组 arr，它保存了从 1 到 n 的数字排列。如果我们有一个大小为 n 的二进制字符串，并且最初它的所有位都设置为零。现在在从 1 到 n 的每一步 i（二进制字符串和 arr 的索引都从 1 开始），位置 arr[i] 处的位被设置为 1。我们还有另一个值 m，我们需要找到最新的存在一组大小为 m 的步骤。这里的一组 1 表示一个连续的 1 子串，这样它就不能在任一方向上扩展。我们必须找到存在一组长度正好为 m 的组的最新一步。如果我们找不到任何这样的组，则返回 -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 的大小
数量：= 0
答案：= -1
l := 大小为 n 的数组，并用 0 填充
r := 大小为 n 的数组，并用 0 填充
对于 0 到 n - 1 范围内的 i，请执行
l[idx + r[idx] + 1] := 当前
r[idx - l[idx] - 1] := cur
ans := ans 的最大值，i + 1
数量 := 数量 - 1
数量 := 数量 - 1
当前：= 1
idx := arr[i] - 1
如果 r[idx] 与 m 相同，则
如果 l[idx] 与 m 相同，则
cur := cur + l[idx] + r[idx]
num := num + cur 与 m 相同
如果 num > 0，则
如果 idx - l[idx] > 0，则
如果 idx + r[idx] < n - 1，则
返回答案
让我们看看以下实现以获得更好的理解 -
示例
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
以上是 使用 Python 查找大小为 M 的最新组的程序 的全部内容， 来源链接： utcz.com/z/317369.html
