使用Python查找大小为M的最新组的程序

假设我们有一个数组arr，它保存了从1到n的数字排列。如果我们有一个大小为n的二进制字符串，最初所有位都设置为零。现在，在每个步骤i（索引从1开始为二进制字符串和arr）中，位置arr[i]的位被设置为1。我们还有另一个值M，并且我们需要找到存在大小为M的一组1的最新步骤。这里的一组1是指一段连续的1的子字符串，它不能在任一方向上扩展。我们需要找到存在长度恰好为M的1组的最新步骤。如果找不到任何这样的组，则返回-1。

因此，如果输入如下arr = [3,5,1,2,4]，M = 3，则输出将为4，因为初始二进制字符串为“00000”，然后以下步骤 –

“00100”，groups：[“1”]
“00101”，groups：[“1”, “1”]
“10101”，groups：[“1”, “1”, “1”]
“11101”，groups：[“111”, “1”]
“11111”，groups：[“11111”]

这里存在大小为3的组的最新步骤为步骤4。

为了解决这个问题，我们将遵循以下步骤 –

n = arr的大小
num = 0
ans = -1
l =大小为n的数组，并填充为0
r =大小为n的数组，并填充为0
对于范围从0到n-1的i，进行：
- 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]
  - l [idx + r [idx] +1] = cur
返回ans

我们看以下实现以更好地理解 –

更多Python相关文章，请阅读：Python 教程

示例

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))