使用 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